pubmed.ncbi.nlm.nih.gov

Ranking stability and super-stable nodes in complex networks - PubMed

  • ️Sat Jan 01 2011

Ranking stability and super-stable nodes in complex networks

Gourab Ghoshal et al. Nat Commun. 2011.

Free article

Abstract

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.

PubMed Disclaimer

Similar articles

Cited by

References

    1. Phys Rev Lett. 2001 Apr 16;86(16):3682-5 - PubMed
    1. Nature. 1999 Jul 8;400(6740):107-9 - PubMed
    1. Nature. 2005 Jun 9;435(7043):814-8 - PubMed
    1. Phys Rev E Stat Nonlin Soft Matter Phys. 2009 Aug;80(2 Pt 2):026107 - PubMed
    1. Proc Natl Acad Sci U S A. 2002 Jun 11;99(12):7821-6 - PubMed

Publication types

MeSH terms

LinkOut - more resources