A New Link Prediction Method for Complex Networks Based on Resources Carrying Capacity Between Nodes
-
摘要: 链路预测旨在发现网络的未知、缺失连接，具有重要的实际应用价值。基于网络结构相似性的链路预测方法具有简单且有效的特点，受到各领域学者的普遍关注。然而，许多现有方法在计算节点间存在连接可能性时，忽视了节点间资源承载能力的影响。鉴于此，该文提出一种基于节点间资源承载度的链路预测方法。该方法首先通过分析节点间资源传输过程，进而对节点间资源承载能力进行量化，提出资源承载度。然后，基于资源承载度对节点间连接可能性的影响进行分析，并提出相应的链路预测方法。9个真实网络的实验结果表明，相比其他链路预测方法，该方法在3个衡量标准下均具有较高的预测精度。Abstract: Link prediction aims to discover the unknown or missing links of complex networks, which plays an important role in practical application. The similarity-based link prediction methods attract a lot of attention due to their briefness and effectiveness. However, most of similarity indices ignore the influence of resource carrying capacity between nodes when calculating the likelihood that a link exists between two endpoints. Because of the problem, a new link prediction method based on resources carrying capacity between nodes is proposed. Firstly, the resource carrying capacity is proposed to quantify the capability of resource carrying between nodes. Then, based on the resource carrying capacity, a new link prediction method is proposed by analyzing the impact of node connectivity. The experimental results of nine real networks show that compared with other link prediction methods, the proposed method can achieve higher prediction accuracy under three standard metrics.
-
Key words:
- Complex network /
- Link prediction /
- Resources carrying capacity /
- Similarity
-
表 1 网络数据特征参数
Network AIDS FWFB FWFW CE Email PB Hamster Figeys UC |V| 146 128 69 297 167 1222 1858 2239 1899 |E| 180 2075 880 2148 5784 16717 12534 6432 13838 C 0.052 0.335 0.552 0.308 0.541 0.361 0.0904 0.04 0.109 <k> 2.47 32.42 25.51 14.46 69.26 27.36 13.49 5.76 14.57 <d> 3.42 1.78 1.64 2.46 1.87 2.74 3.39 3.98 3.06 r –0.725 –0.112 –0.298 –0.225 –0.295 –0.221 –0.085 –0.331 –0.188 
下载: 导出CSV
表 2 AUC结果对比
Network AIDS FWFB FWEW CE Email PB Hamster Figeys UC CN 0.588 0.605 0.686 0.853 0.920 0.923 0.817 0.563 0.782 RA 0.601 0.609 0.701 0.873 0.928 0.927 0.822 0.568 0.786 AA 0.602 0.608 0.695 0.870 0.922 0.926 0.821 0.567 0.786 CAR 0.589 0.620 0.689 0.853 0.919 0.921 0.817 0.564 0.780 LP-0.001 0.831 0.622 0.707 0.871 0.922 0.935 0.936 0.889 0.891 LP-0.01 0.831 0.670 0.730 0.871 0.921 0.937 0.942 0.903 0.902 Katz-0.001 0.847 0.620 0.706 0.870 0.921 0.934 0.935 0.886 0.891 Katz-0.01 0.848 0.675 0.737 0.869 0.919 0.932 0.939 0.900 0.901 ACT 0.951 0.722 0.784 0.755 0.900 0.891 0.871 0.918 0.895 Cos+ 0.584 0.650 0.514 0.862 0.906 0.925 0.961 0.843 0.871 QN-18.5 0.936 0.918 0.927 0.896 0.935 0.946 0.977 0.945 0.928 QN-max 0.962 0.919 0.928 0.896 0.936 0.947 0.977 0.952 0.928
下载: 导出CSV
表 3 Pre结果对比
Network AIDS FWFB FWEW CE Email PB Hamster Figeys UC CN 0.014 0.086 0.161 0.131 0.708 0.417 0.015 0.011 0.022 RA 0.026 0.088 0.170 0.129 0.727 0.247 0.007 0.014 0.020 AA 0.026 0.090 0.164 0.138 0.720 0.380 0.010 0.012 0.022 CAR 0.014 0.088 0.150 0.131 0.703 0.478 0.030 0.026 0.052 LP-0.001 0.051 0.094 0.171 0.137 0.709 0.421 0.017 0.011 0.025 LP-0.01 0.051 0.123 0.198 0.136 0.701 0.455 0.052 0.012 0.034 Katz-0.001 0.053 0.093 0.171 0.137 0.709 0.422 0.017 0.011 0.025 Katz-0.01 0.053 0.134 0.202 0.136 0.696 0.454 0.071 0.012 0.037 ACT 0.000 0.000 0.126 0.000 0.000 0.000 0.000 0.000 0.000 Cos+ 0.000 0.039 0.000 0.081 0.620 0.333 0.017 0.008 0.011 QN-2.5 0.075 0.397 0.415 0.156 0.734 0.460 0.251 0.192 0.114 QN-max 0.078 0.651 0.547 0.251 0.927 0.580 0.906 0.210 0.165
下载: 导出CSV
-
SHANMUKHAPPA T, HO I W H, and TSE C K. Spatial analysis of bus transport networks using network theory[J]. Physica A: Statistical Mechanics and Its Applications, 2018, 502: 295–314. doi: 10.1016/j.physa.2018.02.111 CUI Ying, CAI Meng, DAI Yang, et al. A hybrid network-based method for the detection of disease-related genes[J]. Physica A: Statistical Mechanics and Its Applications, 2018, 492: 389–394. doi: 10.1016/j.physa.2017.10.026 VINCENOT C E. How new concepts become universal scientific approaches: insights from citation network analysis of agent-based complex systems science[J]. Proceedings of the Royal Society B: Biological Sciences, 2018, 285(1874): 20172360. doi: 10.1098/rspb.2017.2360 CHEN Zhenhao, WU Jiajing, XIA Yongxiang, et al. Robustness of interdependent power grids and communication networks: A complex network perspective[J]. IEEE Transactions on Circuits and Systems II: Express Briefs, 2018, 65(1): 115–119. doi: 10.1109/TCSII.2017.2705758 KIM J and HASTAK M. Social network analysis: characteristics of online social networks after a disaster[J]. International Journal of Information Management, 2018, 38(1): 86–96. doi: 10.1016/j.ijinfomgt.2017.08.003 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(1): D433–D437. doi: 10.1093/nar/gki005 SCELLATO S, NOULAS A, and MASCOLO C. Exploiting place features in link prediction on location-based social networks[C]. Proceedings of the 17th ACM Sigkdd International Conference on Knowledge Discovery and Data Mining, San Diego, California, USA, 2011: 1046–1054. doi: 10.1145/2020408.2020575. HOLLAND P W, LASKEY K B, and LEINHARDT S. Stochastic blockmodels: first steps[J]. Social Networks, 1983, 5(2): 109–137. doi: 10.1016/0378-8733(83)90021-7 SANZ-CRUZADO J, PEPA S M, and CASTELLS P. Structural novelty and diversity in link prediction[C]. Companion of the the Web Conference, 2018, Lyon, France, 2018: 1347–1351. LORRAIN F and WHITE H C. Structural equivalence of individuals in social networks[J]. The Journal of Mathematical Sociology, 1971, 1(1): 49–80. doi: 10.1080/0022250X.1971.9989788 ZHOU Tao, LÜ Linyuan, and ZHANG Yicheng. Predicting missing links via local information[J]. The European Physical Journal B, 2009, 71(4): 623–630. doi: 10.1140/epjb/e2009-00335-8 ADAMIC L A and ADAR E. Friends and neighbors on the web[J]. Social Networks, 2003, 25(3): 211–230. doi: 10.1016/S0378-8733(03)00009-1 CANNISTRACI C V, ALANIS-LOBATO G, and RAVASI T. From link-prediction in brain connectomes and protein interactomes to the local-community-paradigm in complex networks[J]. Scientific Reports, 2013(3): 1613. doi: 10.1038/srep01613 LIU Shuxin, JI Xinsheng, LIU Caixia, et al. Extended resource allocation index for link prediction of complex network[J]. Physica A: Statistical Mechanics and Its Applications, 2017, 479: 174–183. doi: 10.1016/j.physa.2017.02.078 KATZ L. A new status index derived from sociometric analysis[J]. Psychometrika, 1953, 18(1): 39–43. doi: 10.1007/BF02289026 KLEIN D J and RANDIĆ M. Resistance distance[J]. Journal of Mathematical Chemistry, 1993, 12(1): 81–95. doi: 10.1007/BF01164627 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. doi: 10.1109/tkde.2007.46 LÜ Linyuan, JIN Cihang, and ZHOU Tao. Similarity index based on local paths for link prediction of complex networks[J]. Physical Review E, 2009, 80(4): 046122. doi: 10.1103/PhysRevE.80.046122 YANG Yujie, ZHANG Jianhua, ZHU Xuzhen, et al. Link prediction via significant influence[J]. Physica A: Statistical Mechanics and Its Applications, 2018, 492: 1523–1530. doi: 10.1016/j.physa.2017.11.078 刘树新, 季新生, 刘彩霞, 等. 一种信息传播促进网络增长的网络演化模型[J]. 物理学报, 2014, 63(15): 158902. doi: 10.7498/aps.63.158902LIU Shuxin, JI Xinsheng, LIU Caixia, et al. A complex network evolution model for network growth promoted by information transmission[J]. Acta Physica Sinica, 2014, 63(15): 158902. doi: 10.7498/aps.63.158902 WANG Xingyuan, ZHOU Wenjie, LI Rui, et al. Improving robustness of interdependent networks by a new coupling strategy[J]. Physica A: Statistical Mechanics and Its Applications, 2018, 492: 1075–1080. doi: 10.1016/j.physa.2017.11.037 WANG Xingyuan, CAO Jianye, LI Rui, et al. A preferential attachment strategy for connectivity link addition strategy in improving the robustness of interdependent networks[J]. Physica A: Statistical Mechanics and Its Applications, 2017, 483: 412–422. doi: 10.1016/j.physa.2017.04.128 WANG Xingyuan, CAO Jianye, and QIN Xiaomeng. Study of robustness in functionally identical coupled networks against cascading failures[J]. PLoS One, 2016, 11(8): e0160545. doi: 10.1371/journal.pone.0160545 DEWHURST D R, DANFORTH C M, and DODDS P S. Continuum rich-get-richer processes: mean field analysis with an application to firm size[J]. Physical Review E, 2018, 97(6): 062317. doi: 10.1103/PhysRevE.97.062317 ZENG Guoping and ZENG E. On the three-way equivalence of AUC in credit scoring with tied scores[J]. Communications in Statistics-Theory and Methods, 2017, 46(17): 1–16. doi: 10.1080/03610926.2018.1435814 WU Zhihao, LIN Youfang, ZHAO Yiji, et al. Improving local clustering based top-L link prediction methods via asymmetric link clustering information[J]. Physica A: Statistical Mechanics and Its Applications, 2018, 492: 1859–1874. doi: 10.1016/j.physa.2017.11.103 ZENG Xiangxiang, LIU Li, LÜ Linyuan, et al. Prediction of potential disease-associated microRNAs using structural perturbation method[J]. Bioinformatics, 2018, 34(14): 2425–2432. doi: 10.1093/bioinformatics/bty112 GOPAL S. The evolving social geography of blogs[M]. MILLER H J. Societies and Cities in the Age of Instant Access. Dordrecht, Springer, 2007: 275–293. doi: 10.1007/1-4020-5427-0_18. MICHALSKI R, PALUS S, and KAZIENKO P. Matching organizational structure and social network extracted from email communication[C]. Proceedings of the 14th International Conference on Business Information Systems, Poznań, Poland, 2011. ULANOWICZ R E and DEANGELIS D L. Network analysis of trophic dynamics in south Florida ecosystems[J]. US Geological Survey Program on the South Florida Ecosystem, 2005, 114: 45–47. (未找到本条文献信息, 请核对 WATTS D J and STROGATZ S H. Collective dynamics of ‘small-world’ networks[J]. Nature, 1998, 393(6684): 440–442. doi: 10.1038/30918 MICHALSKI R, PALUS S, and KAZIENKO P. Matching organizational structure and social network extracted from email communication[C]. Proceedings of the 14th International Conference on Business Information Systems, Poznań, Poland, 2011: 197–206. doi: 10.1007/978-3-642-21863-7_17. ADAMIC L A and GLANCE N. The political blogosphere and the 2004 U.S. election: divided they blog[C]. Proceedings of the 3rd International Workshop on Link Discovery, Chicago, USA, 2005: 36–43. doi: 10.1145/1134271.1134277. LÜ Linyuan, PAN Liming, ZHOU Tao, et al. Toward link predictability of complex networks[J]. Proceedings of the National Academy of Sciences of the United States of America, 2015, 112(8): 2325–2330. doi: 10.1073/pnas.1424644112 EWING R M, CHU P, ELISMA F, et al. Large-scale mapping of human protein-protein interactions by mass spectrometry[J]. Molecular Systems Biology, 2007, 3: 89. doi: 10.1038/msb4100134 OPSAHL T and PANZARASA P. Clustering in weighted networks[J]. Social Networks, 2009, 31(2): 155–163. doi: 10.1016/j.socnet.2009.02.002 刘树新, 季新生, 刘彩霞, 等. 局部拓扑信息耦合促进网络演化[J]. 电子与信息学报, 2016, 38(9): 2180–2187. doi: 10.11999/JEIT151338LIU Shuxin, JI Xinsheng, LIU Caixia, et al. Information coupling of local topology promoting the network evolution[J]. Journal of Electronics &Information Technology, 2016, 38(9): 2180–2187. doi: 10.11999/JEIT151338 -
下载:
图(7) / 表(3)
计量
- 文章访问数: 1044
- HTML全文浏览量: 469
- PDF下载量: 54
- 被引次数: 0
