基于资源传输节点拓扑紧密性的链路预测方法

doi:10.19678/j.issn.1000-3428.0056092

摘要/Abstract

摘要： 针对现有基于网络拓扑结构的局部相似性RA指标未考虑传输节点拓扑紧密性的问题，提出一种节点拓扑紧密性指标及链路预测方法。根据多跳节点资源传输情况确定重要传输节点，基于传输节点周围拓扑集聚程度对拓扑紧密性进行量化，并根据传输节点紧密性对共同邻居传输资源量的影响刻画节点间相似性。实验结果表明，该方法具有较高的普适性，所提相似性指标适合于Precision标准，与CN、AA和CAR等现有相似性指标相比，具有较高的预测精度。

关键词: 复杂网络, 链路预测, 资源传输节点, 拓扑紧密性, 传输资源

Abstract: To address the problem that the existing local similarity RA index based on network topology does not consider the topological closeness of transmission nodes,this paper proposes a node topology closeness index and link prediction method.The important transmission nodes are determined according to the resource transmission details of multi-hop nodes,and then the topological closeness is quantified based on the analysis of the topological clustering degree around the transmission nodes.Finally,the similarity between nodes is described by using the impact of the closeness of the transmission nodes on the transmission resources of the common neighbors.Experimental results show that this method has high universality,and the proposed similarity index is suitable for the Precision standard,and has higher prediction accuracy compared with the existing similarity indexes such as CN,AA and CAR.

Key words: complex network, link prediction, resource transmission nodes, topological tightness, transmission resource

中图分类号:

TP18

李英乐, 何赞园, 王凯, 许明艳. 基于资源传输节点拓扑紧密性的链路预测方法[J]. 计算机工程, 2021, 47(1): 50-57.

LI Yingle, HE Zanyuan, WANG Kai, XU Mingyan. Link Prediction Method Based on Topological Tightness of Resource Transmission Nodes[J]. Computer Engineering, 2021, 47(1): 50-57.

http://www.ecice06.com/CN/Y2021/V47/I1/50

图/表 10

20210125163146

20210125163149

20210125163153

20210125163156

20210125163159

20210125163202

20210125163206

20210125163208

20210125163211

20210125163214

参考文献

