Computer Science ›› 2019, Vol. 46 ›› Issue (12): 20-25.doi: 10.11896/jsjkx.190700057

• Big Data & Data Science • Previous Articles     Next Articles

Link Prediction Based on Correlation of Nodes’ Connecting Patterns

SHAN Na, LI Long-jie, LIU Yu-yang, CHEN Xiao-yun   

  1. (School of Information Science and Engineering,Lanzhou University,Lanzhou,730000,China)
  • Received:2019-04-06 Online:2019-12-15 Published:2019-12-17

Abstract: As a research hotspot in complex network analysis,link prediction has a wide range of applications in many fields,and hence has captured much attention of researchers.Similarity-based methods,which compute the similarity scores between unconnected node pairs based on the known network structures and estimate their connection likelihood according to the similarity scores,are commonly used.In general,different kinds of networks have diverse structural characteristics,and hence the correlation of characteristics between nodes has an important influence on the formation of links.To enhance the performance of link prediction,this paper defined the connecting pattern of a node,and proposed a new link prediction model based on the Correlation of Nodes’ Connecting Patterns (CNCP).By combining CNCP with a similarity-based method,this model can take both similarity and correlation between nodes into account.In this paper,four CNCP-based methods,i.e.,CNCP-CN,CNCP-RA,CNCP-AA and CNCP-PA,are derived from the model,in which similarity indexes are CN(Common Neighbors),RA(Resource Allocation),AA(Adamic-Adar) and PA(Preferential Attachment),respectively.The experimental results on six networks show that the proposed methods are superior to the compared ones under the criteria of AUC and Precision.

Key words: Complex networks, Correlation of nodes’ connecting patterns, Link prediction, Similarity index

CLC Number: 

  • TP391
