OPTIMAL PATH AND MINIMAL SPANNING TREES IN RANDOM WEIGHTED NETWORKS

DOI10.1142/S0218127407018361MaRDI QIDQ3511034zbMATH OpenOpenAlexWikidataFDO

Authors Lidia A. Braunstein, Tomer Kalisky, Sameet Sreenivasan, Reuven Cohen, Eduardo López, Zhenhua Wu, Yi-Ping Chen, S. V. Buldyrev, Shlomo Havlin, H. Eugene Stanley

Publication date 4 July 2008

Published in International Journal of Bifurcation and Chaos in Applied Sciences and Engineering (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/cond-mat/0606338

zbMATH Keywords

optimizationminimum spanning treepercolationscale-free

Mathematics Subject Classification ID

Trees (05C05) Random graphs (graph-theoretic aspects) (05C80) Paths and cycles (05C38) Equilibrium statistical mechanics (82B99)

Abstract: We review results on the scaling of the optimal path length in random networks with weighted links or nodes. In strong disorder we find that the length of the optimal path increases dramatically compared to the known small world result for the minimum distance. For ErdH{o}s-R'enyi (ER) and scale free networks (SF), with parameter $lambda$ ($lambda>3$), we find that the small-world nature is destroyed. We also find numerically that for weak disorder the length of the optimal path scales logaritmically with the size of the networks studied. We also review the transition between the strong and weak disorder regimes in the scaling properties of the length of the optimal path for ER and SF networks and for a general distribution of weights, and suggest that for any distribution of weigths, the distribution of optimal path lengths has a universal form which is controlled by the scaling parameter $Z=el{l}_{infty}/A$ where $A$ plays the role of the disorder strength, and $el{l}_{infty}$ is the length of the optimal path in strong disorder. The relation for $A$ is derived analytically and supported by numerical simulations. We then study the minimum spanning tree (MST) and show that it is composed of percolation clusters, which we regard as "super-nodes", connected by a scale-free tree. We furthermore show that the MST can be partitioned into two distinct components. One component the {it superhighways}, for which the nodes with high centrality dominate, corresponds to the largest cluster at the percolation threshold which is a subset of the MST. In the other component, {it roads}, low centrality nodes dominate. 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.

Recommendations

• On finding a minimum spanning tree in a network with random weights
• scientific article; zbMATH DE number 1984546
• Minimum spanning trees in networks with varying edge weights
• Stochastic minimum spanning trees and related problems
• Minimal spanning trees in undirected networks with exponentially distributed arc weights
• Bounding Distributions for the Weight of a Minimum Spanning Tree in Stochastic Networks
• Shortest paths in random weighted graphs
• A randomly weighted minimum spanning tree with a random cost constraint
• A randomly weighted minimum spanning tree with a random cost constraint

Cites work

• scientific article; zbMATH DE number 5542185 (Why is no real title available?)
• scientific article; zbMATH DE number 50596 (Why is no real title available?)
• scientific article; zbMATH DE number 1776593 (Why is no real title available?)
• scientific article; zbMATH DE number 1866312 (Why is no real title available?)
• A critical point for random graphs with a given degree sequence
• Complex networks: structure and dynamics
• First-passage percolation on the random graph
• Geometry of minimum spanning trees on scale-free networks
• Length of optimal path in random networks with strong disorder
• On the shortest spanning subtree of a graph and the traveling salesman problem
• Statistical mechanics of complex networks
• The Size of the Giant Component of a Random Graph with a Given Degree Sequence

Cited in

(20)

• Weak disorder in the stochastic mean-field model of distance. II
• Universality for critical heavy-tailed network models: metric structure of maximal components
• The path-variance problem on tree networks
• Phase transitions in optimized network models
• Length of optimal path in random networks with strong disorder
• Minimum spanning trees in networks with varying edge weights
• Fast long-range connections in transportation networks
• A probabilistic approach to the leader problem in random graphs
• Spatial Homogeneity Pursuit of Regression Coefficients for Large Datasets
• Scaling limit of dynamical percolation on critical Erdős-Rényi random graphs
• Extracting the sovereigns' CDS market hierarchy: a correlation-filtering approach
• Geometry of the minimal spanning tree of a random 3-regular graph
• The optimal path in an Erdős-Rényi random graph
• Geometry of the minimal spanning tree in the heavy-tailed regime: new universality classes
• scientific article; zbMATH DE number 3852815 (Why is no real title available?)
• Optimal temporal path on spatial decaying networks
• Critical percolation on scale-free random graphs: new universality class for the configuration model
• On finding a minimum spanning tree in a network with random weights
• Information diffusion backbone. From the union of shortest paths to the union of fastest path trees
• The multiplicative coalescent, inhomogeneous continuum random trees, and new universality classes for critical random graphs

Describes a project that uses

Uses Software

• Mathematica

This page was built for publication: OPTIMAL PATH AND MINIMAL SPANNING TREES IN RANDOM WEIGHTED NETWORKS

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3511034)