Computer Science

Computer Science ›› 2019, Vol. 46 ›› Issue (1): 155-161.doi: 10.11896／j.issn.1002-137X.2019.01.024

• Network & Communication • Previous Articles     Next Articles

Link Prediction Method Based on Local Community and Nodes’ Relativity

YANG Xu-hua, YU Jia, ZHANG Duan   

  1. (College of Computer Science and Technology,Zhejiang University of Technology,Hangzhou 310023,China)
  • Received:2017-12-08 Online:2019-01-15 Published:2019-02-25

PDF (PC)

1055

Abstract: Link prediction methods based on the network topology information are effect ways to predict unknown or future network edges.In real applications,further extraction and analyzation of network topology is helpful to improve the precision of network link prediction.This paper proposed a new link prediction method based on local community and nodes’ relativity(HCRP).By expanding the first-level local communities to second-level ones,this method reveals more network topological information compared with first-level local communities.This method takes the shortest path of the second-level local community,coefficients of edge clustering and the impact of linking edge density on the simila-rity of two seed nodes into consideration when calculating relative coefficients between two seed nodes by using Pearson correlation coefficient,thus obtaining excellent prediction results of network linking edges.The algorithm was tested and compared with 11 well-known algorithms on 10 real network data sets.Results show that this algorithm has excellent performance of link prediction.

Key words: Link prediction, Pearson correlation coefficients, Second-level local community

CLC Number: 

  • TP391