[1]LV L,ZHOU T.Link prediction in complex networks:A survey[J].Physica A:statistical mechanics and its applications,2011,390(6):1150-1170.
[2]CANNISTRACI C V,ALANIS-LOBATO G,RAVASI T.From link-prediction in brain connectomes and protein interactomes to the local-community-paradigm in complex networks[J].Scienti-fic Reports,2013,3:1613.
[3]SHERKAT E,RAHGOZAR M,ASADPOUR M.Structural link prediction based on ant colony approach in social networks[J].Physica A:Statistical Mechanics and its Applications,2015,419:80-94.
[4]LI F,HE J,HUANG G,et al.Retracted:A clustering-based link prediction method in social networks[J].Procedia Computer Science,2014,29:432-442.
[5]ZHOU T,LV L,ZHANG Y C.Predicting missing links via local information[J].The European Physical Journal B,2009,71(4):623-630.
[6]CLAUSET A,MOORE C,NEWMAN M E J.Hierarchical structure and the prediction of missing links in networks[J].Nature,2008,453(7191):98.
[7]SARUKKAI R R.Link prediction and path analysis using Markov chains[J].Computer Networks,2000,33(1-6):377-386.
[8]SALTON G,MCGILL M J.Introduction to Modern Information Retrieval [M].Auckland:McGraw-Hill,1983.
[9]SØRENSEN T A.A method of establishing groups of equal amplitude in plant sociology based on similarity of species content and its application to analyses of the vegetation on Danish commons[J].Biologiske Skrifter,1948,5(4):1-34.
[10]NEWMAN M E J.Clustering and preferential attachment in growing networks.Physical Review E,2001,64(2):025102.
[11]LV L,JIN C H,ZHOU T.Similarity index based on local paths for link prediction of complex networks[J].Physical Review E,2009,80(4):046122.
[12]KATZ L.A new status index derived from sociometric analysis[J].Psychometrika,1953,18(1):39-43.
[13]LEICHT E A,HOLME P,NEWMAN M E J.Vertex similarity in networks[J].Physical Review E,2006,73(2):026120.
[14]LIU W,LV L.Link prediction based on local random walk[J].EPL (Europhysics Letters),2010,89(5):58007.
[15]WANG T,WANG H,WANG X.CD-Based indices for link prediction in complex network[J].PloS One,2016,11(1):e0146727.
[16]ADAMIC L A,ADAR E.Friends and neighbors on the web[J].Social Networks,2003,25(3):211-230.
[17]BARABÁSI A L,ALBERT R.Emergence of scaling in random networks[J].Science,1999,286(5439):509-512.
[18]GIRVAN M,NEWMAN M M E J.Community structure in social and biological networks[J].Proceedings of the National Academy of Sciences,2002,99(12):7821-7826.
[19]KUNEGIS J.Jazz musicians network dataset[OL].http://
[20]BAIRD D,LUCZKOVICH J,CHRISTIAN R R.Assessment of spatial and temporal variability in ecosystem attributes of the St Marks National Wildlife Refuge,Apalachee Bay,Florida[J].Estuarine,Coastal and Shelf Science,1998,47(3):329-349.
[21]ULANOWICZ R E,BONDAVALLI C,EGNOTOVICH M S. Technical Report:CBL 98-123 (1998)[R/OL].
[22]LUSSEAU D,SCHNEIDER K,BOISSEAU O J,et al.The bottlenose dolphin community of Doubtful Sound features a large proportion of long-lasting associations[J].Behavioral Ecology and Sociobiology,2003,54(4):396-405.
[23]GUIMERA R,DANON L,DIAZ-GUILERA A,et al.Self-similar community structure in a network of human interactions[J].Physical Review E,2003,68(6):065103.
[24]LATORA V,MARCHIORI M.Efficient behavior of small- world networks[J].Physical Review Letters,2001,87(19):198701.
[25] LICHTENWALTER R N,LUSSIER J T,CHAWLA N V.New perspectives and methods in link prediction[C]//Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.ACM,2010:243-252.
[26]NEWMAN M E J.Assortative mixing in networks[J].Physical Review Letters,2002,89(20):208701.
[27]YANG J,ZHANG X D.Predicting missing links in complex networks based on common neighbors and distance[J].Scientific Reports,2016,6:38208.
[1] SONG Jie, LIANG Mei-yu, XUE Zhe, DU Jun-ping, KOU Fei-fei. Scientific Paper Heterogeneous Graph Node Representation Learning Method Based onUnsupervised Clustering Level [J]. Computer Science, 2022, 49(9): 64-69.
[2] HUANG Li, ZHU Yan, LI Chun-ping. Author’s Academic Behavior Prediction Based on Heterogeneous Network Representation Learning [J]. Computer Science, 2022, 49(9): 76-82.
[3] LI Yong, WU Jing-peng, ZHANG Zhong-ying, ZHANG Qiang. Link Prediction for Node Featureless Networks Based on Faster Attention Mechanism [J]. Computer Science, 2022, 49(4): 43-48.
[4] ZHAO Xue-lei, JI Xin-sheng, LIU Shu-xin, LI Ying-le, LI Hai-tao. Link Prediction Method for Directed Networks Based on Path Connection Strength [J]. Computer Science, 2022, 49(2): 216-222.
[5] LI Jia-wen, GUO Bing-hui, YANG Xiao-bo, ZHENG Zhi-ming. Disease Genes Recognition Based on Information Propagation [J]. Computer Science, 2022, 49(1): 264-270.
[6] WANG Xue-guang, ZHANG Ai-xin, DOU Bing-lin. Non-linear Load Capacity Model of Complex Networks [J]. Computer Science, 2021, 48(6): 282-287.
[7] HU Xin-tong, SHA Chao-feng, LIU Yan-jun. Post-processing Network Embedding Algorithm with Random Projection and Principal Component Analysis [J]. Computer Science, 2021, 48(5): 124-129.
[8] MA Yuan-yuan, HAN Hua, QU Qian-qian. Importance Evaluation Algorithm Based on Node Intimate Degree [J]. Computer Science, 2021, 48(5): 140-146.
[9] YIN Zi-qiao, GUO Bing-hui, MA Shuang-ge, MI Zhi-long, SUN Yi-fan, ZHENG Zhi-ming. Autonomous Structural Adjustment of Crowd Intelligence Network: Begin from Structure of Biological Regulatory Network [J]. Computer Science, 2021, 48(5): 184-189.
[10] CHEN Heng, WANG Wei-mei, LI Guan-yu, SHI Yi-ming. Knowledge Graph Completion Model Using Quaternion as Relational Rotation [J]. Computer Science, 2021, 48(5): 225-231.
[11] GONG Zhui-fei, WEI Chuan-jia. Link Prediction of Complex Network Based on Improved AdaBoost Algorithm [J]. Computer Science, 2021, 48(3): 158-162.
[12] LI Xin-chao, LI Pei-feng, ZHU Qiao-ming. Directed Network Representation Method Based on Hierarchical Structure Information [J]. Computer Science, 2021, 48(2): 100-104.
[13] GONG Zhui-fei, WEI Chuan-jia. Complex Network Link Prediction Method Based on Topology Similarity and XGBoost [J]. Computer Science, 2021, 48(12): 226-230.
[14] ZHAO Man-yu, YE Jun. Synchronization of Uncertain Complex Networks with Sampled-data and Input Saturation [J]. Computer Science, 2021, 48(11A): 481-484.
[15] ZHAO Man, ZHAO Jia-kun, LIU Jin-nuo. Link Prediction Algorithm Based on Ego Networks Structure and Network Representation Learning [J]. Computer Science, 2021, 48(11A): 211-217.
Full text



No Suggested Reading articles found!