基于局部社团和节点相关性的链路预测算法

doi:10.11896／j.issn.1002-137X.2019.01.024

摘要/Abstract

摘要： 基于网络拓扑结构信息的链路预测算法是预测网络未知连边或未来连边的有效方法。在实际应用中,通过进一步提取网络结构信息可以提高网络链路预测结果的精度。文中提出了一种基于局部社团和节点相关性的链路预测算法(HCRP)。该算法把种子节点对的一阶局部社团扩展到二阶局部社团,获得了比一阶局部社团更多的网络结构信息;在用皮尔逊系数计算两个种子节点的相关系数时,该算法也考虑了二阶局部社团的最短路径、边聚类系数和连边密度对两个种子节点相似度的影响,获得了良好的预测网络连边的效果。实验采用了10个真实网络的数据,并对比了HCRP算法和11种知名算法,数值实验结果表明所提算法具有优良的链路预测性能。

关键词: 二阶局部社团, 链路预测, 皮尔逊系数

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

中图分类号:

TP391

杨旭华, 俞佳, 张端. 基于局部社团和节点相关性的链路预测算法[J]. 计算机科学, 2019, 46(1): 155-161. https://doi.org/10.11896／j.issn.1002-137X.2019.01.024

YANG Xu-hua, YU Jia, ZHANG Duan. Link Prediction Method Based on Local Community and Nodes’ Relativity[J]. Computer Science, 2019, 46(1): 155-161. https://doi.org/10.11896／j.issn.1002-137X.2019.01.024

参考文献

