Ranking stability and super-stable nodes in complex networks

被引:138
作者
Ghoshal, Gourab [1 ,2 ,3 ,4 ]
Barabasi, Albert-Laszlo [1 ,2 ,3 ]
机构
[1] Northeastern Univ, Dept Phys Biol & Comp Sci, Ctr Complex Network Res, Boston, MA 02115 USA
[2] Harvard Univ, Sch Med, Dept Med, Boston, MA 02115 USA
[3] Dana Farber Canc Inst, Ctr Canc Syst Biol, Boston, MA 02115 USA
[4] MIT, Media Lab, Cambridge, MA 02139 USA
关键词
COMMUNITY STRUCTURE; PAGERANK; INTERNET; WEB; IDENTIFICATION;
D O I
10.1038/ncomms1396
中图分类号
O [数理科学和化学]; P [天文学、地球科学]; Q [生物科学]; N [自然科学总论];
学科分类号
07 ; 0710 ; 09 ;
摘要
Pagerank, a network-based diffusion algorithm, has emerged as the leading method to rank web content, ecological species and even scientists. Despite its wide use, it remains unknown how the structure of the network on which it operates affects its performance. Here we show that for random networks the ranking provided by pagerank is sensitive to perturbations in the network topology, making it unreliable for incomplete or noisy systems. In contrast, in scale-free networks we predict analytically the emergence of super-stable nodes whose ranking is exceptionally stable to perturbations. We calculate the dependence of the number of super-stable nodes on network characteristics and demonstrate their presence in real networks, in agreement with the analytical predictions. These results not only deepen our understanding of the interplay between network topology and dynamical processes but also have implications in all areas where ranking has a role, from science to marketing.
引用
收藏
页数:7
相关论文
共 46 条
[1]   Link communities reveal multiscale complexity in networks [J].
Ahn, Yong-Yeol ;
Bagrow, James P. ;
Lehmann, Sune .
NATURE, 2010, 466 (7307) :761-U11
[2]   Statistical mechanics of complex networks [J].
Albert, R ;
Barabási, AL .
REVIEWS OF MODERN PHYSICS, 2002, 74 (01) :47-97
[3]   Internet -: Diameter of the World-Wide Web [J].
Albert, R ;
Jeong, H ;
Barabási, AL .
NATURE, 1999, 401 (6749) :130-131
[4]   Error and attack tolerance of complex networks [J].
Albert, R ;
Jeong, H ;
Barabási, AL .
NATURE, 2000, 406 (6794) :378-382
[5]   Googling Food Webs: Can an Eigenvector Measure Species' Importance for Coextinctions? [J].
Allesina, Stefano ;
Pascual, Mercedes .
PLOS COMPUTATIONAL BIOLOGY, 2009, 5 (09)
[6]  
[Anonymous], 2006, The structure and dynamics of networks
[7]  
[Anonymous], 2007, Scale-Free Networks: Complex Webs in Nature and Technology
[8]   Emergence of scaling in random networks [J].
Barabási, AL ;
Albert, R .
SCIENCE, 1999, 286 (5439) :509-512
[9]   Complex networks: from biology to information technology - Preface [J].
Barrat, A. ;
Boccaletti, S. ;
Caldarelli, G. ;
Chessa, A. ;
Latora, V. ;
Motter, A. E. .
JOURNAL OF PHYSICS A-MATHEMATICAL AND THEORETICAL, 2008, 41 (22)
[10]   The anatomy of a large-scale hypertextual Web search engine [J].
Brin, S ;
Page, L .
COMPUTER NETWORKS AND ISDN SYSTEMS, 1998, 30 (1-7) :107-117