一種基于節(jié)點間資源承載度的鏈路預測方法
doi: 10.11999/JEIT180553
-
國家數(shù)字交換系統(tǒng)工程技術(shù)研究中心 ??鄭州 ??450002
基金項目: 國家自然科學基金(61521003, 61803384)
A New Link Prediction Method for Complex Networks Based on Resources Carrying Capacity Between Nodes
-
National Digital Switching System Engineering and Technological R&D Center, Zhengzhou 450002, China
Funds: The National Natural Science Foundation of China (61521003, 61803384)
-
摘要: 鏈路預測旨在發(fā)現(xiàn)網(wǎng)絡的未知、缺失連接，具有重要的實際應用價值?；诰W(wǎng)絡結(jié)構(gòu)相似性的鏈路預測方法具有簡單且有效的特點，受到各領(lǐng)域?qū)W者的普遍關(guān)注。然而，許多現(xiàn)有方法在計算節(jié)點間存在連接可能性時，忽視了節(jié)點間資源承載能力的影響。鑒于此，該文提出一種基于節(jié)點間資源承載度的鏈路預測方法。該方法首先通過分析節(jié)點間資源傳輸過程，進而對節(jié)點間資源承載能力進行量化，提出資源承載度。然后，基于資源承載度對節(jié)點間連接可能性的影響進行分析，并提出相應的鏈路預測方法。9個真實網(wǎng)絡的實驗結(jié)果表明，相比其他鏈路預測方法，該方法在3個衡量標準下均具有較高的預測精度。
-
關(guān)鍵詞:
- 復雜網(wǎng)絡 /
- 鏈路預測 /
- 資源承載度 /
- 相似性
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 網(wǎng)絡數(shù)據(jù)特征參數(shù)
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結(jié)果對比
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結(jié)果對比
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 劉樹新, 季新生, 劉彩霞, 等. 一種信息傳播促進網(wǎng)絡增長的網(wǎng)絡演化模型[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 劉樹新, 季新生, 劉彩霞, 等. 局部拓撲信息耦合促進網(wǎng)絡演化[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)
計量
- 文章訪問數(shù): 1108
- HTML全文瀏覽量: 522
- PDF下載量: 54
- 被引次數(shù): 0
下載:
