基于拓扑连接紧密度的相似性链路预测算法

doi:10.11772/j.issn.1001-9081.2017.08.2129

计算机应用 ›› 2017, Vol. 37 ›› Issue (8): 2129-2132.DOI: 10.11772/j.issn.1001-9081.2017.08.2129

• 网络与通信 • 下一篇

基于拓扑连接紧密度的相似性链路预测算法

丁大钊, 陈云杰, 靳彦青, 刘树新

国家数字交换系统工程技术研究中心, 郑州 450002

收稿日期:2017-02-24 修回日期:2017-05-06 出版日期:2017-08-10 发布日期:2017-08-12
通讯作者: 丁大钊
作者简介:丁大钊(1979-),男,河南许昌人,工程师,硕士,主要研究方向:通信与信息系统;陈云杰(1981-),男,河南新乡人,工程师,硕士,主要研究方向:无线通信网络安全;靳彦青(1983-),女,河南南召人,工程师,主要研究方向:无线通信;刘树新(1987-),男,山东潍坊人,博士,主要研究方向:复杂网络。
基金资助:
国家863计划项目（2015AA01A708，2016YFB0801605）。

Link prediction method for complex network based on closeness between nodes

DING Dazhao, CHEN Yunjie, JIN Yanqing, LIU Shuxin

National Digital Switching System Engineering and Technological R & D Center, Zhengzhou Henan 450002, China

Received:2017-02-24 Revised:2017-05-06 Online:2017-08-10 Published:2017-08-12
Supported by:
This work is partially supported by the National High Technology Research and Development Program (863 Program) of China (2015AA01A708,2016YFB080160).

摘要/Abstract

摘要： 许多链路预测方法仅仅关注预测的准确度衡量指标，忽略了精确度衡量标准在实际应用中的重要作用，且没有考虑共同邻居与预测节点间紧密度对相似性刻画的影响。针对上述问题，提出了一种基于拓扑连接紧密度的相似性链路预测算法。该方法通过局部拓扑结构定义共同邻居紧密度，并引入参数调节不同网络中紧密程度，最终刻画网络节点间的相似度。6个实际网络测试表明，相比共同邻居（CN）、资源分配（RA）、Adamic-Adar（AA）、局部路径（LP）、Katz等相似性指标，该算法提升了链路预测的预测精度。

关键词: 复杂网络, 链路预测, 紧密度, 相似性, 拓扑结构

Abstract: Many link prediction methods only focus on the standard metric AUC (Area Under receiver operating characteristic Curve), ignoring the metric precision and closeness of common neighbors and endpoints under different topological structures. To solve these problems, a link prediction method based on closeness between nodes was proposed. In order to describe the similarity between endpoints more accurately, the closeness of common neighbors was designed by considering the local topological information around common neighbors, which was adjusted for different networks through a parameter. Empirical study on six real networks show that compared with the similarity indicators such as Common Neighbor (CN), Resource Allocation (RA), Adamic-Adar (AA), Local Path (LP) and Katz, the proposed index can improve the prediction accuracy.

Key words: complex network, link prediction, closeness, similarity, topological structure

中图分类号:

TP393.02

丁大钊, 陈云杰, 靳彦青, 刘树新. 基于拓扑连接紧密度的相似性链路预测算法[J]. 计算机应用, 2017, 37(8): 2129-2132.

DING Dazhao, CHEN Yunjie, JIN Yanqing, LIU Shuxin. Link prediction method for complex network based on closeness between nodes[J]. Journal of Computer Applications, 2017, 37(8): 2129-2132.

参考文献

