高级搜索

一种基于资源传输路径拓扑有效性的链路预测方法

王凯 李星 兰巨龙 卫红权 刘树新

引用本文: 王凯, 李星, 兰巨龙, 卫红权, 刘树新. 一种基于资源传输路径拓扑有效性的链路预测方法[J]. 电子与信息学报, 2020, 42(3): 653-660. doi: 10.11999/JEIT190333 shu
Citation:  Kai WANG, Xing LI, Julong LAN, Hongquan WEI, Shuxin LIU. A New Link Prediction Method for Complex Networks Based onTopological Effectiveness of Resource Transmission Paths[J]. Journal of Electronics and Information Technology, 2020, 42(3): 653-660. doi: 10.11999/JEIT190333 shu

一种基于资源传输路径拓扑有效性的链路预测方法

    作者简介: 王凯: 男,1980年生,副研究员,博士生,研究方向为链路预测、社会网络分析;
    李星: 男,1987年生,助理研究员,博士生,研究方向为链路预测;
    兰巨龙: 男,1962年生,教授,博士生导师,研究方向为新型网络体系,网络动力学;
    卫红权: 男,1970年生,副研究员,硕士生导师,研究方向为社团发现;
    刘树新: 男,1987年生,助理研究员,博士,研究方向为复杂网络演化、链路预测
    通讯作者: 刘树新,liushuxin11@126.com;liushuxin11@gmail.com
  • 基金项目: 国家自然科学基金(61803384),国家自然科学基金创新研究群体项目(61521003)

摘要: 链路预测旨在利用网络中已有的拓扑结构或其他信息,预测未连边节点间存在连接的可能性。资源分配指标具有较低复杂度的同时取得了较好的预测效果,但在资源传输过程的描述中缺少对路径有效性的刻画。资源传输过程是网络演化连边产生的重要内在动力,通过分析节点间资源传输路径周围拓扑的有效性,该文提出一种基于资源传输路径有效性的链路预测方法。该方法首先分析了节点间潜在的资源传输路径对资源传输量的影响,提出资源传输路径有效性的量化方法。然后,基于资源传输路径的有效性,通过对双向资源传输量进行刻画,提出了节点间传输路径的有效性指标。在12个实际网络数据集上的实验测试表明,相比其他基于相似性的链路预测方法,该方法在AUC和Precision衡量标准下能够取得更好的效果。

