高级搜索

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

一种基于线性规划的有向网络链路预测方法

李劲松 彭建华 刘树新 季新生

李劲松, 彭建华, 刘树新, 季新生. 一种基于线性规划的有向网络链路预测方法[J]. 电子与信息学报, 2020, 42(10): 2394-2402. doi: 10.11999/JEIT190731
引用本文: 李劲松, 彭建华, 刘树新, 季新生. 一种基于线性规划的有向网络链路预测方法[J]. 电子与信息学报, 2020, 42(10): 2394-2402. doi: 10.11999/JEIT190731
Jinsong LI, Jianhua PENG, Shuxin LIU, Xinsheng JI. A Link Prediction Method in Directed Networks Via Linear Programming[J]. Journal of Electronics and Information Technology, 2020, 42(10): 2394-2402. doi: 10.11999/JEIT190731
Citation: Jinsong LI, Jianhua PENG, Shuxin LIU, Xinsheng JI. A Link Prediction Method in Directed Networks Via Linear Programming[J]. Journal of Electronics and Information Technology, 2020, 42(10): 2394-2402. doi: 10.11999/JEIT190731

一种基于线性规划的有向网络链路预测方法

doi: 10.11999/JEIT190731
基金项目: 国家自然科学基金(61803384)
详细信息
    作者简介:

    李劲松:男,1992年生,博士生,研究方向为复杂网络,链路预测,网络安全

    彭建华:男,1966年生,研究员,研究方向为网络安全,云安全,复杂网络

    刘树新:男,1987年生,助理研究员,研究方向为复杂网络,链路预测,网络演化

    季新生:男,1969年生,教授,研究方向为网络安全,云安全,复杂网络

    通讯作者:

    刘树新 liushuxin11@126.com

  • 中图分类号: N92; TP393

A Link Prediction Method in Directed Networks Via Linear Programming

Funds: The National Natural Science Foundation of China (61803384)
  • 摘要: 大多数有向网络链路预测方法在计算节点相似性时没有充分考虑有向网络的结构特点,未区分不同有向邻居对连边形成具有的贡献差异,导致预测性能受到局限。鉴于此,该文提出一种基于线性规划的有向网络链路预测方法。该方法对3种有向邻居的信息贡献进行量化分析,结合结构特点建立线性规划模型,进而通过求解贡献矩阵的最优解构建相似性指标。9个真实有向网络中的实验结果表明,所提方法相比于9种现有方法在两种衡量标准下表现出较高的预测性能与良好的鲁棒性。
  • 图  1  相似性矩阵的计算过程示意图

    图  2  相似性指标与对应邻接矩阵元素之间的关系示意图

    图  3  9组网络中ROC曲线对比图

    图  4  AUC随训练集划分比例变化曲线图

    图  5  AUC随参数$\alpha $变化曲线图

    表  1  网络数据基本统计参数

    序号名称类型$N$$M$$\left\langle k \right\rangle $$\rho $(%)$C$$\left\langle d \right\rangle $$\gamma $$\kappa $
    (1)ADO社交网络2,53912,96910.2238.814.25.300.2518.25
    (2)HIG社交网络7036610.4650.340.43.510.0834.38
    (3)RES社交网络2172,67224.6362.430.42.790.0966.32
    (4)EMA信息网络1,00525,57150.8971.125.73.01–0.0142.80
    (5)USA交通网络1,57428,23635.8878.138.43.85–0.1131.85
    (6)OF交通网络2,93930,50120.7697.225.55.190.0511.74
    (7)CELE生物网络4534,59620.2916.812.43.03–0.2262.62
    (8)FWFD生态网络1282,13733.392.931.41.88–0.1045.02
    (9)LAK生态网络1832,49427.264.0933.22.65–0.2662.99
    下载: 导出CSV

    表  2  AUC结果对比

    预测指标ADOHIGRESEMAUSAOFCELEFWFDLAK
    DCN0.7160.8600.8890.9490.9690.9680.8040.7450.942
    DAA0.7140.8620.8950.9530.9720.9690.8070.7490.940
    DRA0.7160.8610.8950.9560.9730.9710.8110.7520.939
    DPA0.6800.6210.6500.8870.9530.9240.8100.8540.946
    Bifan0.7700.8260.8590.9320.9640.9650.8880.9200.988
    LP-0.0010.7810.8820.8990.9540.9760.9840.8600.7690.964
    Katz-0.0010.877 0.8830.8980.9540.9760.9840.8740.7780.970
    MFI0.8720.8450.7920.7720.9080.9750.8360.7340.947
    LO-0.010.6780.8300.8880.9490.9670.9710.8890.972 0.995
    LO-0.0010.6790.8300.8680.9560.9770.9740.8920.9340.990
    LPD-0.01-10.8030.898 0.917 0.9560.984 0.991 0.899 0.9560.994
    LPD-0.001-10.8120.8830.9020.969 0.9680.9900.8860.9070.988
    LPD-max0.8140.898 0.919 0.969 0.984 0.993 0.907 0.973 0.996
    下载: 导出CSV
  • [1] REN Zhuoming, ZENG An, and ZHANG Yicheng. Structure-oriented prediction in complex networks[J]. Physics Reports, 2018, 750: 1–51. doi:  10.1016/J.PHYSREP.2018.05.002
    [2] LÜ Linyuan and ZHOU Tao. Link prediction in complex networks: A survey[J]. Physica A: Statistical Mechanics and its Applications, 2011, 390(6): 1150–1170. doi:  10.1016/J.PHYSA.2010.11.027
    [3] 王凯, 李星, 兰巨龙, 等. 一种基于资源传输路径拓扑有效性的链路预测方法[J]. 电子与信息学报, 2020, 42(3): 653–660. doi:  10.11999/JEIT190333

    WANG Kai, LI Xing, LAN Julong, et al. A new link prediction method for complex networks based on topological effectiveness of resource transmission paths[J]. Journal of Electronics &Information Technology, 2020, 42(3): 653–660. doi:  10.11999/JEIT190333
    [4] 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
    [5] AGHABOZORGI F and KHAYYAMBASHI M R. A new similarity measure for link prediction based on local structures in social networks[J]. Physica A: Statistical Mechanics and its Applications, 2018, 501: 12–23. doi:  10.1016/J.PHYSA.2018.02.010
    [6] 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
    [7] 王凯, 刘树