Optimal path in random networks with disorder: A mini review

Shlomo Havlin, Lidia A. Braunstein, Sergey V. Buldyrev, Reuven Cohen, Tomer Kalisky, Sameet Sreenivasan and H. Eugene Stanley

Physica A: Statistical Mechanics and its Applications, 2005, vol. 346, issue 1, 82-92

Abstract: We review the analysis of the length of the optimal path ℓopt in random networks with disorder (i.e., random weights on the links). In the case of strong disorder, in which the maximal weight along the path dominates the sum, we find that ℓopt increases dramatically compared to the known small-world result for the minimum distance ℓmin: for Erdős–Rényi (ER) networks ℓopt∼N1/3, while for scale-free (SF) networks, with degree distribution P(k)∼k-λ, we find that ℓopt scales as N(λ-3)/(λ-1) for 3<λ<4 and as N1/3 for λ⩾4. Thus, for these networks, the small-world nature is destroyed. For 2<λ<3, our numerical results suggest that ℓopt scales as lnλ-1N. We also find numerically that for weak disorder ℓopt∼lnN for ER models as well as for SF networks. We also study the transition between the strong and weak disorder regimes in the scaling properties of the average optimal path ℓopt in ER and SF networks.

Keywords: Networks; Optimal path; Strong disorder (search for similar items in EconPapers)
Date: 2005
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0378437104011653
Full text for ScienceDirect subscribers only. Journal offers the option of making the article available online on Science direct for a fee of $3,000

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:phsmap:v:346:y:2005:i:1:p:82-92

DOI: 10.1016/j.physa.2004.08.053

Access Statistics for this article

Physica A: Statistical Mechanics and its Applications is currently edited by K. A. Dawson, J. O. Indekeu, H.E. Stanley and C. Tsallis

More articles in Physica A: Statistical Mechanics and its Applications from Elsevier
Bibliographic data for series maintained by Catherine Liu ().