[1]ZHAO J,MIAO L,YANG J,et al.Prediction of Links and Weights in Networks by Reliable Routes[J].Scientific Reports,2015,5:12261.<br /> [2]WANG W Q,ZHANG Q M,ZHOU T.Evaluating Network Models:A Likelihood Analysis[J].Epl,2011,98(2):28004.<br /> [3]ZHANG Q M,XU X K,ZHU Y X,et al.Measuring multiple evolution mechanisms of complex networks[J].Scientific Reports,2015,5(1):10350.<br /> [4]YU H,BRAUN P,YILDIRIM M A,et al.High-quality binary protein interaction map of the yeast interactome network[J].Science,2008,322(5898):104-110.<br /> [5]WANG P,XU B W,WU Y R,et al.Link prediction in social networks:the state-of-the-art[J].Science China,2015,58(1):011101.<br /> [6]HU W B,PENG C,LIANG H L,et al.Event Detection Method Based on Link Prediction for Social Network Evolution[J].Journal of Software,2015,26(9):2339-2355.(in Chinese)<br /> 胡文斌,彭超,梁欢乐,等.基于链路预测的社会网络事件检测方法[J].软件学报,2015,26(9):2339-2355.<br /> [7]ZENG A,XU X Q.Hybrid Collaborative Filtering Recommendation Algorithm Based on Friendships and Tag[J].Computer Science,2017,44(8):246-251.(in Chinese)<br /> 曾安,徐小强.基于好友关系和标签的混合协同过滤算法[J].计算机科学,2017,44(8):246-251.<br /> [8]ZHU B,XIA Y.An information-theoretic model for link prediction in complex networks[J].Scientific Reports,2015,5:13707.<br /> [9]ZHOU T,LÜ L,ZHANG Y C.Predicting missing links via local information[J].European Physical Journal B,2009,71(4):623-630.<br /> [10]ADAMIC L A,ADAR E.Friends and neighbors on the Web[J].Social Networks,2003,25(3):211-230.<br /> [11]FRANÇOIS L,HARRISON C.White.Structural equivalence of individuals in social networks[J].Social Networks,1977,1(1):67-98.<br /> [12]DILLON M.Introduction to modern information retrieval[J].Information Processing & Management,1983,19(6):402-403.<br /> [13]JACCARD P.Etude de la distribution florale dans une portion des Alpes et du Jura[J].Bulletin De La Societe Vaudoise Des Sciences Naturelles,1901,37(142):547-579.<br /> [14]SØRENSEN T J.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.<br /> [15]RAVASZ E.Hierarchical organization of modularity in metabolic networks[J].Science,2002,297(5586):1551-1555.<br /> [16]LEICHT E A,HOLME P,NEWMAN M E.Vertex similarity in networks[J].Physical Review E Statistical Nonlinear & Soft Matter Physics,2006,73(2 Pt 2):026120.<br /> [17]ZHANG Y Q,LU Y L,YANG G Z.Link Prediction of AS Level Internet Based on Association Rule of Frequent Closed Graphs[J].Computer Science,2016,43(s1):314-318.(in Chinese)<br /> 张岩庆,陆余良,杨国正.基于频繁闭图关联规则的AS级Internet链路预测方法[J].计算机科学,2016,43(s1):314-318.<br /> [18]KATZ L.A new status index derived from sociometric analysis[J].Psychometrika,1953,18(1):39-43.<br /> [19]LÜL,JIN C H,ZHOU T.Similarity index based on local paths for link prediction of complex networks[J].Physical Review E,2009,80(2):046122.<br /> [20]CANNISTRACI C V,ALANISLOBATO 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(4):1613.<br /> [21]DAMINELLI S,THOMAS J M,DURÁN C,et al.Common neighbours and the local-community-paradigm for link prediction in bipartite networks[J].New Journal of Physics,2015,17(11):1-8.<br /> [22]YANG X H,ZHANG H F,LING F,et al.Link prediction based on local community properties[J].International Journal of Mo-dern Physics B,2016,30(31):12.<br /> [23]LIAO H,ZENG A,ZHANG Y C.Predicting missing links via correlation between nodes[J].Physica A Statistical Mechanics &Its Applications,2015,436(1):216-223.<br /> [24]PABLO M.GLEISER,LEON D.Community structure in jazzZ[J].Advances in Complex Systems,2003,6(4):565-573.<br /> [25]BULDYREV S V.Robustness of interdependent networks under targeted attack[J].Physical Review E Statistical Nonlinear &Soft Matter Physics,2011,83(2):065101.<br /> [26]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 & Sociobiology,2003,54(4):396-405.<br /> [27]HAGE P,HARARY F.Structural models in anthropology[M].Cambridge:Cambridge University Press,1983:705-714.<br /> [28]SCHWIMMER E G.Exchange in the social structure of the Orokaiva[D].Columbia:University of British Columbia,1961.<br /> [29]KNUTH D E.The Stanford GraphBase:a platform for combinatorial computing[M].New York:Association for Computing Machinery,1993.<br /> [30]BURT R S.Social Contagion and Innovation:Cohesion Versus Structural Equivalence[J].American Journal of Sociology,1987,92(6):1287-1335.<br /> [31]ZACHARY W W.An Information Flow Model for Conflict and Fission in Small Groups[J].Journal of Anthropological Research,1977,33(4):452-473.<br /> [32]SUNDARESAN S R,FISCHHOFF I R,DUSHOFF J,et al. Network metrics reveal differences in social organization between two fission-fusion species,Grevy’s zebra and onager[J].Oecologia,2007,151(1):140-149.<br /> [33]ŠUBELJ L,BAJEC M.Robust network community detection using balanced propagation[J].European Physical Journal B,2011,81(3):353-362.<br /> [34]JÉRÔME K.KONECT:the Koblenz network collection[C]//International Conference on World Wide Web Companion.New York:ACM,2013:1343-1350.<br /> [35]HANLEY J A,MCNEIL B J.The meaning and use of the area under a receiver operating characteristic (ROC) curve[J].Radio-logy,1982,143(1):29-36.<br /> [36]HERLOCKER J L.Evaluating collaborative filtering recommender systems[J].Acm Transactions on Information Systems,2004,22(1):5-53.
[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] 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.
[6] 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.
[7] GONG Zhui-fei, WEI Chuan-jia. Link Prediction of Complex Network Based on Improved AdaBoost Algorithm [J]. Computer Science, 2021, 48(3): 158-162.
[8] 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.
[9] 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.
[10] HUANG Shou-meng. Heterogeneous Network Link Prediction Model Based on Supervised Learning [J]. Computer Science, 2021, 48(11A): 111-116.
[11] 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.
[12] WANG Wen-bo, LUO Heng-li. Complete Graph Face Clustering Based on Graph Convolution Network [J]. Computer Science, 2021, 48(11A): 275-277.
[13] WANG Hui, LE Zi-chun, GONG Xuan, WU Yu-kun, ZUO Hao. Review of Link Prediction Methods Based on Feature Classification [J]. Computer Science, 2020, 47(8): 302-312.
[14] FU Kun, QIU Qian, ZHAO Xiao-meng, GAO Jin-hui. Event Detection Method Based on Node Evolution Staged Optimization [J]. Computer Science, 2020, 47(5): 96-102.
[15] YUAN Rong, SONG Yu-rong, MENG Fan-rong. Link Prediction Method Based on Weighted Network Topology Weight [J]. Computer Science, 2020, 47(5): 265-270.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
Add:18# Honghu West Rd., Yubei ,Chongqing,China    Post Code: 401121
Tel: 023-63500828/023-67039612/023-67039623
E-mail: jsjkx12@163.com
Powered by Beijing Magtech Co., Ltd.