-
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.
-
Keywords:
- complex networks /
- node ranking /
- self-avoiding random walk /
- local information
[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
Catalog
Metrics
- Abstract views: 6897
- PDF Downloads: 377
- Cited By: 0
下载:
