Link prediction method for complex network based on closeness between nodes

doi:10.11772/j.issn.1001-9081.2017.08.2129

Journal of Computer Applications ›› 2017, Vol. 37 ›› Issue (8): 2129-2132.DOI: 10.11772/j.issn.1001-9081.2017.08.2129

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).

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

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

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

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

Abstract

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

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

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

CLC Number:

TP393.02

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.

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

References

[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

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

[1]	CAI Biao, LI Ruicen, WU Yuanyuan. Impact and enhancement of similarity features on link prediction [J]. Journal of Computer Applications, 2021, 41(9): 2569-2577.
[2]	ZHANG Cheng, WAN Yuan, QIANG Haopeng. Deep unsupervised discrete cross-modal hashing based on knowledge distillation [J]. Journal of Computer Applications, 2021, 41(9): 2523-2531.
[3]	CHEN Jun, HE Qing. Improved butterfly optimization algorithm based on cosine similarity [J]. Journal of Computer Applications, 2021, 41(9): 2668-2677.
[4]	LI Yafang, LIANG Ye, FENG Weiwei, ZU Baokai, KANG Yujian. Deep network embedding method based on community optimization [J]. Journal of Computer Applications, 2021, 41(7): 1956-1963.
[5]	WU Yue, LUO Jiangtao, LIU Rui, HU Zhongyin. Video similarity detection method based on perceptual hashing and dicing [J]. Journal of Computer Applications, 2021, 41(7): 2070-2075.
[6]	ZHANG Yuanjun, ZHANG Xihuang. Dynamic network representation learning model based on graph convolutional network and long short-term memory network [J]. Journal of Computer Applications, 2021, 41(7): 1857-1864.
[7]	WANG Yue, JIANG Yiming, LAN Julong. Intrusion detection based on improved triplet network and K-nearest neighbor algorithm [J]. Journal of Computer Applications, 2021, 41(7): 1996-2002.
[8]	ZHANG Hao, ZHU Rui, SONG Fuyao, FANG Peng, XIA Xiufeng. Bichromatic reverse k nearest neighbor query method based on distance-keyword similarity constraint [J]. Journal of Computer Applications, 2021, 41(6): 1686-1693.
[9]	YANG Mengmeng, ZHANG Aihua. Fractal image compression based on gray-level co-occurrence matrix and simultaneous orthogonal matching pursuit [J]. Journal of Computer Applications, 2021, 41(5): 1445-1449.
[10]	LI Ping, WANG Fen, CHEN Qidong, SUN Jun. Discrete random drift particle swarm optimization algorithm for solving multi-objective community detection problem [J]. Journal of Computer Applications, 2021, 41(3): 803-811.
[11]	HU Lihua, ZUO Weijian, NIE Yaoyao. Feature matching method based on weighted similarity measurement [J]. Journal of Computer Applications, 2021, 41(2): 511-516.
[12]	Yubin ZHOU, Hong XIAO, Tao WANG, Wenchao JIANG, Meng XIONG, Zhongtang HE. Health index construction and remaining useful life prediction of mechanical axis based on action cycle degradation similarity measurement [J]. Journal of Computer Applications, 2021, 41(11): 3192-3199.
[13]	ZHU Yi, NING Zhenhu, ZHOU Yihua. Lightweight detection technology of typosquatting based on visual features [J]. Journal of Computer Applications, 2020, 40(8): 2279-2285.
[14]	LI Weizhong. Multi-exposure image fusion based on local features of scene [J]. Journal of Computer Applications, 2020, 40(8): 2365-2371.
[15]	ZHU Lin, YU Haitao, LEI Xinyu, LIU Jing, WANG Ruofan. Brain network feature identification algorithm for Alzheimer's patients based on MRI image [J]. Journal of Computer Applications, 2020, 40(8): 2455-2459.