计算机科学 ›› 2020, Vol. 47 ›› Issue (5): 265-270.doi: 10.11896/jsjkx.190600031
袁榕1, 宋玉蓉1, 孟繁荣2
YUAN Rong1, SONG Yu-rong1, MENG Fan-rong2
摘要: 近年来,复杂网络中的链路预测问题受到越来越多的关注,链路预测的应用场景也越来越广泛,因此如何提高链路预测精度是一个重要问题。目前已提出了很多方法,其中加权相似性指标的预测方法取得了很好的效果。然而传统的加权网络链路预测方法仅考虑了链接的自然权重,忽略了链接的拓扑权重对预测精度的影响。因此,针对加权网络的链路预测,综合考虑网络中边的聚类和扩散特性并将其作为边的拓扑权重,提出了基于链接拓扑权重的WCD含权预测指标,包括WCD-CN,WCD-AA,WCD-RA和WCD-LP4个相似性指标。文中以Matlab为实验平台,在两个带权数据集(USAir,Bibble)和两个无权数据集(Pblogs,Dolphins)上进行实验,并以AUC作为评价指标。仿真结果表明,与基于自然权重的含权指标、基于簇系数的结构含权指标相比,所提算法具有更好的预测精度。
中图分类号:
[1]LV L Y.Link prediction on complex networks [J].Journal of University of Electronic Science and Technology of China,2010,39(5):651-661. [2]KIM J,KIM S,LEE C.Anticipating technological convergence:Link prediction using Wikipedia hyperlinks[J].Technovation,2019,79:25-34. [3]KOVÁCS I A,LUCK K,SPIROHN K,et al.Network-basedprediction of protein interactions[J].Nature Communications,2019,10(1):1240. [4]SUFIAN A,SULTANA F,DUTTA P.Data Load Balancing In Mobile Ad Hoc Network Using Fuzzy Logic(DBMF)[J].arXiv:1905.11627. [5]AHUJA R,SINGHAL V,BANGA A.Using Hierarchies in Online Social Networks to Determine Link Prediction[M]//Soft Computing and Signal Processing.Singapore:Springer,2019:67-76. [6]LIBEN-NOWELL D,KLEINBERG J.The link-prediction problem for social networks[J].Journal of the American Society for Information Science and Technology,2007,58(7):1019-1031. [7]YANG J,ZHANG X D.Predicting missing links in complex networks based on common neighbors and distance[J].Scientific Reports,2016,6:38208. [8]WU Z,LIN Y,WANG J,et al.Link prediction with node clustering coefficient[J].Physica A Statistical Mechanics & Its Applications,2016,452:1-8. [9]LIU Y,ZHAO C,WANG X,et al.The degree-related clustering coefficient and its application to link prediction[J].Physica A Statistical Mechanics & Its Applications,2016,454:24-33. [10]MURATA T,MORIYASU S.Link Prediction of Social Net-works Based on Weighted Proximity Measures[C].IEEE International Conference on Web Intelligence.IEEE,2007. [11]ZHU B,XIA Y.Link prediction in weighted networks:A weighted mutual information model[J].PloS One,2016,11(2):e0148265. [12]SETT N,SINGH S R,NANDI S.Influence of edge weight on node proximity based link prediction methods:An empirical analysis[J].Neurocomputing,2016,172:71-83. [13]HUANG Z.Link prediction based on graph topology:The predictive value of generalized clustering coefficient[J/OL].https://papers.ssrn.com/sol3/papers.cfm?abstract_id=1634014. [14]ZHU M,CAO T,JIANG X.Using clustering coefficient to construct weighted networks for supervised link prediction[J].Social Network Analysis and Mining,2014,4(1):215. [15]WANG L,HU K,TANG Y.Robustness of Link-Prediction Algorithm Based on Similarity and Application to Biological Networks [J].Current Bioinformatics,2014,9(5):1-7. [16]YAO Y B.Research on Link Prediction Method Based on Complex Network Topology[D].Lanzhou:Lanzhou University,2017. [17]YANG L,SONG Y R,LI Y W.Network structure optimization algorithm for information propagation considering edge clustering and diffusion characteristics[J].Journal of Physics,2018,67(19):56-67. [18]吕琳媛,周涛.链路预测[M].北京:高等教育出版社,2013:290. [19]LV L Y,ZHOU T.Link prediction in weighted networks:The role of weak ties[J].Epl,2010,89(1):18001. [20]MENG B,KE H,YI T.Link prediction based on a semi-localsimilarity index[J].Chinese Physics B,2011,20(12):128902. [21]LIU Y,TANG M,DO Y,et al.Accurate ranking of influential spreaders in networks based on dynamically asymmetric link weights[J].Physical Review E,2017,96(2):022323. [22]OPSAHL T.Why Anchorage is not(that) important:Binary ties and Sample selection [OL].http://wp.me/poFcY-Vw. [23]KUNEGIS J.Konect:the koblenz network collection[C]//Proceedings of the 22nd International Conference on World Wide Web.ACM,2013:1343-1350. [24]ADAMIC,LADA A,NATALIE G.The political blogosphereand the 2004 US election:divided they blog[C]//Proceedings of the 3rd International Workshop on Link Discovery.ACM,2005. [25]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 and Sociobiology,2003,54(4):396-405. [26]DU Z Y,CHEN H,SONG F.SNR Based Weighted-Consensus Algorithm for Cooperative Spectrum-Sensing [J].Journal of Data Acquisition & Processing,2013,28(2):184-189. |
[1] | 郑文萍, 刘美麟, 杨贵. 一种基于节点稳定性和邻域相似性的社区发现算法 Community Detection Algorithm Based on Node Stability and Neighbor Similarity 计算机科学, 2022, 49(9): 83-91. https://doi.org/10.11896/jsjkx.220400146 |
[2] | 何茜, 贺可太, 王金山, 林绅文, 杨菁林, 冯玉超. 比特币实体交易模式分析 Analysis of Bitcoin Entity Transaction Patterns 计算机科学, 2022, 49(6A): 502-507. https://doi.org/10.11896/jsjkx.210600178 |
[3] | 杨波, 李远彪. 数据科学与大数据技术课程体系的复杂网络分析 Complex Network Analysis on Curriculum System of Data Science and Big Data Technology 计算机科学, 2022, 49(6A): 680-685. https://doi.org/10.11896/jsjkx.210800123 |
[4] | 王本钰, 顾益军, 彭舒凡, 郑棣文. 融合动态距离和随机竞争学习的社区发现算法 Community Detection Algorithm Based on Dynamic Distance and Stochastic Competitive Learning 计算机科学, 2022, 49(5): 170-178. https://doi.org/10.11896/jsjkx.210300206 |
[5] | 李勇, 吴京鹏, 张钟颖, 张强. 融合快速注意力机制的节点无特征网络链路预测算法 Link Prediction for Node Featureless Networks Based on Faster Attention Mechanism 计算机科学, 2022, 49(4): 43-48. https://doi.org/10.11896/jsjkx.210800276 |
[6] | 陈世聪, 袁得嵛, 黄淑华, 杨明. 基于结构深度网络嵌入模型的节点标签分类算法 Node Label Classification Algorithm Based on Structural Depth Network Embedding Model 计算机科学, 2022, 49(3): 105-112. https://doi.org/10.11896/jsjkx.201000177 |
[7] | 赵学磊, 季新生, 刘树新, 李英乐, 李海涛. 基于路径连接强度的有向网络链路预测方法 Link Prediction Method for Directed Networks Based on Path Connection Strength 计算机科学, 2022, 49(2): 216-222. https://doi.org/10.11896/jsjkx.210100107 |
[8] | 李家文, 郭炳晖, 杨小博, 郑志明. 基于信息传播的致病基因识别研究 Disease Genes Recognition Based on Information Propagation 计算机科学, 2022, 49(1): 264-270. https://doi.org/10.11896/jsjkx.201100129 |
[9] | 穆俊芳, 郑文萍, 王杰, 梁吉业. 基于重连机制的复杂网络鲁棒性分析 Robustness Analysis of Complex Network Based on Rewiring Mechanism 计算机科学, 2021, 48(7): 130-136. https://doi.org/10.11896/jsjkx.201000108 |
[10] | 胡军, 王雨桐, 何欣蔚, 武晖栋, 李慧嘉. 基于复杂网络的全球航空网络结构分析与应用 Analysis and Application of Global Aviation Network Structure Based on Complex Network 计算机科学, 2021, 48(6A): 321-325. https://doi.org/10.11896/jsjkx.200900112 |
[11] | 王学光, 张爱新, 窦炳琳. 复杂网络上的非线性负载容量模型 Non-linear Load Capacity Model of Complex Networks 计算机科学, 2021, 48(6): 282-287. https://doi.org/10.11896/jsjkx.200700040 |
[12] | 马媛媛, 韩华, 瞿倩倩. 基于节点亲密度的重要性评估算法 Importance Evaluation Algorithm Based on Node Intimate Degree 计算机科学, 2021, 48(5): 140-146. https://doi.org/10.11896/jsjkx.200300184 |
[13] | 殷子樵, 郭炳晖, 马双鸽, 米志龙, 孙怡帆, 郑志明. 群智体系网络结构的自治调节:从生物调控网络结构谈起 Autonomous Structural Adjustment of Crowd Intelligence Network: Begin from Structure of Biological Regulatory Network 计算机科学, 2021, 48(5): 184-189. https://doi.org/10.11896/jsjkx.210200161 |
[14] | 刘胜久, 李天瑞, 谢鹏, 刘佳. 带权图的多重分形度量 Measure for Multi-fractals of Weighted Graphs 计算机科学, 2021, 48(3): 136-143. https://doi.org/10.11896/jsjkx.200700159 |
[15] | 龚追飞, 魏传佳. 基于改进AdaBoost算法的复杂网络链路预测 Link Prediction of Complex Network Based on Improved AdaBoost Algorithm 计算机科学, 2021, 48(3): 158-162. https://doi.org/10.11896/jsjkx.200600075 |
|