Random walks on complex networks - PubMed

Affiliations

• PMID: 15089179
• DOI: 10.1103/PhysRevLett.92.118701

Random walks on complex networks

Jae Dong Noh et al. Phys Rev Lett. 2004.

Abstract

We investigate random walks on complex networks and derive an exact expression for the mean first-passage time (MFPT) between two nodes. We introduce for each node the random walk centrality C, which is the ratio between its coordination number and a characteristic relaxation time, and show that it determines essentially the MFPT. The centrality of a node determines the relative speed by which a node can receive and spread information over the network in a random process. Numerical simulations of an ensemble of random walkers moving on paradigmatic network models confirm this analytical prediction.

Similar articles

• Random walks in weighted networks with a perfect trap: an application of Laplacian spectra.

  Lin Y, Zhang Z. Lin Y, et al. Phys Rev E Stat Nonlin Soft Matter Phys. 2013 Jun;87(6):062140. doi: 10.1103/PhysRevE.87.062140. Epub 2013 Jun 28. Phys Rev E Stat Nonlin Soft Matter Phys. 2013. PMID: 23848660

• Random walks in modular scale-free networks with multiple traps.

  Zhang Z, Yang Y, Lin Y. Zhang Z, et al. Phys Rev E Stat Nonlin Soft Matter Phys. 2012 Jan;85(1 Pt 1):011106. doi: 10.1103/PhysRevE.85.011106. Epub 2012 Jan 3. Phys Rev E Stat Nonlin Soft Matter Phys. 2012. PMID: 22400511

• Random walks on weighted networks.

  Zhang Z, Shan T, Chen G. Zhang Z, et al. Phys Rev E Stat Nonlin Soft Matter Phys. 2013 Jan;87(1):012112. doi: 10.1103/PhysRevE.87.012112. Epub 2013 Jan 14. Phys Rev E Stat Nonlin Soft Matter Phys. 2013. PMID: 23410288

• Estimating mean first passage time of biased random walks with short relaxation time on complex networks.

  Lee ZQ, Hsu WJ, Lin M. Lee ZQ, et al. PLoS One. 2014 Apr 3;9(4):e93348. doi: 10.1371/journal.pone.0093348. eCollection 2014. PLoS One. 2014. PMID: 24699325 Free PMC article.

• How predictable are symptoms in psychopathological networks? A reanalysis of 18 published datasets.

  Haslbeck JMB, Fried EI. Haslbeck JMB, et al. Psychol Med. 2017 Dec;47(16):2767-2776. doi: 10.1017/S0033291717001258. Epub 2017 Jun 19. Psychol Med. 2017. PMID: 28625186 Review.

Cited by

• Consistency and differences between centrality measures across distinct classes of networks.

  Oldham S, Fulcher B, Parkes L, Arnatkevic Iūtė A, Suo C, Fornito A. Oldham S, et al. PLoS One. 2019 Jul 26;14(7):e0220061. doi: 10.1371/journal.pone.0220061. eCollection 2019. PLoS One. 2019. PMID: 31348798 Free PMC article.

• The Switch in a Genetic Toggle System with Lévy Noise.

  Xu Y, Li Y, Zhang H, Li X, Kurths J. Xu Y, et al. Sci Rep. 2016 Aug 19;6:31505. doi: 10.1038/srep31505. Sci Rep. 2016. PMID: 27539010 Free PMC article.

• Generalized Erdős numbers for network analysis.

  Morrison G, Dudte LH, Mahadevan L. Morrison G, et al. R Soc Open Sci. 2018 Aug 29;5(8):172281. doi: 10.1098/rsos.172281. eCollection 2018 Aug. R Soc Open Sci. 2018. PMID: 30224995 Free PMC article.

• [Formula: see text]: ComplexOme-Structural Network Interpreter used to study spatial enrichment in metazoan ribosomes.

  Martinez-Seidel F, Hsieh YC, Walther D, Kopka J, Pereira Firmino AA. Martinez-Seidel F, et al. BMC Bioinformatics. 2021 Dec 20;22(1):605. doi: 10.1186/s12859-021-04510-z. BMC Bioinformatics. 2021. PMID: 34930116 Free PMC article.

• Communication structure of cortical networks.

  da Fontoura Costa L, Batista JL, Ascoli GA. da Fontoura Costa L, et al. Front Comput Neurosci. 2011 Mar 4;5:6. doi: 10.3389/fncom.2011.00006. eCollection 2011. Front Comput Neurosci. 2011. PMID: 21427794 Free PMC article.

Publication types

MeSH terms

LinkOut - more resources

• Full Text Sources

  • American Physical Society