-
Identifying the most important nodes, or ranking the node importance by using the method of quantitative analysis in large scale networks are important problems in the complex networks. In this article, the metrics for node importance ranking in complex networks are reviewed and the latest progresses in this field are summarized from two prospects: the network structure and the spreading dynamics. The merits, weaknesses and applicable conditions of different node importance ranking metrics are analyzed. Finally, several important open problems are outlined as possible future directions.
-
Keywords:
- complex networks /
- node importance /
- network structure /
- spreading dynamics
[1] Albert R, Barabasi A L 2002 Rev. Mod. Phys. 74 47
[2] Newman M E J 2003 SIAM Rev. 45 167
[3] L L Y, Medo M, Yeung C H, Zhang Y C, Zhang Z K, Zhou T 2012 Phys. Rep. 519 1
[4] Wang B H, Zhou T, Wang W X, Yang H J, Liu J G, Zhao M, Yin C Y, Han X P, Xie Y B 2008 Complex System and Complex Science 5 21 (in Chinese) [汪秉宏, 周涛, 王文旭, 杨会杰, 刘建国, 赵明, 殷传洋, 韩筱璞, 谢彦波 2008 复杂系统与复杂性科学 5 21]
[5] Li X, Liu Z H, Wang B 2010 Complx System and Complex Science 7 34 (in Chinese) [李翔, 刘宗华, 汪秉宏 2010 复杂系统与复杂性科学 7 34]
[6] Rong Z H, Tang M, Wang X F, Wu Z X, Yan G, Zhou T 2012 Journal of University of Electronic Science and Technology of China 41 801 (in Chinese) [荣智海, 唐明, 汪小帆, 吴枝喜, 严钢, 周涛 2012 电子科技大学学报 41 801]
[7] Dorogovtsev S N, Mendes J F F, Samukhin A N 2000 Phys. Rev. Lett. 85 4633
[8] Eagle N, Macy M, Claxton R 2010 Science 328 1029
[9] Papadopoulos F, Kitsak M, Serrano M A, Boguna M, Krioukov D 2012 Nature 489 537
[10] Pinto P C, Thiran P, Vetterli M 2012 Phys. Rev. Lett. 109 068702
[11] Ghoshal G, Barabasi A L 2011 Nat. Commun. 2 394
[12] Goltsev A V, Dorogovtsev S N, Oliveira J G, Mendes J F F 2012 Phys. Rev. Lett. 109 128702
[13] Wang L, Zhang J J 2006 Complex System and Complex Science 3 13 (in Chinese) [王林, 张婧婧 2006 复杂系统与复杂性科学 3 13]
[14] He N, Li D, Gan W Y, Zhu X 2007 Computer Science 34 1 (in Chinese) [赫南, 李德, 淦文燕, 朱熙 2007 计算机科学 34 1]
[15] Sun R, Luo W B 2012 Application Research of Computers 29 3606 (in Chinese) [孙睿, 罗万伯 2012 计算机应用研究 29 3606]
[16] Kitsak M, Gallos L K, Havlin S, Liljeros F, Muchnik L, Stanley H E, Makse H A 2010 Nat. Phys. 6 888
[17] Tan Y J, Yu J, Deng H Z, Zhu D Z 2006 Systems Engineering 24 1 (in Chinese) [谭跃进, 吴俊, 邓宏钟, 朱大智 2006 系统工程 24 1]
[18] Liu J, Wang Z, Dang Y 2006 Mod. Phys. Lett. B 20 815
[19] Vragovic I, Louis E, Diaz-Guilera A 2005 Phys. Rev. E 71 036122
[20] Latora V, Marchiori M A 2007 New J. Phys. 9 188
[21] Newman M E J 2010 Networks An Introduction (New York: Oxford University Press) p 168-169
[22] Wang J W, Rong L L, Guo T Z 2010 Journal of Dalian University of Technology 50 822 (in Chinese) [王建伟, 荣莉莉, 郭天柱 2010 大连理工大学学报 50 822]
[23] Chen D B, L L Y, Shang M S, Zhang Y C, Zhou T 2012 Physica A 391 1777
[24] Ren Z M, Shao F, Liu J G, Guo Q, Wang B H 2013 Acta Phys. Sin. 62 128901 (in Chinese) [任卓明, 邵凤, 刘建国, 郭强, 汪秉宏 2013 物理学报 62 128901]
[25] Centola D 2010 Science 329 1194
[26] Ugander J, Backstrom L, Marlow C, Kleinberg J 2012 Proc Natl. Acad. Sci. USA 109 5962
[27] Stephenson K, Zelen M 1989 Soc. Netw. 1 11
[28] Borgatti S P 2005 Soc. Netw. 27 55
[29] Poulin R, Boily M C, Massea B R 2000 Soc. Netw. 22 187
[30] Katz L 1953 Psychometrika 18 39
[31] Sabidussi G 1966 Psyehometrika 31 581
[32] Zhang J, Xu X K, Li P, Zhang K, Small M 2011 Chaos 21 016107
[33] Huang X Q, Vodenska I, Wang F Z, Havlin S, Stanley H E 2011 Phys. Rev. E 84 046101
[34] Freeman L 1977 Sociometry 40 35
[35] Zhou T, Liu J, Wang B H 2006 Chin. Phys. Lett. 23 2327
[36] Travencolo B A N, Costa L D 2008 Phys. Lett. A 373 89
[37] Comin C H, Costa L D 2011 Phys. Rev. E 84 056105
[38] Li P X, Ren Y Q, Xi Y M 2004 Systems Engineering 22 13 (in Chinese) [李鹏翔, 任玉晴, 席酉民 2004 系统工程 22 13]
[39] Tan Y J, Wu J, Deng H Z 2006 Sytems Engineering-Theory and Practice 788 79 (in Chinese) [谭跃进, 吴俊, 邓宏钟 2006 系统工程理论与实践 788 79]
[40] Yu X, Li Y H, Zheng X P, Zhang H Y, Guo Y L 2008 Journal of Tsinghua University (Science and Technology) 48 541 (in Chinese) [余新, 李艳和, 郑小平, 张汉一, 郭奕理 2008 清华大学学报(自然科学版) 48 541]
[41] Rao Y P, Lin J Y, Yue D F 2009 Computer Engineering 35 14 (in Chinese) [饶育萍, 林竞焉, 月东方 2009 计算机工程 35 14]
[42] Chen K Q, Li S W, Zhou J 2010 Computer Engineering and Applications 46 95 (in Chinese) [程克勤, 李世伟, 周健 2010 计算机工程与应用 46 95]
[43] Carmi S, Havlin S, Kirkpatrick S, Shavitt Y, Shir E 2007 Proc. Natl. Acad. Sci. USA 104 11150
[44] Zeng A, Zhang C J 2013 Phys. Lett. A 377 1031
[45] Garas A, Schweitzer F, Havlin S 2012 New J. Phys. 14 083030
[46] Liu J G, Ren Z M, Guo Q 2013 Physica A 392 4154
[47] Ren Z M, Liu J G, Shao F, Guo Q 2013 Acta Phys. Sin. 62 108902 (in Chinese) [任卓明, 刘建国, 邵凤, 郭强, 汪秉宏 2013 物理学报 62 108902]
[48] Hou B N, Yao Y P, Liao D S 2012 Physica A 391 4012
[49] Bryan K, Leise T 2006 SIAM Rev. 48 569
[50] Berkhin P 2005 Int. Math. 2 73
[51] L L Y, Zhang Y C, Yeung C H, Zhou T 2011 PLoS One 6 e21202
[52] Kleinberg J M 1999 ACM 46 604
[53] Radicchi F, Fortunato S, Markines B, Vespignani A 2009 Phys. Rev. E 80 056103
[54] Radicchi F 2011 PLoS One 6 e17249
[55] Masuda N, Kori H 2010 Phys. Rev. E 82 056107
[56] Chen Y, Hu A Q, Hu X 2004 Journal of China Institute of Communications 25 129 (in Chinese) [陈勇, 胡爱群, 胡啸 2004 通信学报 25 129]
[57] An S H, Nie P R, He G G 2006 Journal of Management Sciences in China 9 37 (in Chinese) [安世虎, 聂培尧, 贺国光 2006 管理科学学报 9 37]
[58] Wu J, Tan Y J, Deng H Z, Chi Y 2007 Journal of Chinese Computer Systems 28 627 (in Chinese) [吴俊, 谭跃进, 邓宏钟, 迟妍 2007 小型微型计算机系统 28 627]
[59] Chen J, Sun L F 2009 Journal of Southwest Jiaotong University 44 426 (in Chinese) [陈静, 孙林夫 2009 西南交通大学学报 44 426]
[60] Xiao L J, Wu J N, Xuan Z G 2010 Science of Science and Management of S&T 241 12 (in Chinese) [肖连杰, 吴江宁, 宣照国 2010 科学学与科学技术管理 241 12]
[61] Ye C S, Wang C L, Liu H W 2010 Statistics and Decision 301 22 (in Chinese) [叶春森, 汪传雷, 刘宏伟 2010 统计与决策 301 22]
[62] Zhou X, Zhang F M, Li K W, Hui X B, Wu H S 2012 Acta Phys. Sin. 61 050201 (in Chinese) [周漩, 张凤鸣, 李克武, 惠晓滨, 吴虎胜 2012 物理学报 61 050201]
[63] Yan G, Zhou T, Wang J, Fu Z Q, Wang B H 2005 Chinese Phys. Lett. 22 510
[64] Borge-Holthoefer J, Rivero A, Moreno Y 2012 Phys. Rev. E 85 066123
[65] Borge-Holthoefer J, Moreno Y 2012 Phys. Rev. E 85 026116
[66] Klemm K, Serrano M A, Eguiluz V M, San Miguel M 2012 Sci. Rep. 2 292
[67] Aral S, Walker D 2012 Science 337 337
[68] Liu J, Wu Z X, Wang F 2007 Int. J. Mod. Phys. C 18 1087
[69] Silva R A P, Viana M P, Costa L 2012 J. Stat. Mech. 7 P07005
[70] Bond R M, Fariss C J, Jones J J, Kramer A D, Marlow C, Settle J E, Fowler J H 2012 Nature 489 295
[71] Holme P, Saramaki J 2012 Phys. Rep. 519 97 ewpage
[72] Takaguchi T, Sato N, Yano K, Masuda N 2012 New J. Phys. 14 093003
[73] Kim H, Anderson R 2012 Phys. Rev. E 85 026107
-
[1] Albert R, Barabasi A L 2002 Rev. Mod. Phys. 74 47
[2] Newman M E J 2003 SIAM Rev. 45 167
[3] L L Y, Medo M, Yeung C H, Zhang Y C, Zhang Z K, Zhou T 2012 Phys. Rep. 519 1
[4] Wang B H, Zhou T, Wang W X, Yang H J, Liu J G, Zhao M, Yin C Y, Han X P, Xie Y B 2008 Complex System and Complex Science 5 21 (in Chinese) [汪秉宏, 周涛, 王文旭, 杨会杰, 刘建国, 赵明, 殷传洋, 韩筱璞, 谢彦波 2008 复杂系统与复杂性科学 5 21]
[5] Li X, Liu Z H, Wang B 2010 Complx System and Complex Science 7 34 (in Chinese) [李翔, 刘宗华, 汪秉宏 2010 复杂系统与复杂性科学 7 34]
[6] Rong Z H, Tang M, Wang X F, Wu Z X, Yan G, Zhou T 2012 Journal of University of Electronic Science and Technology of China 41 801 (in Chinese) [荣智海, 唐明, 汪小帆, 吴枝喜, 严钢, 周涛 2012 电子科技大学学报 41 801]
[7] Dorogovtsev S N, Mendes J F F, Samukhin A N 2000 Phys. Rev. Lett. 85 4633
[8] Eagle N, Macy M, Claxton R 2010 Science 328 1029
[9] Papadopoulos F, Kitsak M, Serrano M A, Boguna M, Krioukov D 2012 Nature 489 537
[10] Pinto P C, Thiran P, Vetterli M 2012 Phys. Rev. Lett. 109 068702
[11] Ghoshal G, Barabasi A L 2011 Nat. Commun. 2 394
[12] Goltsev A V, Dorogovtsev S N, Oliveira J G, Mendes J F F 2012 Phys. Rev. Lett. 109 128702
[13] Wang L, Zhang J J 2006 Complex System and Complex Science 3 13 (in Chinese) [王林, 张婧婧 2006 复杂系统与复杂性科学 3 13]
[14] He N, Li D, Gan W Y, Zhu X 2007 Computer Science 34 1 (in Chinese) [赫南, 李德, 淦文燕, 朱熙 2007 计算机科学 34 1]
[15] Sun R, Luo W B 2012 Application Research of Computers 29 3606 (in Chinese) [孙睿, 罗万伯 2012 计算机应用研究 29 3606]
[16] Kitsak M, Gallos L K, Havlin S, Liljeros F, Muchnik L, Stanley H E, Makse H A 2010 Nat. Phys. 6 888
[17] Tan Y J, Yu J, Deng H Z, Zhu D Z 2006 Systems Engineering 24 1 (in Chinese) [谭跃进, 吴俊, 邓宏钟, 朱大智 2006 系统工程 24 1]
[18] Liu J, Wang Z, Dang Y 2006 Mod. Phys. Lett. B 20 815
[19] Vragovic I, Louis E, Diaz-Guilera A 2005 Phys. Rev. E 71 036122
[20] Latora V, Marchiori M A 2007 New J. Phys. 9 188
[21] Newman M E J 2010 Networks An Introduction (New York: Oxford University Press) p 168-169
[22] Wang J W, Rong L L, Guo T Z 2010 Journal of Dalian University of Technology 50 822 (in Chinese) [王建伟, 荣莉莉, 郭天柱 2010 大连理工大学学报 50 822]
[23] Chen D B, L L Y, Shang M S, Zhang Y C, Zhou T 2012 Physica A 391 1777
[24] Ren Z M, Shao F, Liu J G, Guo Q, Wang B H 2013 Acta Phys. Sin. 62 128901 (in Chinese) [任卓明, 邵凤, 刘建国, 郭强, 汪秉宏 2013 物理学报 62 128901]
[25] Centola D 2010 Science 329 1194
[26] Ugander J, Backstrom L, Marlow C, Kleinberg J 2012 Proc Natl. Acad. Sci. USA 109 5962
[27] Stephenson K, Zelen M 1989 Soc. Netw. 1 11
[28] Borgatti S P 2005 Soc. Netw. 27 55
[29] Poulin R, Boily M C, Massea B R 2000 Soc. Netw. 22 187
[30] Katz L 1953 Psychometrika 18 39
[31] Sabidussi G 1966 Psyehometrika 31 581
[32] Zhang J, Xu X K, Li P, Zhang K, Small M 2011 Chaos 21 016107
[33] Huang X Q, Vodenska I, Wang F Z, Havlin S, Stanley H E 2011 Phys. Rev. E 84 046101
[34] Freeman L 1977 Sociometry 40 35
[35] Zhou T, Liu J, Wang B H 2006 Chin. Phys. Lett. 23 2327
[36] Travencolo B A N, Costa L D 2008 Phys. Lett. A 373 89
[37] Comin C H, Costa L D 2011 Phys. Rev. E 84 056105
[38] Li P X, Ren Y Q, Xi Y M 2004 Systems Engineering 22 13 (in Chinese) [李鹏翔, 任玉晴, 席酉民 2004 系统工程 22 13]
[39] Tan Y J, Wu J, Deng H Z 2006 Sytems Engineering-Theory and Practice 788 79 (in Chinese) [谭跃进, 吴俊, 邓宏钟 2006 系统工程理论与实践 788 79]
[40] Yu X, Li Y H, Zheng X P, Zhang H Y, Guo Y L 2008 Journal of Tsinghua University (Science and Technology) 48 541 (in Chinese) [余新, 李艳和, 郑小平, 张汉一, 郭奕理 2008 清华大学学报(自然科学版) 48 541]
[41] Rao Y P, Lin J Y, Yue D F 2009 Computer Engineering 35 14 (in Chinese) [饶育萍, 林竞焉, 月东方 2009 计算机工程 35 14]
[42] Chen K Q, Li S W, Zhou J 2010 Computer Engineering and Applications 46 95 (in Chinese) [程克勤, 李世伟, 周健 2010 计算机工程与应用 46 95]
[43] Carmi S, Havlin S, Kirkpatrick S, Shavitt Y, Shir E 2007 Proc. Natl. Acad. Sci. USA 104 11150
[44] Zeng A, Zhang C J 2013 Phys. Lett. A 377 1031
[45] Garas A, Schweitzer F, Havlin S 2012 New J. Phys. 14 083030
[46] Liu J G, Ren Z M, Guo Q 2013 Physica A 392 4154
[47] Ren Z M, Liu J G, Shao F, Guo Q 2013 Acta Phys. Sin. 62 108902 (in Chinese) [任卓明, 刘建国, 邵凤, 郭强, 汪秉宏 2013 物理学报 62 108902]
[48] Hou B N, Yao Y P, Liao D S 2012 Physica A 391 4012
[49] Bryan K, Leise T 2006 SIAM Rev. 48 569
[50] Berkhin P 2005 Int. Math. 2 73
[51] L L Y, Zhang Y C, Yeung C H, Zhou T 2011 PLoS One 6 e21202
[52] Kleinberg J M 1999 ACM 46 604
[53] Radicchi F, Fortunato S, Markines B, Vespignani A 2009 Phys. Rev. E 80 056103
[54] Radicchi F 2011 PLoS One 6 e17249
[55] Masuda N, Kori H 2010 Phys. Rev. E 82 056107
[56] Chen Y, Hu A Q, Hu X 2004 Journal of China Institute of Communications 25 129 (in Chinese) [陈勇, 胡爱群, 胡啸 2004 通信学报 25 129]
[57] An S H, Nie P R, He G G 2006 Journal of Management Sciences in China 9 37 (in Chinese) [安世虎, 聂培尧, 贺国光 2006 管理科学学报 9 37]
[58] Wu J, Tan Y J, Deng H Z, Chi Y 2007 Journal of Chinese Computer Systems 28 627 (in Chinese) [吴俊, 谭跃进, 邓宏钟, 迟妍 2007 小型微型计算机系统 28 627]
[59] Chen J, Sun L F 2009 Journal of Southwest Jiaotong University 44 426 (in Chinese) [陈静, 孙林夫 2009 西南交通大学学报 44 426]
[60] Xiao L J, Wu J N, Xuan Z G 2010 Science of Science and Management of S&T 241 12 (in Chinese) [肖连杰, 吴江宁, 宣照国 2010 科学学与科学技术管理 241 12]
[61] Ye C S, Wang C L, Liu H W 2010 Statistics and Decision 301 22 (in Chinese) [叶春森, 汪传雷, 刘宏伟 2010 统计与决策 301 22]
[62] Zhou X, Zhang F M, Li K W, Hui X B, Wu H S 2012 Acta Phys. Sin. 61 050201 (in Chinese) [周漩, 张凤鸣, 李克武, 惠晓滨, 吴虎胜 2012 物理学报 61 050201]
[63] Yan G, Zhou T, Wang J, Fu Z Q, Wang B H 2005 Chinese Phys. Lett. 22 510
[64] Borge-Holthoefer J, Rivero A, Moreno Y 2012 Phys. Rev. E 85 066123
[65] Borge-Holthoefer J, Moreno Y 2012 Phys. Rev. E 85 026116
[66] Klemm K, Serrano M A, Eguiluz V M, San Miguel M 2012 Sci. Rep. 2 292
[67] Aral S, Walker D 2012 Science 337 337
[68] Liu J, Wu Z X, Wang F 2007 Int. J. Mod. Phys. C 18 1087
[69] Silva R A P, Viana M P, Costa L 2012 J. Stat. Mech. 7 P07005
[70] Bond R M, Fariss C J, Jones J J, Kramer A D, Marlow C, Settle J E, Fowler J H 2012 Nature 489 295
[71] Holme P, Saramaki J 2012 Phys. Rep. 519 97 ewpage
[72] Takaguchi T, Sato N, Yano K, Masuda N 2012 New J. Phys. 14 093003
[73] Kim H, Anderson R 2012 Phys. Rev. E 85 026107
Catalog
Metrics
- Abstract views: 17066
- PDF Downloads: 6757
- Cited By: 0