[1] GAO Z-K, SMALL M, KURTHS J. Complex network analysis of time series[J]. Europhysics Letters, 2017, 116(5):50001-50005.
[2] LIU S, JI X, LIU C, et al. Similarity indices based on link weight assignment for link prediction of unweighted complex networks[J]. International Journal of Modern Physics B, 2016, 31(2):1650254.
[3] ZHANG Y, BAO Z, CAO Y, et al. Long-term effect of different topology evolutions on blackouts in power grid[J]. International Journal of Electrical Power & Energy Systems, 2014, 62(2014):718-726.
[4] 刘树新,季新生,刘彩霞,等.一种信息传播促进网络增长的网络演化模型[J].物理学报,2014,63(15):158902. (LIU S X, JI X S, LIU C X, et al. A complex network evolution model for network growth promoted by information transmission[J]. Acta Physica Sinica, 2014, 63(15):158902.
[5] PECH R, HAO D, PAN L, et al. Link prediction via matrix completion[J]. Europhysics Letters, 2017, 117(3):38002.
[6] WANG P, XU B W, WU Y R, et al. Link prediction in social networks:the state-of-the-art[J]. Science China Information Sciences, 2015, 58(1):1-38.
[7] VON MERING C, JENSEN L J, SNEL B, et al. STRING:known and predicted protein-protein associations, integrated and transferred across organisms[J]. Nucleic Acids Research, 2005(33):D433-D437.
[8] SCELLATO S, NOULAS A, MASCOLO C. Exploiting place features in link prediction on location-based social networks[C]//KDD' 11:Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York:ACM, 2011:1046-1054.
[9] HOLLAND P W, LASKEY K B, LEINHARDT S. Stochastic blockmodels:first steps[J]. Social Networks, 1983, 5(2):109-137.
[10] FENG X, ZHAO J C, XU K. Link prediction in complex networks:a clustering perspective[J]. The European Physical Journal B, 2012, 85:3.
[11] LÜ L, ZHOU T. Link prediction in complex networks:a survey[J]. Physica A:Statistical Mechanics and its Applications, 2011, 390(6):1150-1170.
[12] LORRAIN F, WHITE H C. Structural equivalence of individuals in social networks[J]. The Journal of Mathematical Sociology, 1971, 1(1):49-80.
[13] ZHOU T, LV L, ZHANG Y-C. Predicting missing links via local information[J]. The European Physical Journal B, 2009, 71(4):623-630.
[14] ADAMIC L A, ADAR E. Friends and neighbors on the Web[J]. Social Networks, 2003, 25(3):211-230.
[15] LV L, JIN C-H, ZHOU T. Similarity index based on local paths for link prediction of complex networks[J]. Physical Review E, Statistical, Nonlinear, and Soft Matter Physics, 2009, 80(4):046122.
[16] LIU S, JI X, LIU C, et al. Extended resource allocation index for link prediction of complex network[J]. Physica A:Statistical Mechanics and its Applications, 2017, 479:174-183.
[17] 刘思,刘海,陈启买,等.基于网络表示学习与随机游走的链路预测算法[J/OL].计算机应用,2017[2017-04-01]. http://www.joca.cn/CN/abstract/abstract20373.shtml. (LIU S, LIU H, CHEN Q M, et al. Link prediction algorithm based on network representation learning and random walk[J/OL]. Journal of Computer Applications, 2017[2017-04-01]. http://www.joca.cn/CN/abstract/abstract20373.shtml.)
[18] LEICHT E A, HOLME P, NEWMAN M E J. Vertex similarity in networks[J]. Physical Review E, Statistical, Nonlinear, and Soft Matter Physics, 2006, 73(2):026120.
[19] FOUSS F, PIROTTE A, RENDERS J-M, et al. Random-walk computation of similarities between nodes of a graph with application to collaborative recommendation[J]. IEEE Transactions on Knowledge and Data Engineering, 2007, 19(3):355-369.
[20] HERLOCKER J L, KONSTAN J A, TERVEEN L G, et al. Evaluating collaborative filtering recommender systems[J]. ACM Transactions on Information Systems, 2004, 22(1):5-53.
[21] LV L, ZHOU T. Link prediction in weighted networks:the role of weak ties[J]. Europhysics Letters, 2010, 89(1):18001.
[22] GLEISER P M, DANON L. Community structure in Jazz[J]. Advances in Complex Systems, 2003, 6(4):565-573.
[23] ZHANG Q, LV L, WANG W, et al. Potential theory for directed networks[J]. PLoS ONE, 2013, 8(2):e55437.
[24] LV L, PAN L, ZHOU T, et al. Toward link predictability of complex networks[J]. Proceedings of the National Academy of Sciences, 2015, 112(8):2325-2330.
[25] DUCH J, ARENAS A. Community detection in complex networks using extremal optimization[J]. Physical Review E, Statistical, Nonlinear, and Soft Matter Physics, 2005, 72(2):027104.
[26] MICHALSKI R, PALUS S, KAZIENKO P. Matching organizational structure and social network extracted from email communication[C]//BIS 2011:Proceedings of the International Conference on Business Information Systems. Berlin:Springer-Verlag, 2011:197-206.
[27] BU D, ZHAO Y, CAI L, et al. Topological structure analysis of the protein-protein interaction network in budding yeast[J]. Nucleic Acids Research, 2003, 31(9):2443-2450.

基于拓扑连接紧密度的相似性链路预测算法

Link prediction method for complex network based on closeness between nodes

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	蔡彪, 李蕊岑, 吴媛媛. 相似性特征对链路预测的影响与增强[J]. 计算机应用, 2021, 41(9): 2569-2577.
[2]	张元钧, 张曦煌. 基于图卷积与长短期记忆网络的动态网络表示学习模型[J]. 计算机应用, 2021, 41(7): 1857-1864.
[3]	李亚芳, 梁烨, 冯韦玮, 祖宝开, 康玉健. 基于社区优化的深度网络嵌入方法[J]. 计算机应用, 2021, 41(7): 1956-1963.
[4]	王月, 江逸茗, 兰巨龙. 基于改进三元组网络和K近邻算法的入侵检测[J]. 计算机应用, 2021, 41(7): 1996-2002.
[5]	杨蒙蒙, 张爱华. 基于灰度共生矩阵和同步正交匹配追踪的分形图像压缩[J]. 计算机应用, 2021, 41(5): 1445-1449.
[6]	李萍, 汪芬, 陈祺东, 孙俊. 求解多目标社区发现问题的离散化随机漂移粒子群优化算法[J]. 计算机应用, 2021, 41(3): 803-811.
[7]	胡立华, 左威健, 聂瑶瑶. 基于加权相似性度量的特征匹配方法[J]. 计算机应用, 2021, 41(2): 511-516.
[8]	周玉彬, 肖红, 王涛, 姜文超, 熊梦, 贺忠堂. 基于动作周期退化相似性度量的机械轴健康指标构建与剩余寿命预测[J]. 《计算机应用》唯一官方网站, 2021, 41(11): 3192-3199.
[9]	朱琳, 于海涛, 雷新宇, 刘静, 王若凡. 基于MRI图像的阿尔茨海默症患者脑网络特征识别算法[J]. 计算机应用, 2020, 40(8): 2455-2459.
[10]	李卫中. 基于场景局部特征的多曝光图像融合[J]. 计算机应用, 2020, 40(8): 2365-2371.
[11]	葛宇, 梁静. 基于相遇概率时效性和重复扩散感知的机会网络消息转发算法[J]. 计算机应用, 2020, 40(5): 1397-1402.
[12]	王肖, 魏嘉旺, 袁玉波. 基于特征部位圆形域的人脸图像修复方法[J]. 计算机应用, 2020, 40(3): 847-853.
[13]	吕一可, 徐凯, 黄振强. 基于面积划分的轨迹相似性度量方法[J]. 计算机应用, 2020, 40(2): 578-583.
[14]	齐鹏飞, 周丽华, 杜国王, 黄皓, 黄通. 基于聚类的超链路预测[J]. 计算机应用, 2020, 40(2): 434-440.
[15]	郑文萍, 岳香豆, 杨贵. 基于随机游走的改进标签传播算法[J]. 计算机应用, 2020, 40(12): 3423-3429.