计算机科学 ›› 2020, Vol. 47 ›› Issue (5): 265-270.doi: 10.11896/jsjkx.190600031

• 计算机网络 • 上一篇    下一篇

一种基于加权网络拓扑权重的链路预测方法

袁榕1, 宋玉蓉1, 孟繁荣2   

  1. 1 南京邮电大学自动化学院人工智能学院 南京210003
    2 南京邮电大学计算机学院软件学院网络空间安全学院 南京210003
  • 收稿日期:2019-06-06 出版日期:2020-05-15 发布日期:2020-05-19
  • 通讯作者: 宋玉蓉(songyr@njupt.edu.cn)
  • 作者简介:15738774278@163.com
  • 基金资助:
    国家自然科学基金(61672298,61873326,61373136,61802155);江苏高校哲学社会科学研究重点项目(2018SJZDI142);教育部人文社会科学研究规划基金(17YJAZH071)

Link Prediction Method Based on Weighted Network Topology Weight

YUAN Rong1, SONG Yu-rong1, MENG Fan-rong2   

  1. 1 College of Automation & College of Artificial Intelligence,Nanjing University of Posts and Telecommunications,Nanjing 210003,China
    2 School of Computer,Network Space Security,Nanjing University of Posts and Telecommunications,Nanjing 210003,China
  • Received:2019-06-06 Online:2020-05-15 Published:2020-05-19
  • About author:YUAN Rong,born in 1995,postgradua-te.Her main research interests include complex network and link prediction.
    SONG Yu-Rong,born in 1971,Ph.D,professor,is a member of China Computer Federation.Her main research interests include network information dissemination and its control.
  • Supported by:
    This work was supported by the National Natural Science Foundation of China(61672298,61873326,61373136,61802155),Philosophy SocialScience Research Key Project Fund of Jiangsu University(G2018SJZDI142) and Social Sciences of Ministry of Education of China(17YJAZH071).

摘要: 近年来,复杂网络中的链路预测问题受到越来越多的关注,链路预测的应用场景也越来越广泛,因此如何提高链路预测精度是一个重要问题。目前已提出了很多方法,其中加权相似性指标的预测方法取得了很好的效果。然而传统的加权网络链路预测方法仅考虑了链接的自然权重,忽略了链接的拓扑权重对预测精度的影响。因此,针对加权网络的链路预测,综合考虑网络中边的聚类和扩散特性并将其作为边的拓扑权重,提出了基于链接拓扑权重的WCD含权预测指标,包括WCD-CN,WCD-AA,WCD-RA和WCD-LP4个相似性指标。文中以Matlab为实验平台,在两个带权数据集(USAir,Bibble)和两个无权数据集(Pblogs,Dolphins)上进行实验,并以AUC作为评价指标。仿真结果表明,与基于自然权重的含权指标、基于簇系数的结构含权指标相比,所提算法具有更好的预测精度。

关键词: 复杂网络, 结构权重, 链路预测, 拓扑结构, 相似性指标

Abstract: In recent years,with more and more attention drawning to link prediction in complex networks,and with the application of link prediction becoming increasingly extensive,a crucial question is raised on how to improve the accuracy of link prediction.Many proposals are made,among which the weighted similarity indices have already achieved a promising result.However,the traditional weighted network link prediction only considers the natural weight of the link neglects the influence of the topologi-cal weights on prediction accuracy.Therefore,aiming at the weighted networks,this paper takes the clustering and diffusion characteristics of edges into consideration and regard them as the topological weights of edges,and consequently recommended four similarity indices based on the topology weight of links,namely WCD-CN,WCD-AA,WCD-RA,and WCD-LP.This paper takes Matlab as the experimental platform and carries out experiments on two weighted datasets(USAir,Bibble) and two weightless datasets(Pblogs and Dolphins),in which AUC is used as the evaluation index.The results of the simulation indicate that compared with two weighted indices,which are based on natural weight and cluster coefficient respectively,the proposed algorithm has higher accuracy in prediction.

Key words: Complex network, Link prediction, Similarity index, Structural weight, Topological structure

中图分类号: 

  • TP393.02
[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
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!