OPTIMAL PATH AND MINIMAL SPANNING TREES IN RANDOM WEIGHTED NETWORKS
Open accessThe DOI matches its Crossref record; 3 of the 3 references it cites were found in a registry or an index.
Abstract
We review results on the scaling of the optimal path length ℓ opt in random networks with weighted links or nodes. We refer to such networks as "weighted" or "disordered" networks. The optimal path is the path with minimum sum of the weights. In strong disorder, where 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 ~ log N, where N is the number of nodes. For Erdős–Rényi (ER) networks ℓ opt ~ N 1/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 N 1/3 for λ ≥ 4. Thus, for these networks, the small-world nature is destroyed. For 2 < λ < 3 in contrary, our numerical results suggest that ℓ opt scales as ln λ-1 N, representing still a small world. We also find numerically that for weak disorder ℓ opt ~ ln N for ER models as well as for SF networks. We also review the transition between the strong and weak disorder regimes in the scaling properties of ℓ opt for ER and SF networks and for a general distribution of weights τ, P(τ). For a weight distribution of the form P(τ) = 1/(aτ) with (τ min < τ < τ max ) and a = ln τ max /τ min , we find that there is a crossover network size N* = N*(a) at which the transition occurs. For N ≪ N* the scaling behavior of ℓ opt is in the strong disorder regime, while for N ≫ N* the scaling behavior is in the weak disorder regime. The value of N* can be determined from the expression ℓ∞(N*) = ap c, where ℓ∞ is the optimal path length in the limit of strong disorder, A ≡ ap c → ∞ and p c is the percolation threshold of the network. We suggest that for any P(τ) the distribution of optimal path lengths has a universal form which is controlled by the scaling parameter Z = ℓ∞/A where [Formula: see text] plays the role of the disorder strength and τ c is defined by [Formula: see text]. In case P(τ) ~ 1/(aτ), the equation for A is reduced to A = ap c. The relation for A is derived analytically and supported by numerical simulations for Erdős–Rényi and scale-free graphs. We also determine which form of P(τ) can lead to strong disorder A → ∞. We then study the minimum spanning tree (MST), which is the subset of links of the network connecting all nodes of the network such that it minimizes the sum of their weights. We show that the minimum spanning tree (MST) in the strong disorder limit is composed of percolation clusters, which we regard as "super-nodes", interconnected by a scale-free tree. The MST is also considered to be the skeleton of the network where the main transport occurs. We furthermore show that the MST can be partitioned into two distinct components, having significantly different transport properties, characterized by centrality — number of times a node (or link) is used by transport paths. One component the superhighways, for which the nodes (or links) with high centrality dominate, corresponds to the largest cluster at the percolation threshold (incipient infinite percolation cluster) which is a subset of the MST. The other component, roads, includes the remaining nodes, low centrality nodes dominate. We find also that the distribution of the centrality for the incipient infinite percolation cluster satisfies a power law, with an exponent smaller than that for the entire MST. We demonstrate the significance identifying the superhighways by showing that one can improve significantly the global transport by improving a very small fraction of the network, the superhighways.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Fibonacci heaps and their uses in improved network optimization algorithms
Fredman, M. L., & Tarjan, R. E. (1987) · Journal of the ACM · doi:10.1145/28869.28874 · Cited by 3,132
Barabási, A.-L., & Bonabeau, E. (2003) · Scientific American · doi:10.1038/scientificamerican0503-60 · Cited by 2,494
Dorogovtsev, S. N., & Mendes, J. F. F. (2003) · doi:10.1093/acprof:oso/9780198515906.001.0001 · Cited by 1,563
Cited by
Cascade of failures in coupled network systems with multiple support-dependence relations
Shao, J., Buldyrev, S. V., Havlin, S., & Stanley, H. E. (2011) · Physical Review E · doi:10.1103/physreve.83.036116 · Cited by 432
Self-citationUnification of theoretical approaches for epidemic spreading on complex networks
Wang, W., Tang, M., Eugene Stanley, H., & Braunstein, L. A. (2017) · Reports on Progress in Physics · doi:10.1088/1361-6633/aa5398 · Cited by 366
Self-citationThe minimum spanning tree: An unbiased method for brain network analysis
Tewarie, P., van Dellen, E., Hillebrand, A., & Stam, C. J. (2015) · NeuroImage · doi:10.1016/j.neuroimage.2014.10.015 · Cited by 345
Competing for Attention in Social Media under Information Overload Conditions
Feng, L., Hu, Y., Li, B., Stanley, H. E., Havlin, S., & Braunstein, L. A. (2015) · PLOS ONE · doi:10.1371/journal.pone.0126090 · Cited by 133
Self-citationSaba, V., Premi, E., Cristillo, V., Gazzina, S., Palluzzi, F., Zanetti, O., Gasparotti, R., Padovani, A., Borroni, B., & Grassi, M. (2019) · Frontiers in Neuroscience · doi:10.3389/fnins.2019.00211 · Cited by 33
Metadata
- Authors
- BRAUNSTEIN, L. A., WU, Z., CHEN, Y., BULDYREV, S. V., KALISKY, T., SREENIVASAN, S., COHEN, R., LÓPEZ, E., HAVLIN, S., & STANLEY, H. E.
- Venue
- International Journal of Bifurcation and Chaos
- Publisher
- World Scientific Pub Co Pte Lt
- Published
- 2007-07
- Volume
- 17
- Issue
- 07
- Pages
- 2215-2255
- ISSN
- 0218-1274 (ISSN-L)
- 1793-6551
- OpenAlex
- W2156119272
- Cited by
- 76
- References
- 3
- FWCI
- 2.47
- Type
- journal article
- Language
- en
- Open access
- green
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: OPTIMAL PATH AND MINIMAL SPANNING TREES IN RANDOM WEIGHTED NETWORKS. https://app.cochat.ai/papers/10.1142/s0218127407018361
- The paper
- BRAUNSTEIN, L. A., WU, Z., CHEN, Y., BULDYREV, S. V., KALISKY, T., SREENIVASAN, S., COHEN, R., LÓPEZ, E., HAVLIN, S., & STANLEY, H. E. (2007). OPTIMAL PATH AND MINIMAL SPANNING TREES IN RANDOM WEIGHTED NETWORKS. International Journal of Bifurcation and Chaos. https://doi.org/10.1142/s0218127407018361
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.