搜索

x

留言板

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

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

基于自规避随机游走的节点排序算法

段杰明 尚明生 蔡世民 张玉霞

引用本文:
Citation:

基于自规避随机游走的节点排序算法

段杰明, 尚明生, 蔡世民, 张玉霞

A ranking method based on self-avoiding random walk in complex networks

Duan Jie-Ming, Shang Ming-Sheng, Cai Shi-Min, Zhang Yu-Xia
PDF
导出引用
  • 评估复杂网络系统的节点重要性有助于提升其系统抗毁性和结构稳定性. 目前, 定量节点重要性的排序算法通常基于网络结构的中心性指标如度数、介数、紧密度、特征向量等. 然而, 这些算法需要以知晓网络结构的全局信息为前提, 很难在大规模网络中实际应用. 基于自规避随机游走的思想, 提出一种结合网络结构局域信息和标签扩散的节点排序算法. 该算法综合考虑了节点的直接邻居数量及与其他节点之间的拓扑关系, 能够表征其在复杂网络系统中的结构影响力和重要性. 基于三个典型的实际网络, 通过对极大连通系数、网络谱距离数、节点连边数和脆弱系数等评估指标的实验对比, 结果表明提出的算法显著优于现有的依据局域信息的节点排序算法.
    Evaluation of node importance is helpful to improve the invulnerability and robustness of complex networked systems. At present, the classic ranking methods of quantitatively analyzing node importance are based on the centrality measurements of network topology, such as degree, betweenness, closeness, eigenvector, etc. Therefore, they often restrict the unknown topological information and are not convenient to use in large-scale real networked systems. In this paper, according to the idea of self-avoiding random walking, we propose a novel and simplified ranking method integrated with label propagation and local topological information, in which the number of labels that node collects from propagating process quantitatively denotes the ranking order. Moreover, the proposed method is able to characterize the structural influence and importance of node in complex networked system because it comprehensively considers both the direct neighbors of node and the topological relation of node to other ones. Through performing the experiments on three benchmark networks, we obtain interesting results derived from four common evaluating indices, i. e., the coefficient of giant component, the spectral distance, the links of node, and the fragility, which indicate that the proposed method is much more efficient and effective for ranking influential nodes than the acquaintance algorithm.
    • 基金项目: 国家自然科学基金(批准号: 61370150, 61433014, 71490720)和中央高校基本科研业务费(批准号: 2014ZM0079)资助的课题.
    • Funds: Project supported by the National Natural Science Foundation of China (Grant Nos. 61370150, 61433014, 71490720) and the Fundamental Research Funds for the Central Universities, China (Grant No. 2014ZM0079).
    [1]

    Kinney R, Crucitti P, Albert R, Latora V 2005 Eur. Phys. J. B 46 101

    [2]

    Strogatz S H 2001 Nature 410 268

    [3]

    Watts D J, Strogatz S H 1998 Nature 393 440

    [4]

    Barabasi A L, Albert R 1999 Science 286 509

    [5]

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

    [6]

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

    [7]

    Liang Z W, Li J P, Yang F, Petropulu A 2014 Chin. Phys. B 23 098902

    [8]

    Liu J G, Ren Z M, Guo Q, Wang B H 2013 Acta Phys. Sin. 62 178901 (in Chinese) [刘建国, 任卓明, 郭强, 汪秉宏 2013 物理学报 62 178901]

    [9]

    Newman M 2010 Networks: An Introduction (Oxford: Oxford University Press)

    [10]

    Freeman L 1977 Sociometry 40 35

    [11]

    Sabidussi G 1966 Psychometrika 31 581

    [12]

    Stephenson K, Zelen M 1989 Soc. Networks 11 1

    [13]

    Kitsak M, Gallos L K, Havlin S, Liljeros F, Muchnik L, Stanley H E, Makse H A 2010 Nat. Phys. 6 888

    [14]

    Ghoshal G, Barabási A L 2010 Nat. Commun. 2 394

    [15]

    Zhao J, Yu L, Li J R, Zhou P 2015 Chin. Phys. B 24 058904

    [16]

    Chen D, L L, Shang M S, Zhang Y C, Zhou T 2012 Physica A 391 1777

    [17]

    Zhang H F, Li K Z, Fu X C, Wang B H 2009 Chin. Phys. Lett. 26 068901

    [18]

    Cheng X Q, Ren F X, Shen H W, Zhang Z K, Zhou T 2010 J. Stat. Mech. 20 595

    [19]

    Zhao Y X, Huang B, Tang M, Zhang H F, Chen D B 2014 EPL 108 68005

    [20]

    Liu Y, Tang M, Zhou T, Do Y 2015 Sci. Rep. 5 9602

    [21]

    Hu Q, Gao Y, Ma P, Yin Y, Zhang Y, Xing C 2013 Web-Age Information (Berlin: Springer Berlin Heidelberg) pp99-104

    [22]

    Ren X L, L L Y 2014 Chin. Sci. Bull. 59 1175 (in Chinese) [任晓龙, 吕琳媛 2014 科学通报 59 1175]

    [23]

    Cohen R, Havlin S, Ben-Avraham D 2003 Phys. Rev. Lett. 91 247901

    [24]

    Cohen R, Erez K, Ben-Avraham D, Havlin S 2001 Phys. Rev. Lett. 86 3682

    [25]

    Salathé M, Jones J H 2010 PLoS Comput. Biol. 4 e1000736

    [26]

    Albert R, Jeong H, Barabasi A L 2000 Nature 406 378

    [27]

    Muff S, Rao F, Caflisch A 2005 Phys. Rev. E 72 056107

    [28]

    Dorogovtsev S N, Mendes J F 2001 Phys. Rev. Lett. 87 219801

    [29]

    Holme P, Kim B J, Yoon C N, Han S K 2002 Phys. Rev. E 65 056109

    [30]

    Costa L F, Rodrigues F A, Travieso G, Villas Boas P R 2007 Adv. Phys. 56 167

    [31]

    Latora V, Marchiori M 2001 Phys. Rev. Lett. 87 198701

    [32]

    Latora V, Marchiori M 2003 Eur. Phys. J. B 32 249

    [33]

    Moreno Y, Nekovee M, Vespignani A 2004 Phys. Rev. E 69 055101

    [34]

    Newman M E 2002 Phys. Rev. Lett. 89 208701

  • [1]

    Kinney R, Crucitti P, Albert R, Latora V 2005 Eur. Phys. J. B 46 101

    [2]

    Strogatz S H 2001 Nature 410 268

    [3]

    Watts D J, Strogatz S H 1998 Nature 393 440

    [4]

    Barabasi A L, Albert R 1999 Science 286 509

    [5]

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

    [6]

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

    [7]

    Liang Z W, Li J P, Yang F, Petropulu A 2014 Chin. Phys. B 23 098902

    [8]

    Liu J G, Ren Z M, Guo Q, Wang B H 2013 Acta Phys. Sin. 62 178901 (in Chinese) [刘建国, 任卓明, 郭强, 汪秉宏 2013 物理学报 62 178901]

    [9]

    Newman M 2010 Networks: An Introduction (Oxford: Oxford University Press)

    [10]

    Freeman L 1977 Sociometry 40 35

    [11]

    Sabidussi G 1966 Psychometrika 31 581

    [12]

    Stephenson K, Zelen M 1989 Soc. Networks 11 1

    [13]

    Kitsak M, Gallos L K, Havlin S, Liljeros F, Muchnik L, Stanley H E, Makse H A 2010 Nat. Phys. 6 888

    [14]

    Ghoshal G, Barabási A L 2010 Nat. Commun. 2 394

    [15]

    Zhao J, Yu L, Li J R, Zhou P 2015 Chin. Phys. B 24 058904

    [16]

    Chen D, L L, Shang M S, Zhang Y C, Zhou T 2012 Physica A 391 1777

    [17]

    Zhang H F, Li K Z, Fu X C, Wang B H 2009 Chin. Phys. Lett. 26 068901

    [18]

    Cheng X Q, Ren F X, Shen H W, Zhang Z K, Zhou T 2010 J. Stat. Mech. 20 595

    [19]

    Zhao Y X, Huang B, Tang M, Zhang H F, Chen D B 2014 EPL 108 68005

    [20]

    Liu Y, Tang M, Zhou T, Do Y 2015 Sci. Rep. 5 9602

    [21]

    Hu Q, Gao Y, Ma P, Yin Y, Zhang Y, Xing C 2013 Web-Age Information (Berlin: Springer Berlin Heidelberg) pp99-104

    [22]

    Ren X L, L L Y 2014 Chin. Sci. Bull. 59 1175 (in Chinese) [任晓龙, 吕琳媛 2014 科学通报 59 1175]

    [23]

    Cohen R, Havlin S, Ben-Avraham D 2003 Phys. Rev. Lett. 91 247901

    [24]

    Cohen R, Erez K, Ben-Avraham D, Havlin S 2001 Phys. Rev. Lett. 86 3682

    [25]

    Salathé M, Jones J H 2010 PLoS Comput. Biol. 4 e1000736

    [26]

    Albert R, Jeong H, Barabasi A L 2000 Nature 406 378

    [27]

    Muff S, Rao F, Caflisch A 2005 Phys. Rev. E 72 056107

    [28]

    Dorogovtsev S N, Mendes J F 2001 Phys. Rev. Lett. 87 219801

    [29]

    Holme P, Kim B J, Yoon C N, Han S K 2002 Phys. Rev. E 65 056109

    [30]

    Costa L F, Rodrigues F A, Travieso G, Villas Boas P R 2007 Adv. Phys. 56 167

    [31]

    Latora V, Marchiori M 2001 Phys. Rev. Lett. 87 198701

    [32]

    Latora V, Marchiori M 2003 Eur. Phys. J. B 32 249

    [33]

    Moreno Y, Nekovee M, Vespignani A 2004 Phys. Rev. E 69 055101

    [34]

    Newman M E 2002 Phys. Rev. Lett. 89 208701

计量
  • 文章访问数:  5728
  • PDF下载量:  371
  • 被引次数: 0
出版历程
  • 收稿日期:  2015-04-08
  • 修回日期:  2015-06-02
  • 刊出日期:  2015-10-05

/

返回文章
返回