[1] LYU L,ZHOU T.Link prediction in complex networks:a survey[J].Physica A:Statistical Mechanics and Its Applications,2011,390(6):1150-1170.
[2] LIU Hongkun,LÜ Linyuan,ZHOU Tao.Uncovering the network evolution mechanism by link prediction[J].Science in China:Physica,Mechanica & Astronomica,2011,41(7):816-823.(in Chinese)刘宏鲲,吕琳媛,周涛.利用链路预测推断网络演化机制[J].中国科学:物理学力学天文学,2011,41(7):816-823.
[3] 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.
[4] YUAN Weiwei,HE Kangya,GUAN Danghai,et al.Graph kernel based link prediction for signed social networks[J].Information Fusion,2019,46:1-10.
[5] LORRAIN F,WHITE H C.Structural equivalence of individuals in social networks[J].The Journal of Mathematical Sociology,1971,1(1):49-80.
[6] SALTON G,MCGILL M J.Introduction to modern information retrieval[M].Auckland,New Zealand:McGraw-Hill,1983.
[7] ADAMIC L A,ADAR E.Friends and neighbors on the Web[J].Social Networks,2003,25(3):211-230.
[8] ZHOU Tao,LÜ Linyuan,ZHANG Yicheng.Predicting missing links via local information[J].The European Physical Journal B,2009,71(4):623-630.
[9] FOUSS F,PIROTTE A,RENDERS J M,et al.Randomwalk 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.
[10] KLEIN D J,RANDI M.Resistance distance[J].Journal of Mathematical Chemistry,1993,12(1):81-95.
[11] BRIN S,PAGE L.The anatomy of a large-scale hypertextual Web search engine[J].Computer Networks and ISDN Systems,1998,30(1):107-117.
[12] LÜ Linyuan,JIN Cihang,ZHOU Tao.Similarity index based on local paths for link prediction of complex networks[J].Physical Review E,2009,80(4):46-62.
[13] LEICHT E A,HILME P,NEWMAN M E J.Vertex similarity in networks[J].Physical Review E,2006,73(2):61-80.
[14] KATZ L.A new status index derived from sociometric analysis[J].Psychometrika,1953,18(1):39-43.
[15] TAN Fei,XIA Yongxiang,ZHU Boyao.Link prediction in complex networks:a mutual information perspective[J].PloS One,2014,9(9):107-126.
[16] WU Zhihao,LIN Youfang,WANG Jing,et al.Link prediction with node clustering coefficient[J].Physica A:Statistical Mechanics and Its Applications,2016,452(15):1-8.
[17] LIU Shuxin,JI Xinsheng,LIU Caixia,et al.Similarity index for link prediction based on the clustering coefficient of nodes[J].Journal of Information Engineering University,2017,18(6):698-702.(in Chinese)刘树新,季新生,刘彩霞,等.一种基于节点集聚程度的相似性链路预测方法[J].信息工程大学学报,2017,18(6):698-702.
[18] DING Dazhao,CHEN Yunjie,JIN Yanqing,et al.Link prediction method for complex network based on closeness between nodes[J].Journal of Computer Applications,2017,37(8):2129-2132,2138.(in Chinese)丁大钊,陈云杰,靳彦青,等.基于拓扑连接紧密度的相似性链路预测算法[J].计算机应用,2017,37(8):2129-2132,2138.
[19] LIU Shuxin,JI Xisheng,LIU Caixia,et al.Extended resource allocation index for link prediction of complex network[J].Physica A:Statistical Mechanics and Its Applications,2017,479(2):174-183.
[20] WANG Kai,LI Xing,LAN Julong,et al.A new link prediction method for complex networks based on topological effectiveness of resource transmission paths[J].Journal of Electronics and Information Technology 2020,42(3):653-660. 王凯,李星,兰巨龙,等.一种基于资源传输路径拓扑有效性的链路预测方法[J].电子与信息学报,2020,42(3):653-660.
[21] WANG Kai,LIU Shuxin,CHEN Hongchang,et al.A new link prediction method for complex networks based on resources carrying capacity between nodes[J].Journal of Electronics and Information Technology,2019,41(5):1225-1234.(in Chinese)王凯,刘树新,陈鸿昶,等.一种基于节点间资源承载度的链路预测方法[J].电子与信息学报,2019,41(5):1225-1234.
[22] 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].Scientific Reports,2013,4(3):16-23.
[23] IRIBARREN J L,MORO E.Impact of human activity patterns on the dynamics of information diffusion[J].Physical Review Letters,2009,103(3):38-47.
[24] WENG L,RATKIEWICZ J,PERRA N,et al.The role of information diffusion in the evolution of social networks[C]//Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York,USA:ACM Press,2013:356-364.
[25] GRINDROD P,HIGHAM D J.Evolving graphs:dynamical models,inverse problems and propagation[J].Proceedings of the Royal Society A:Mathematical,Physical and Engineering Sciences,2009,466(2115):753-770.
[26] VAN ECK P S,JAGER W,LEEFLANG P S H.Opinion leaders' role in innovation diffusion:a simulation study[J].Journal of Product Innovation Management,2011,28(2):187-203.
[27] GLEISER P M,DANON L.Community structure in jazz[J].Advances in Complex Systems,2003,6(4):565-573.
[28] ULANOWICZ R E,DEANGELIS D L.Network analysis of trophic dynamics in south florida ecosystems[J].Florida Bay Ecosystem,1998,55:20688-20738.
[29] BATAGELJ V,MRVAR A.Pajek-program for large network analysis[J].Connections,1998,21(2):47-57.
[30] WATTS D J,STROGATZ S H.Collective dynamics of ‘small-world’ networks[J].Nature,1998,393(6684):440-442.
[31] GUIMERA R,DANOD L,DIAZ-GUILEAR A,et al.Self-similar community structure in a network of human interactions[J].Physical Review E,2003,68(6):65-73.
[32] GUIMERA R,AMARAL L A N.Functional cartography of complex metabolic networks[J].Nature,2005,433(7028):895-906.
[33] ISELLA L,STEHLé J,BARRAT A,et al.What's in a crowd?analysis of face-to-face behavioral networks[J].Journal of Theoretical Biology,2011,271(1):166-180.
[34] TAKAHATA Y.Diachronic changes in the dominance relations of adult female Japanese monkeys of the Arashiyama B group[M].Albany,USA:State University of New York Press,1991.

选择文件类型/文献管理软件名称

选择包含的内容