搜索

x

留言板

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

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

复杂网络链路可预测性: 基于特征谱视角

谭索怡 祁明泽 吴俊 吕欣

引用本文:
Citation:

复杂网络链路可预测性: 基于特征谱视角

谭索怡, 祁明泽, 吴俊, 吕欣

Link predictability of complex network from spectrum perspective

Tan Suo-Yi, Qi Ming-Ze, Wu Jun, Lu Xin
PDF
HTML
导出引用
  • 近年来链路预测的理论和实证研究发展迅速, 大部分工作关注于提出更精确的预测算法. 事实上, 链路预测的前提是网络的结构本身能够被预测, 这种“可被预测的程度”可以看作是网络自身的基本属性. 本文拟从特征谱的视角去解释网络的链路可预测性, 并刻画网络的拓扑结构信息, 通过对网络特征谱进行分析, 构造了复杂网络链路可预测性评价指标. 通过该指标计算和分析不同网络的链路可预测性, 能够在选择算法前获取目标网络能够被预测的难易程度, 解决到底是网络本身难以预测还是预测算法不合适的问题, 为复杂网络与链路预测算法的选择和匹配问题提供帮助.
    Link prediction in complex networks has attracted much attention in recent years and most of work focuses on proposing more accurate prediction algorithms. In fact, “how difficultly the target network can be predicted” can be regarded as an important attribute of the network itself. In this paper it is intended to explain and characterize the link predictability of the network from the perspective of spectrum. By analyzing the characteristic spectrum of the network, we propose the network link predictability index. Through calculating the index, it is possible to learn how difficultly the target network can be predicted before choosing algorithm, and to solve the problem whether the network is unpredictable or the algorithm is inappropriate. The results are useful for the selecting and matching the complex network and link prediction algorithms.
      通信作者: 吴俊, wujunpla@hotmail.com ; 吕欣, xin.lu@flowminder.org
    • 基金项目: 国家级-不完全信息条件下基于链路预测的复杂网络瓦解问题研究(71871217)
      Corresponding author: Wu Jun, wujunpla@hotmail.com ; Lu Xin, xin.lu@flowminder.org
    [1]

    Albert R, Jeong H, Barabási A L 2000 Nature 406 378Google Scholar

    [2]

    Albert R, Barabási A L 2002 Rev. Mod. Phys. 74 47Google Scholar

    [3]

    Newman M E J 2003 SIAM Rev. 45 167Google Scholar

    [4]

    Wang X F 2002 Int. J. Bifurcat. Chaos 12 885Google Scholar

    [5]

    侯绿林, 老松杨, 肖延东, 白亮 2015 物理学报 64 188901Google Scholar

    Hou L L, Lao S Y, Xiao Y D, Bai L 2015 Acta Phys. Sin. 64 188901Google Scholar

    [6]

    吕琳媛 2010 电子科技大学学报 39 651Google Scholar

    Lü L L 2010 J. Univ. Electron. Sci. Technol. China 39 651Google Scholar

    [7]

    吕琳媛, 周涛 2013 链路预测 (北京: 高等教育出版社) 第 41页

    Lü L L, Zhou T 2013 Link Prediction (Beijing: Higher Education Press) p41 (in Chinese)

    [8]

    Sarukkai R R 2010 Comput. Networking 33 377

    [9]

    Clauset A, Moore C, Newman M E J 2008 Nature 453 98Google Scholar

    [10]

    Guimerá R, Marta S P 2009 Proc. Natl. Acad. Sci. U.S.A. 106 22073Google Scholar

    [11]

    Pan L M, Zhou T, Lü L Y, Hu C K 2016 Sci. Rep. 6 22955Google Scholar

    [12]

    Taskar B, Wong M F, Abbeel P, Koller D 2003 Proceedings of the 16th International Conference on Neural Information Processing Systems (Cambridge: MIT Press) pp659–666

    [13]

    David L N, Kleinberg J 2007 J. Am. Soc. Inf. Sci. Technol. 58 1019Google Scholar

    [14]

    Zhou T, Lü L Y, Zhang Y C 2009 Eur. Phys. J. B 71 623Google Scholar

    [15]

    许小可, 方锦清 2010 复杂系统与复杂性科学 7 116Google Scholar

    Xu X K, Fang J Q 2010 Complex Syst. Complex Sci. 7 116Google Scholar

    [16]

    Tan S Y, Wu J, Lü L Y, Li M J, Lu X 2016 Sci. Rep. 6 22916Google Scholar

    [17]

    Amaral L A N 2008 Proc. Natl. Acad. Sci. U.S.A. 105 6795Google Scholar

    [18]

    Menche J, Sharma A, Kitsak M, Ghiassian S D, Vidal M, Loscalzo J, Barabási A L 2015 Science 347 1257601Google Scholar

    [19]

    Lü L Y, Medo M, Yeung C H, Zhang Y C, Zhang Z K, Zhou T 2012 Phys. Rep. 519 1Google Scholar

    [20]

    朱郁筱, 吕琳媛 2012 电子科技大学学报 41 163

    Zhou Y X, Lü L Y 2012 J. Univ. Electron. Sci. Technol. China 41 163

    [21]

    刘宏鲲, 吕琳媛, 周涛 2011 中国科学: 物理学 力学 天文学 41 816Google Scholar

    Liu H K, Lü L Y, Zhou T 2011 Scientia Sinica: Phys. Mech. Astron. 41 816Google Scholar

    [22]

    Zhang Q M, Lü L Y, Wang W Q, X Y, Zhou T 2013 PLoS One 8 1

    [23]

    Wang W Q, Zhang Q M, Zhou T 2012 EPL 98 28004Google Scholar

    [24]

    Zhang Q M, Xu X K, Zhu Y X, Zhou T 2015 Sci. Rep. 5 10350Google Scholar

    [25]

    Lü L Y, Zhou T 2011 Physica A 390 1150Google Scholar

    [26]

    于会, 刘尊, 李勇军, 尹超 2016 物理学报 65 020501Google Scholar

    Yu H, Liu Z, Li Y J, Yi C 2016 Acta Phys. Sin. 65 020501Google Scholar

    [27]

    许小可, 许爽, 朱郁筱, 张千明 2014 复杂系统与复杂性科学 11 41

    Xu X K, Xu S, Zhu Y X, Zhang Q M 2014 Complex Syst. Complex Sci. 11 41

    [28]

    Lü L Y, Pan L M, Zhou T, Zhang Y C, Stanley H E 2015 Proc. Natl. Acad. Sci. USA 112 2325Google Scholar

    [29]

    Yin L K, Zheng H Y, Bian T, Deng Y 2014 Physica A 482 699712

    [30]

    Hanley J A, McNeil B J 1982 Radiology 143 29Google Scholar

    [31]

    Herlocker J L, Konstan J A, Terveen L G, Riedl J T 2004 ACM Trans. Inf. Syst. 22 5Google Scholar

    [32]

    Zhou T, Ren J, Matúš M, Zhang Y C 2007 Phys. Rev. E 76 046115Google Scholar

    [33]

    Farkas I J, Derényi I, Barabási A L, Vicsek T 2001 Phys. Rev. E 64 026704Google Scholar

    [34]

    Estrada E, Hatano N, Benzi M 2012 Phys. Rep. 514 89Google Scholar

    [35]

    Newman M E J 2006 Phys. Rev. E 74 036104Google Scholar

    [36]

    Kousik D, Sovan S, Madhumangal P 2018 Soc. Netw. Anal. Min. 8 1Google Scholar

    [37]

    张金浩, 申玉卓, 李艳雨, 孙娟, 李晓霞 2017 物理学报 66 188901Google Scholar

    Zhang J H, Shen Y Z, Li Y Y, Sun J, Li X X 2017 Acta Phys. Sin. 66 188901Google Scholar

    [38]

    Wang R, Lin P, Liu M X, Wu Y, Zhou T, Zhou C S 2019 Phys. Rev. Lett. 123 038301Google Scholar

    [39]

    Estrada E 2006 EPL 73 649Google Scholar

    [40]

    Tan S Y, Wu J, Li M J, Lu X 2016 EPL 114 58002Google Scholar

    [41]

    Estrada E, Hatano N 2007 Chem. Phys. Lett. 439 247Google Scholar

  • 图 1  链路预测问题示意图

    Fig. 1.  Illustration of link prediction problem

    图 2  无标度网络特征谱直方图

    Fig. 2.  The histograms of eigenvalues of random sacle-free networks

    图 3  不同节点规模下, 模型网络可预测性$ p $$ \alpha $的变化

    Fig. 3.  The link predictability of model network versus $ \alpha $ with various $ N $

    图 4  无标度网络和随机网络可预测性示意图

    Fig. 4.  The link predictability of BA scale-free network and random graph

    图 5  预测算法在真实网络上的表现

    Fig. 5.  The performance of prediction algorithms in real networks

    表 1  链路预测算法在模型网络中的表现

    Table 1.  Performance of link prediction algorithms in model networks.

    网络 $ p $ CN AA RA LP IA CAR PA Katz RWR ACT LRW LHN-II
    BA网络 0.975 0.423 0.324 0.272 0.415 0.271 0.283 0.594 0.412 0.136 0.507 0.085 0.003
    随机网络 0.543 0.015 0.008 0.009 0.008 0.009 0 0.030 0.008 0.002 0.020 0 0.001
    下载: 导出CSV

    表 2  不同领域真实网络拓扑属性

    Table 2.  Basic statistics of real networks.

    网络 V E r $\langle k\rangle$ $\langle l\rangle$ C
    C_elegans 297 2148 –0.163 14.47 2.46 0.308
    Windsurfers 43 336 –0.147 15.63 1.70 0.564
    Adolescent health 2539 12969 0.251 10.22 4.52 0.142
    Jazz 198 2742 0.020 27.69 2.21 0.520
    USAirport 1574 28236 –0.113 35.87 3.14 0.384
    Metabolic 453 4596 –0.226 20.29 2.64 0.124
    Yeast 2375 11693 0.454 9.85 5.10 0.388
    US powergrid 4941 6594 0.003 2.67 20.09 0.103
    Physicians 241 1098 –0.056 9.11 3.02 0.552
    Air Traffic Control 1226 2615 –0.015 4.27 6.10 0.063
    Contiguous USA 49 107 0.233 4.37 4.26 0.406
    Email 1133 5451 0.078 9.62 3.65 0.166
    King James Bible 1773 9131 –0.048 10.30 3.38 0.163
    Protein Stelzl 1706 6207 –0.191 7.28 5.09 0.006
    Router 5022 6258 –0.138 2.49 6.45 0.033
    下载: 导出CSV

    表 3  链路预测算法在真实网络中的precision值

    Table 3.  The precision of link prediction algorithms in real networks

    网络 p CN AA RA LP IA CAR PA Katz RWR ACT LRW SRW
    C_elegans 0.999 0.100 0.107 0.105 0.101 0.108 0.094 0.058 0.101 0.105 0.055 0.110 0.108
    Windsurfers 0.999 0.379 0.396 0.413 0.370 0.393 0.381 0.214 0.369 0.360 0.247 0.402 0.426
    Adolescent health 0.422 0.103 0.103 0.088 0.089 0.101 0.094 0.003 0.088 0.053 0.008 0.042 0.047
    Jazz 1.000 0.502 0.523 0.542 0.489 0.535 0.517 0.133 0.489 0.352 0.168 0.342 0.393
    USAirport 0.998 0.333 0.336 0.364 0.332 0.332 0.330 0.280 0.332 0.087 0.294 0.076 0.080
    Metabolic 0.999 0.137 0.195 0.269 0.141 0.168 0.132 0.104 0.141 0.196 0.092 0.214 0.215
    Yeast 0.998 0.154 0.177 0.267 0.158 0.161 0.148 0.094 0.174 0.073 0.211 0.045 0.059
    US powergrid 0.362 0.054 0.032 0.028 0.058 0.047 0.037 0.000 0.057 0.016 0.034 0.015 0.018
    Physicians 0.368 0.119 0.126 0.121 0.117 0.122 0.106 0.014 0.117 0.119 0.015 0.132 0.127
    Air Traffic Control 0.480 0.036 0.024 0.018 0.037 0.021 0.025 0.007 0.037 0.002 0.015 0.002 0.002
    Contiguous USA 0.540 0.096 0.130 0.132 0.005 0.000 0.000 0.012 0.004 0.067 0.053 0.133 0.121
    Email 0.950 0.144 0.158 0.143 0.142 0.159 0.145 0.018 0.141 0.065 0.024 0.052 0.051
    King James Bible 0.960 0.167 0.270 0.446 0.163 0.256 0.176 0.078 0.163 0.186 0.069 0.197 0.224
    Protein Stelzl 0.441 0.001 0.002 0.001 0.001 0.002 0.006 0.014 0.001 0.006 0.013 0.006 0.006
    Router 0.511 0.051 0.029 0.020 0.056 0.031 0.055 0.022 0.055 0.006 0.164 0.005 0.005
    下载: 导出CSV
  • [1]

    Albert R, Jeong H, Barabási A L 2000 Nature 406 378Google Scholar

    [2]

    Albert R, Barabási A L 2002 Rev. Mod. Phys. 74 47Google Scholar

    [3]

    Newman M E J 2003 SIAM Rev. 45 167Google Scholar

    [4]

    Wang X F 2002 Int. J. Bifurcat. Chaos 12 885Google Scholar

    [5]

    侯绿林, 老松杨, 肖延东, 白亮 2015 物理学报 64 188901Google Scholar

    Hou L L, Lao S Y, Xiao Y D, Bai L 2015 Acta Phys. Sin. 64 188901Google Scholar

    [6]

    吕琳媛 2010 电子科技大学学报 39 651Google Scholar

    Lü L L 2010 J. Univ. Electron. Sci. Technol. China 39 651Google Scholar

    [7]

    吕琳媛, 周涛 2013 链路预测 (北京: 高等教育出版社) 第 41页

    Lü L L, Zhou T 2013 Link Prediction (Beijing: Higher Education Press) p41 (in Chinese)

    [8]

    Sarukkai R R 2010 Comput. Networking 33 377

    [9]

    Clauset A, Moore C, Newman M E J 2008 Nature 453 98Google Scholar

    [10]

    Guimerá R, Marta S P 2009 Proc. Natl. Acad. Sci. U.S.A. 106 22073Google Scholar

    [11]

    Pan L M, Zhou T, Lü L Y, Hu C K 2016 Sci. Rep. 6 22955Google Scholar

    [12]

    Taskar B, Wong M F, Abbeel P, Koller D 2003 Proceedings of the 16th International Conference on Neural Information Processing Systems (Cambridge: MIT Press) pp659–666

    [13]

    David L N, Kleinberg J 2007 J. Am. Soc. Inf. Sci. Technol. 58 1019Google Scholar

    [14]

    Zhou T, Lü L Y, Zhang Y C 2009 Eur. Phys. J. B 71 623Google Scholar

    [15]

    许小可, 方锦清 2010 复杂系统与复杂性科学 7 116Google Scholar

    Xu X K, Fang J Q 2010 Complex Syst. Complex Sci. 7 116Google Scholar

    [16]

    Tan S Y, Wu J, Lü L Y, Li M J, Lu X 2016 Sci. Rep. 6 22916Google Scholar

    [17]

    Amaral L A N 2008 Proc. Natl. Acad. Sci. U.S.A. 105 6795Google Scholar

    [18]

    Menche J, Sharma A, Kitsak M, Ghiassian S D, Vidal M, Loscalzo J, Barabási A L 2015 Science 347 1257601Google Scholar

    [19]

    Lü L Y, Medo M, Yeung C H, Zhang Y C, Zhang Z K, Zhou T 2012 Phys. Rep. 519 1Google Scholar

    [20]

    朱郁筱, 吕琳媛 2012 电子科技大学学报 41 163

    Zhou Y X, Lü L Y 2012 J. Univ. Electron. Sci. Technol. China 41 163

    [21]

    刘宏鲲, 吕琳媛, 周涛 2011 中国科学: 物理学 力学 天文学 41 816Google Scholar

    Liu H K, Lü L Y, Zhou T 2011 Scientia Sinica: Phys. Mech. Astron. 41 816Google Scholar

    [22]

    Zhang Q M, Lü L Y, Wang W Q, X Y, Zhou T 2013 PLoS One 8 1

    [23]

    Wang W Q, Zhang Q M, Zhou T 2012 EPL 98 28004Google Scholar

    [24]

    Zhang Q M, Xu X K, Zhu Y X, Zhou T 2015 Sci. Rep. 5 10350Google Scholar

    [25]

    Lü L Y, Zhou T 2011 Physica A 390 1150Google Scholar

    [26]

    于会, 刘尊, 李勇军, 尹超 2016 物理学报 65 020501Google Scholar

    Yu H, Liu Z, Li Y J, Yi C 2016 Acta Phys. Sin. 65 020501Google Scholar

    [27]

    许小可, 许爽, 朱郁筱, 张千明 2014 复杂系统与复杂性科学 11 41

    Xu X K, Xu S, Zhu Y X, Zhang Q M 2014 Complex Syst. Complex Sci. 11 41

    [28]

    Lü L Y, Pan L M, Zhou T, Zhang Y C, Stanley H E 2015 Proc. Natl. Acad. Sci. USA 112 2325Google Scholar

    [29]

    Yin L K, Zheng H Y, Bian T, Deng Y 2014 Physica A 482 699712

    [30]

    Hanley J A, McNeil B J 1982 Radiology 143 29Google Scholar

    [31]

    Herlocker J L, Konstan J A, Terveen L G, Riedl J T 2004 ACM Trans. Inf. Syst. 22 5Google Scholar

    [32]

    Zhou T, Ren J, Matúš M, Zhang Y C 2007 Phys. Rev. E 76 046115Google Scholar

    [33]

    Farkas I J, Derényi I, Barabási A L, Vicsek T 2001 Phys. Rev. E 64 026704Google Scholar

    [34]

    Estrada E, Hatano N, Benzi M 2012 Phys. Rep. 514 89Google Scholar

    [35]

    Newman M E J 2006 Phys. Rev. E 74 036104Google Scholar

    [36]

    Kousik D, Sovan S, Madhumangal P 2018 Soc. Netw. Anal. Min. 8 1Google Scholar

    [37]

    张金浩, 申玉卓, 李艳雨, 孙娟, 李晓霞 2017 物理学报 66 188901Google Scholar

    Zhang J H, Shen Y Z, Li Y Y, Sun J, Li X X 2017 Acta Phys. Sin. 66 188901Google Scholar

    [38]

    Wang R, Lin P, Liu M X, Wu Y, Zhou T, Zhou C S 2019 Phys. Rev. Lett. 123 038301Google Scholar

    [39]

    Estrada E 2006 EPL 73 649Google Scholar

    [40]

    Tan S Y, Wu J, Li M J, Lu X 2016 EPL 114 58002Google Scholar

    [41]

    Estrada E, Hatano N 2007 Chem. Phys. Lett. 439 247Google Scholar

  • [1] 汪亭亭, 梁宗文, 张若曦. 基于信息熵与迭代因子的复杂网络节点重要性评价方法. 物理学报, 2023, 72(4): 048901. doi: 10.7498/aps.72.20221878
    [2] 杨青林, 王立夫, 李欢, 余牧舟. 基于相对距离的复杂网络谱粗粒化方法. 物理学报, 2019, 68(10): 100501. doi: 10.7498/aps.68.20181848
    [3] 孔江涛, 黄健, 龚建兴, 李尔玉. 基于复杂网络动力学模型的无向加权网络节点重要性评估. 物理学报, 2018, 67(9): 098901. doi: 10.7498/aps.67.20172295
    [4] 周建, 贾贞, 李科赞. 复杂网络谱粗粒化方法的改进算法. 物理学报, 2017, 66(6): 060502. doi: 10.7498/aps.66.060502
    [5] 武喜萍, 杨红雨, 韩松臣. 基于复杂网络理论的多元混合空管技术保障系统网络特征分析. 物理学报, 2016, 65(14): 140203. doi: 10.7498/aps.65.140203
    [6] 李勇军, 尹超, 于会, 刘尊. 基于最大熵模型的微博传播网络中的链路预测. 物理学报, 2016, 65(2): 020501. doi: 10.7498/aps.65.020501
    [7] 侯绿林, 老松杨, 肖延东, 白亮. 复杂网络可控性研究现状综述. 物理学报, 2015, 64(18): 188901. doi: 10.7498/aps.64.188901
    [8] 余晓平, 裴韬. 手机通话网络度特征分析. 物理学报, 2013, 62(20): 208901. doi: 10.7498/aps.62.208901
    [9] 刘建国, 任卓明, 郭强, 汪秉宏. 复杂网络中节点重要性排序的研究进展. 物理学报, 2013, 62(17): 178901. doi: 10.7498/aps.62.178901
    [10] 于会, 刘尊, 李勇军. 基于多属性决策的复杂网络节点重要性综合评价方法. 物理学报, 2013, 62(2): 020204. doi: 10.7498/aps.62.020204
    [11] 梁义, 王兴元. 基于低阶矩阵最大特征值的复杂网络牵制混沌同步. 物理学报, 2012, 61(3): 038901. doi: 10.7498/aps.61.038901
    [12] 高湘昀, 安海忠, 方伟. 基于复杂网络的时间序列双变量相关性波动研究. 物理学报, 2012, 61(9): 098902. doi: 10.7498/aps.61.098902
    [13] 龚志强, 支蓉, 侯威, 王晓娟, 封国林. 基于复杂网络的北半球遥相关年代际变化特征研究. 物理学报, 2012, 61(2): 029202. doi: 10.7498/aps.61.029202
    [14] 周漩, 张凤鸣, 周卫平, 邹伟, 杨帆. 利用节点效率评估复杂网络功能鲁棒性. 物理学报, 2012, 61(19): 190201. doi: 10.7498/aps.61.190201
    [15] 冯爱霞, 龚志强, 黄琰, 王启光. 全球温度场信息熵的时空特征分析. 物理学报, 2011, 60(9): 099204. doi: 10.7498/aps.60.099204
    [16] 张璐, 章大全, 封国林. 中国旱涝极端事件前兆信号及可预测性研究. 物理学报, 2010, 59(8): 5896-5903. doi: 10.7498/aps.59.5896
    [17] 宋青松, 冯祖仁, 李人厚. 用于混沌时间序列预测的多簇回响状态网络. 物理学报, 2009, 58(7): 5057-5064. doi: 10.7498/aps.58.5057
    [18] 郭进利. 新节点的边对网络无标度性影响. 物理学报, 2008, 57(2): 756-761. doi: 10.7498/aps.57.756
    [19] 王启光, 支 蓉, 张增平. Lorenz系统长程相关性研究. 物理学报, 2008, 57(8): 5343-5350. doi: 10.7498/aps.57.5343
    [20] 郭进利. 供应链型网络中双幂律分布模型. 物理学报, 2006, 55(8): 3916-3921. doi: 10.7498/aps.55.3916
计量
  • 文章访问数:  8742
  • PDF下载量:  316
  • 被引次数: 0
出版历程
  • 收稿日期:  2019-11-03
  • 修回日期:  2020-02-27
  • 刊出日期:  2020-04-20

/

返回文章
返回