[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. [2]WANG W Q,ZHANG Q M,ZHOU T.Evaluating Network Models:A Likelihood Analysis[J].Epl,2011,98(2):28004. [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. [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. [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. [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) 胡文斌,彭超,梁欢乐,等.基于链路预测的社会网络事件检测方法[J].软件学报,2015,26(9):2339-2355. [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) 曾安,徐小强.基于好友关系和标签的混合协同过滤算法[J].计算机科学,2017,44(8):246-251. [8]ZHU B,XIA Y.An information-theoretic model for link prediction in complex networks[J].Scientific Reports,2015,5:13707. [9]ZHOU T,LÜ L,ZHANG Y C.Predicting missing links via local information[J].European Physical Journal B,2009,71(4):623-630. [10]ADAMIC L A,ADAR E.Friends and neighbors on the Web[J].Social Networks,2003,25(3):211-230. [11]FRANÇOIS L,HARRISON C.White.Structural equivalence of individuals in social networks[J].Social Networks,1977,1(1):67-98. [12]DILLON M.Introduction to modern information retrieval[J].Information Processing & Management,1983,19(6):402-403. [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. [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. [15]RAVASZ E.Hierarchical organization of modularity in metabolic networks[J].Science,2002,297(5586):1551-1555. [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. [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) 张岩庆,陆余良,杨国正.基于频繁闭图关联规则的AS级Internet链路预测方法[J].计算机科学,2016,43(s1):314-318. [18]KATZ L.A new status index derived from sociometric analysis[J].Psychometrika,1953,18(1):39-43. [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. [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. [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. [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. [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. [24]PABLO M.GLEISER,LEON D.Community structure in jazzZ[J].Advances in Complex Systems,2003,6(4):565-573. [25]BULDYREV S V.Robustness of interdependent networks under targeted attack[J].Physical Review E Statistical Nonlinear &Soft Matter Physics,2011,83(2):065101. [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. [27]HAGE P,HARARY F.Structural models in anthropology[M].Cambridge:Cambridge University Press,1983:705-714. [28]SCHWIMMER E G.Exchange in the social structure of the Orokaiva[D].Columbia:University of British Columbia,1961. [29]KNUTH D E.The Stanford GraphBase:a platform for combinatorial computing[M].New York:Association for Computing Machinery,1993. [30]BURT R S.Social Contagion and Innovation:Cohesion Versus Structural Equivalence[J].American Journal of Sociology,1987,92(6):1287-1335. [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. [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. [33]ŠUBELJ L,BAJEC M.Robust network community detection using balanced propagation[J].European Physical Journal B,2011,81(3):353-362. [34]JÉRÔME K.KONECT:the Koblenz network collection[C]//International Conference on World Wide Web Companion.New York:ACM,2013:1343-1350. [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. [36]HERLOCKER J L.Evaluating collaborative filtering recommender systems[J].Acm Transactions on Information Systems,2004,22(1):5-53.

相关文章 15

[1]	李勇, 吴京鹏, 张钟颖, 张强. 融合快速注意力机制的节点无特征网络链路预测算法 Link Prediction for Node Featureless Networks Based on Faster Attention Mechanism 计算机科学, 2022, 49(4): 43-48. https://doi.org/10.11896/jsjkx.210800276
[2]	赵学磊, 季新生, 刘树新, 李英乐, 李海涛. 基于路径连接强度的有向网络链路预测方法 Link Prediction Method for Directed Networks Based on Path Connection Strength 计算机科学, 2022, 49(2): 216-222. https://doi.org/10.11896/jsjkx.210100107
[3]	骆菁菁, 唐卫贞, 丁继婷. 基于皮尔逊系数的管制仿真训练数据独立化与因子分析下的数据可视化研究 Research of ATC Simulator Training Values Independence Based on Pearson Correlation Coefficient and Study of Data Visualization Based on Factor Analysis 计算机科学, 2021, 48(6A): 623-628. https://doi.org/10.11896/jsjkx.210200021
[4]	龚追飞, 魏传佳. 基于改进AdaBoost算法的复杂网络链路预测 Link Prediction of Complex Network Based on Improved AdaBoost Algorithm 计算机科学, 2021, 48(3): 158-162. https://doi.org/10.11896/jsjkx.200600075
[5]	李鑫超, 李培峰, 朱巧明. 一种基于层级信息优化的有向网络表示学习方法 Directed Network Representation Method Based on Hierarchical Structure Information 计算机科学, 2021, 48(2): 100-104. https://doi.org/10.11896/jsjkx.191200033
[6]	龚追飞, 魏传佳. 基于拓扑相似和XGBoost的复杂网络链路预测方法 Complex Network Link Prediction Method Based on Topology Similarity and XGBoost 计算机科学, 2021, 48(12): 226-230. https://doi.org/10.11896/jsjkx.200800026
[7]	赵曼, 赵加坤, 刘金诺. 基于自我中心网络结构特征和网络表示学习的链路预测算法 Link Prediction Algorithm Based on Ego Networks Structure and Network Representation Learning 计算机科学, 2021, 48(11A): 211-217. https://doi.org/10.11896/jsjkx.201200231
[8]	黄寿孟. 一种基于监督学习的异构网链路预测模型 Heterogeneous Network Link Prediction Model Based on Supervised Learning 计算机科学, 2021, 48(11A): 111-116. https://doi.org/10.11896/jsjkx.210300030
[9]	王慧, 乐孜纯, 龚轩, 武玉坤, 左浩. 基于特征分类的链路预测方法综述 Review of Link Prediction Methods Based on Feature Classification 计算机科学, 2020, 47(8): 302-312. https://doi.org/10.11896/jsjkx.190700136
[10]	富坤, 仇倩, 赵晓梦, 高金辉. 基于节点演化分阶段优化的事件检测方法 Event Detection Method Based on Node Evolution Staged Optimization 计算机科学, 2020, 47(5): 96-102. https://doi.org/10.11896/jsjkx.190400072
[11]	袁榕, 宋玉蓉, 孟繁荣. 一种基于加权网络拓扑权重的链路预测方法 Link Prediction Method Based on Weighted Network Topology Weight 计算机科学, 2020, 47(5): 265-270. https://doi.org/10.11896/jsjkx.190600031
[12]	李鑫超, 李培峰, 朱巧明. 一种基于改进向量投影距离的知识图谱表示方法 Knowledge Graph Representation Based on Improved Vector Projection Distance 计算机科学, 2020, 47(4): 189-193. https://doi.org/10.11896/jsjkx.190300024
[13]	马扬, 程光权, 梁星星, 李妍, 杨雨灵, 刘忠. 有向加权网络中的改进SDNE算法 Improved SDNE in Weighted Directed Network 计算机科学, 2020, 47(4): 233-237. https://doi.org/10.11896/jsjkx.190600151
[14]	王慧, 乐孜纯, 龚轩, 左浩, 武玉坤. 基于特征学习的链路预测模型TNTlink TNTlink Prediction Model Based on Feature Learning 计算机科学, 2020, 47(12): 245-251. https://doi.org/10.11896/jsjkx.190700020
[15]	吴勇, 王斌君, 翟一鸣, 仝鑫. 共引增强有向网络嵌入研究 Study on Co-citation Enhancing Directed Network Embedding 计算机科学, 2020, 47(12): 279-284. https://doi.org/10.11896/jsjkx.191000199

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed