计算机科学 ›› 2017, Vol. 44 ›› Issue (10): 96-98, 108.doi: 10.11896/j.issn.1002-137X.2017.10.018

• 网络与通信 • 上一篇    下一篇

一种改进的加权网络链接预测方法

陈旭,陈可佳   

  1. 南京邮电大学计算机学院 南京210003,南京邮电大学计算机学院 南京210003
  • 出版日期:2018-12-01 发布日期:2018-12-01
  • 基金资助:
    本文受国家自然科学基金面上项目(61571238),国家自然科学基金青年科学基金(61302158,61302157)资助

Improved Link Prediction Method for Weighted Networks

CHEN Xu and CHEN Ke-jia   

  • Online:2018-12-01 Published:2018-12-01

摘要: 目前,复杂网络的链接挖掘问题已得到了广泛研究,而加权网络的相关研究还较少且结果不甚理想。鉴于此,提出一种新的针对加权网络的链接预测方法,对以往方法中的加权相似性度量进行改造。新方法主要基于这一假定:链接xz为强关系而链接zy为弱关系时,链路〈x,z,y〉对节点x和 y之间形成链接的贡献最低。因此,新方法中链接xz为强关系而链接zy为弱关系时,链路〈x,z,y〉对节点x和节点y之间的相似性得分S(x,y)的贡献度的削弱程度最大。在带权网络数据集USAir和NetScience上的比较实验表明,新方法在AUC指标上具有一定的优势。

关键词: 加权复杂网络,链接预测,相似度指标,弱关系理论

Abstract: Currently,link mining in complex networks has been extensively studied.However,there are only a few rela-ted works on weighted networks and the results are not satisfactory.A new link prediction method for weighted networks was proposed by improving the weighted similarity measure of network structure.The new method is based on the assumption that when the link xz is strong and the link zy is weak,the link 〈x,z,y〉 has the least contribution to the link between node x and y.Therefore,in the new method,as the link xz is strong and the link zy is weak,the degree of weakening of the link 〈x,z,y〉 to the contribution degree of the similarity score S(x,y) between the node x and y is maximal.Comparative experiments on weighted dataset USAir and NetScience show that the proposed method has better performance in AUC indicators.

Key words: Weighted complex networks,Link prediction,Similarity index,Weak ties theory

[1] HOLLAND P W,LASKEY K B,LEINHARDT S.Stochastic blockmodels:first steps [J].Social Networks,1983,5(2):109-137.
[2] LV L Y.Link prediction on complex networks [J].Journal of University of Electronic Science and Technology of China,2010,39(5):652-660.(in Chinese) 吕琳媛.复杂网络链路预测[J].电子科技大学学报,2010,39(5):652-660.
[3] MURATA T,MORIYASU S.Link prediction of social net-works based on weighted proximity measures[C]∥IEEE/WIC/ACM International Conference on Web Intelligence.Silicon Valley,CA,USA,2007:85-88.
[4] LV L Y,ZHOU T.Role of weak ties in link prediction of complex networks[C]∥Proceedings of the 1st ACM International Workshop on Complex Networks Meet Information & Know-ledge Management.New York,USA,2009:55-58.
[5] LIBEN-NOWELL D,KLEINBERG J.The link prediction problem for social networks [J].Journal of the American Society for Information Science & Technology,2003,54(5):1345-1347.
[6] LV L Y,JIN C H,ZHOU T.Similarity index based on local paths for link prediction of complex networks [J].PhysicalReview E,2009,80(2):046122.
[7] ZHOU T,LV L Y,ZHANG Y C.Predicting missing links via local information [J].Physics of Condensed Matter,2009,71(4):623-630.
[8] Gl S,KAYA M,KAYA B.Predicting links in weighted disease networks[C]∥2016 3rd International Conference on Computer and Information Sciences (ICCOINS).Kuala Lumpur,Malaysia,2016:77-81.
[9] MARTIN ˇI'-IPi' S,MOˇIBOB E,METROVI' A.Link PredictiononTweets’ Content[C]∥2016 International Confe-rence on Information and Software Technologies:Information and Technologies.2016:559-567.
[10] GRANOVETTER M S.Strength of weak ties [J].AmericanJournal of Sociology,1973,78(6):1360-1380.
[11] LV L Y,ZHOU T.Link prediction in weighted networks:the role of weak ties [J].Europhysics Letters,2010,89(1):18001.
[12] MILO R,SHEN-ORR S,ITZKOVITZ S,et al.Network motifs:simple building blocks of complex networks [J].Science,2002,298(5594):824-827.
[13] MILO R,ITZKOVITZ S,KASHTAN N,et al.Super families of evolved and designed networks [J].Science,2004,303(5663):1538-1542.
[14] 吕琳媛,周涛.链路预测[M].北京:高等教育出版社,2013:290.
[15] SHARMA S,SINGH A.An efficient method for link prediction in weighted multiplex networks[C]∥International Conference on Signal-image Technology & Internet-based Systems.2015:453-459.
[16] SCHWEITZER F,FAGIOLO G,SORNETTE D,et al.Econo-mic networks:The new challenges [J].Science,2009,325(5939):422-425.
[17] BORGATTI S P,MHEGRA A,BRASS D J,et al.Networkanalysis in the social sciences[J].Science,2009,323(5916):892-895.
[18] COLIZZA V,BARRAT A,BARTHLEMY M,et al.The mo-deling of global epidemics:Stochastic dynamics and predictability [J].B MathBiol,2006,68(8):1893-1921.
[19] BARABSI A L,OLTVAI Z N.Network biology:Understan-ding the cell’s functional organization [J].Nat Rev Genet,2004,5(2):101-113.

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] 雷丽晖,王静. 可能性测度下的LTL模型检测并行化研究[J]. 计算机科学, 2018, 45(4): 71 -75, 88 .
[2] 夏庆勋,庄毅. 一种基于局部性原理的远程验证机制[J]. 计算机科学, 2018, 45(4): 148 -151, 162 .
[3] 厉柏伸,李领治,孙涌,朱艳琴. 基于伪梯度提升决策树的内网防御算法[J]. 计算机科学, 2018, 45(4): 157 -162 .
[4] 王欢,张云峰,张艳. 一种基于CFDs规则的修复序列快速判定方法[J]. 计算机科学, 2018, 45(3): 311 -316 .
[5] 孙启,金燕,何琨,徐凌轩. 用于求解混合车辆路径问题的混合进化算法[J]. 计算机科学, 2018, 45(4): 76 -82 .
[6] 张佳男,肖鸣宇. 带权混合支配问题的近似算法研究[J]. 计算机科学, 2018, 45(4): 83 -88 .
[7] 伍建辉,黄中祥,李武,吴健辉,彭鑫,张生. 城市道路建设时序决策的鲁棒优化[J]. 计算机科学, 2018, 45(4): 89 -93 .
[8] 刘琴. 计算机取证过程中基于约束的数据质量问题研究[J]. 计算机科学, 2018, 45(4): 169 -172 .
[9] 钟菲,杨斌. 基于主成分分析网络的车牌检测方法[J]. 计算机科学, 2018, 45(3): 268 -273 .
[10] 史雯隽,武继刚,罗裕春. 针对移动云计算任务迁移的快速高效调度算法[J]. 计算机科学, 2018, 45(4): 94 -99, 116 .