Computer Science ›› 2020, Vol. 47 ›› Issue (5): 265-270.doi: 10.11896/jsjkx.190600031

• Computer Network • Previous Articles     Next Articles

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).

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, Topological structure, Link prediction, Similarity index, Structural weight

CLC Number: 

  • 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] YANG Chao, LIU Zhi. Study on Complex Network Cascading Failure Based on Totally Asymmetric Simple Exclusion Process Model [J]. Computer Science, 2020, 47(9): 265-269.
[2] ZHANG Meng-yue, HU Jun, YAN Guan, LI Hui-jia. Analysis of China’s Patent Application Concern Based on Visibility Graph Network [J]. Computer Science, 2020, 47(8): 189-194.
[3] ZHANG Qing-qi, LIU Man-dan. Multi-objective Five-elements Cycle Optimization Algorithm for Complex Network Community Discovery [J]. Computer Science, 2020, 47(8): 284-290.
[4] WANG Hui, LE Zi-chun, GONG Xuan, WU Yu-kun, ZUO Hao. Review of Link Prediction Methods Based on Feature Classification [J]. Computer Science, 2020, 47(8): 302-312.
[5] DONG Ming-gang, GONG Jia-ming and JING Chao. Multi-obJective Evolutionary Algorithm Based on Community Detection Spectral Clustering [J]. Computer Science, 2020, 47(6A): 461-466.
[6] FU Kun, QIU Qian, ZHAO Xiao-meng, GAO Jin-hui. Event Detection Method Based on Node Evolution Staged Optimization [J]. Computer Science, 2020, 47(5): 96-102.
[7] LI Xin-chao, LI Pei-feng, ZHU Qiao-ming. Knowledge Graph Representation Based on Improved Vector Projection Distance [J]. Computer Science, 2020, 47(4): 189-193.
[8] MA Yang, CHENG Guang-quan, LIANG Xing-xing, LI Yan, YANG Yu-ling, LIU Zhong. Improved SDNE in Weighted Directed Network [J]. Computer Science, 2020, 47(4): 233-237.
[9] LIU Miao-miao,HU Qing-cui,GUO Jing-feng,CHEN Jing. Survey of Link Prediction Algorithms in Signed Networks [J]. Computer Science, 2020, 47(2): 21-30.
[10] ZHANG Hu, ZHOU Jing-jing, GAO Hai-hui, WANG Xin. Network Representation Learning Method on Fusing Node Structure and Content [J]. Computer Science, 2020, 47(12): 119-124.
[11] WANG Hui, LE Zi-chun, GONG Xuan, ZUO Hao, WU Yu-kun. TNTlink Prediction Model Based on Feature Learning [J]. Computer Science, 2020, 47(12): 245-251.
[12] WU Yong, WANG Bin-jun, ZHAI Yi-ming, TONG Xin. Study on Co-citation Enhancing Directed Network Embedding [J]. Computer Science, 2020, 47(12): 279-284.
[13] LI Zhong-wen, DING Ye, HUA Zhong-yun, LI Jun-yi, LIAO Qing. Knowledge Graph Completion Model Based on Triplet Importance Integration [J]. Computer Science, 2020, 47(11): 231-236.
[14] RUAN Zi-rui,RUAN Zhong-yuan,SHEN Guo-jiang. Study of TASEP Model Based on Road Networks [J]. Computer Science, 2020, 47(1): 265-269.
[15] ZHAO Lei, ZHOU Jin-he. ICN Energy Efficiency Optimization Strategy Based on Content Field of Complex Networks [J]. Computer Science, 2019, 46(9): 137-142.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] LEI Li-hui and WANG Jing. Parallelization of LTL Model Checking Based on Possibility Measure[J]. Computer Science, 2018, 45(4): 71 -75 .
[2] SUN Qi, JIN Yan, HE Kun and XU Ling-xuan. Hybrid Evolutionary Algorithm for Solving Mixed Capacitated General Routing Problem[J]. Computer Science, 2018, 45(4): 76 -82 .
[3] ZHANG Jia-nan and XIAO Ming-yu. Approximation Algorithm for Weighted Mixed Domination Problem[J]. Computer Science, 2018, 45(4): 83 -88 .
[4] WU Jian-hui, HUANG Zhong-xiang, LI Wu, WU Jian-hui, PENG Xin and ZHANG Sheng. Robustness Optimization of Sequence Decision in Urban Road Construction[J]. Computer Science, 2018, 45(4): 89 -93 .
[5] SHI Wen-jun, WU Ji-gang and LUO Yu-chun. Fast and Efficient Scheduling Algorithms for Mobile Cloud Offloading[J]. Computer Science, 2018, 45(4): 94 -99 .
[6] ZHOU Yan-ping and YE Qiao-lin. L1-norm Distance Based Least Squares Twin Support Vector Machine[J]. Computer Science, 2018, 45(4): 100 -105 .
[7] LIU Bo-yi, TANG Xiang-yan and CHENG Jie-ren. Recognition Method for Corn Borer Based on Templates Matching in Muliple Growth Periods[J]. Computer Science, 2018, 45(4): 106 -111 .
[8] GENG Hai-jun, SHI Xin-gang, WANG Zhi-liang, YIN Xia and YIN Shao-ping. Energy-efficient Intra-domain Routing Algorithm Based on Directed Acyclic Graph[J]. Computer Science, 2018, 45(4): 112 -116 .
[9] CUI Qiong, LI Jian-hua, WANG Hong and NAN Ming-li. Resilience Analysis Model of Networked Command Information System Based on Node Repairability[J]. Computer Science, 2018, 45(4): 117 -121 .
[10] WANG Zhen-chao, HOU Huan-huan and LIAN Rui. Path Optimization Scheme for Restraining Degree of Disorder in CMT[J]. Computer Science, 2018, 45(4): 122 -125 .