English

    1. [1]

      WANG Minggang, ZHAO Longfeng, DU Ruijin, et al. A novel hybrid method of forecasting crude oil prices using complex network science and artificial intelligence algorithms[J]. Applied Energy, 2018, 220: 480–495. doi: 10.1016/j.apenergy.2018.03.148

    2. [2]

      GOSAK M, MARKOVIČ R, DOLENŠEK J, et al. Network science of biological systems at different scales: A review[J]. Physics of Life Reviews, 2018, 24: 118–135. doi: 10.1016/j.plrev.2017.11.003

    3. [3]

      DU Wenbo, ZHANG Mingyuan, YING Wen, et al. The networked evolutionary algorithm: A network science perspective[J]. Applied Mathematics and Computation, 2018, 338: 33–43. doi: 10.1016/j.amc.2018.06.002

    4. [4]

      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

    5. [5]

      王凯, 刘树新, 陈鸿昶, 等. 一种基于节点间资源承载度的链路预测方法[J]. 电子与信息学报, 2019, 41(5): 1225–1234. doi: 10.11999/JEIT180553
      WANG Kai, LIU Shuxin, CHEN Hongchang, et al. A new link prediction method for complex networks based on resources carrying capacity between nodes[J]. Journal of Electronics &Information Technology, 2019, 41(5): 1225–1234. doi: 10.11999/JEIT180553

    6. [6]

      BENSON A R, ABEBE R, SCHAUB M T, et al. Simplicial closure and higher-order link prediction[J]. The National Academy of Sciences of the United States of America, 2018, 115(48): E11221–E11230. doi: 10.1073/pnas.1800683115

    7. [7]

      LIU Shuxin, JI Xinsheng, LIU Caixia, et al. Similarity indices based on link weight assignment for link prediction of unweighted complex networks[J]. International Journal of Modern Physics B, 2017, 31(2): 1650254. doi: 10.1142/S0217979216502544

    8. [8]

      LORRAIN F and WHITE H C. Structural Equivalence of Individuals in Social Networks[M]. LEINHARDT S. Social Networks: A Developing Paradigm. Lausanne: Academic Press, 1977: 67-98. doi: 10.1080/0022250X.1971.9989788.

    9. [9]

      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

    10. [10]

      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

    11. [11]

      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

    12. [12]

      XIE Yanbo, ZHOU Tao, and WANG Binhong. Scale-free networks without growth[J]. Physica A: Statistical Mechanics and its Applications, 2008, 387(7): 1683–1688. doi: 10.1016/j.physa.2007.11.005

    13. [13]

      SALTON G and MCGILL M J. Introduction to Modern Information Retrieval[M]. New York: McGraw-Hill, 1986.

    14. [14]

      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

    15. [15]

      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

    16. [16]

      KATZ L. A new status index derived from sociometric analysis[J]. Psychometrika, 1953, 18(1): 39–43. doi: 10.1007/BF02289026

    17. [17]

      KLEIN D J and RANDIĆ M. Resistance distance[J]. Journal of Mathematical Chemistry, 1993, 12(1): 81–95. doi: 10.1007/BF01164627

    18. [18]

      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

    19. [19]

      BRIN S and PAGE L. The anatomy of a large-scale hypertextual Web search engine[J]. Computer Networks and ISDN Systems, 1998, 30(1/7): 107–117. doi: 10.1016/s0169-7552(98)00110-x

    20. [20]

      YANG Dingda, LIAO Xiangwen, SHEN Huawei, et al. Dynamic node immunization for restraint of harmful information diffusion in social networks[J]. Physica A: Statistical Mechanics and Its Applications, 2018, 503: 640–649. doi: 10.1016/j.physa.2018.02.128

    21. [21]

      刘树新, 季新生, 刘彩霞, 等. 一种信息传播促进网络增长的网络演化模型[J]. 物理学报, 2014, 63(15): 158902. doi: 10.7498/aps.63.158902
      LIU 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

    22. [22]

      YAO Yabing, ZHANG Ruisheng, YANG Fan, et al. Link prediction in complex networks based on the interactions among paths[J]. Physica A: Statistical Mechanics and Its Applications, 2018, 510: 52–67. doi: 10.1016/j.physa.2018.06.051

    23. [23]

      LIU Liang, QU Bo, CHEN Bin, et al. Modelling of information diffusion on social networks with applications to WeChat[J]. Physica A: Statistical Mechanics and Its Applications, 2018, 496: 318–329. doi: 10.1016/j.physa.2017.12.026

    24. [24]

      SATHIYAKUMARI K and VIJAYA M S. Identification of Subgroups in a Directed Social Network Using Edge Betweenness and Random Walks[M]. SATAPATHY S C, BHATEJA V, and DAS S. Smart Computing and Informatics. Singapore: Springer, 2018: 115-125. doi: 10.1007/978-981-10-5544-7_12.

    25. [25]

      WU Yiteng, YU Hongtao, ZHANG Jianpeng, et al. USI-AUC: An evaluation criterion of community detection based on a novel link-prediction method[J]. Intelligent Data Analysis, 2018, 22(2): 439–462. doi: 10.3233/IDA-173400

    26. [26]

      CHUAN P M, SON L H, ALI M, et al. Link prediction in co-authorship networks based on hybrid content similarity metric[J]. Applied Intelligence, 2018, 48(8): 2470–2486. doi: 10.1007/s10489-017-1086-x

    1. [1]

      缪祥华, 单小撤. 基于密集连接卷积神经网络的入侵检测技术研究. 电子与信息学报, 2020, 41(0): 1-7.

    2. [2]

      游凌, 李伟浩, 张文林, 王科人. 基于深度神经网络的Morse码自动译码算法. 电子与信息学报, 2020, 41(0): 1-6.

  • 图 1  网络中节点间多路径传输示意图

    图 2  网络拓扑结构与路径传输有效性的关系示意图

    图 3  不同网络结构下路径数目对比分析

    图 4  不同网络结构下路径有效性对比分析

    图 5  存在直接连接的两点之间路径有效性的量化

    图 6  未直接连接的两点之间路径有效性的量化

    图 7  节点xy传输路径有效性量化举例

    图 8  节点yx传输路径有效性量化举例

    图 9  调节参数对AUC结果的影响曲线图

    图 10  强度参数对Pre结果影响曲线图

    表 1  网络数据特征参数

    网络AIDSFWEWHSFigeysUCMetbolic
    节点数14669185822391899453
    边数180880125346432138382025
    集聚系数2.4725.5113.495.7614.578.94
    平均度3.421.643.393.983.062.66
    平均路径–0.725–0.298–0.085–0.331–0.188–0.226
    匹配系数0.0520.5520.09040.040.1090.647
    下载: 导出CSV

    表 2  AUC结果对比分析

    方法AIDSFWEWHSFigeysUCMetbolic
    CN0.5990.6840.8120.5660.7810.921
    RA0.6090.7020.8160.5700.7870.959
    AA0.6090.6950.8150.5690.7870.955
    CAR0.5990.6850.8120.5670.7830.920
    LP(a)0.8360.7020.9330.8880.8930.920
    LP(b)0.8330.7280.9400.9030.9030.921
    Katz(a)0.8540.7040.9330.8870.8930.920
    Katz(b)0.8520.7340.9370.8980.9030.920
    ACT0.9540.7790.8680.9170.8960.767
    Cos+0.5910.5100.9600.8440.8690.904
    本文方法0.9610.8270.9710.9520.9290.964
    (a)可调参数$\alpha {\rm{ = 0}}{\rm{.001}}$ (b)可调参数$\alpha {\rm{ = 0}}{\rm{.01}}$
    下载: 导出CSV

    表 3  Pre结果对比

    方法AIDSFWEWHSFigeysUCMetbolic
    CN0.0190.1430.0170.0110.0340.202
    RA0.0280.1650.0080.0120.0260.319
    AA0.0280.1520.0120.0120.0330.252
    CAR0.0190.1370.0330.0250.0640.193
    LP(a)0.0550.1530.0210.0110.0340.202
    LP(b)0.0550.1800.0550.0120.0530.200
    Katz(a)0.0550.1530.0210.0100.0340.202
    Katz(b)0.0550.1830.0710.0110.0540.198
    ACT0.0000.1280.0000.0000.0000.000
    Cos+0.0000.0000.0150.0050.0100.097
    本文方法0.0680.3440.1070.1300.0930.374
    (a)可调参数$\alpha {\rm{ = 0}}{\rm{.001}}$ (b)可调参数$\alpha {\rm{ = 0}}{\rm{.01}}$
    下载: 导出CSV
  • 加载中
图(10)表(3)
计量
  • PDF下载量:  39
  • 文章访问数:  901
  • HTML全文浏览量:  563
文章相关
通讯作者: 陈斌, bchen63@163.com
  • 1. 

    沈阳化工大学材料科学与工程学院 沈阳 110142

  1. 本站搜索
  2. 百度学术搜索
  3. 万方数据库搜索
  4. CNKI搜索

/

返回文章