Optimal Path and Minimal Spanning Trees in Random Weighted Networks

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 Erdős-Rényi (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={\ell }_{\infty }/A$ where $A$ plays the role of the disorder strength, and ${\ell }_{\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.

review, accepted at IJBC

References in corpus (10)

• Optimal Paths in Disordered Complex Networks
• Transport in weighted networks: Partition into superhighways and roads
• Scale-free trees: the skeletons of complex networks
• Width of percolation transition in complex networks
• Current Flow in Random Resistor Networks: The Role of Percolation in Weak and Strong Disorder
• Universal behavior of optimal paths in weighted networks with general disorder
• Load distribution in weighted complex networks
• Effect of Disorder Strength on Optimal Paths in Complex Networks
• Resistance distribution in the hopping percolation model
• Scale-Free Networks Emerging from Weighted Random Graphs

Cited by in corpus (34)

• Cascade of failures in coupled network systems with multiple support-dependent relations
• Unification of theoretical approaches for epidemic spreading on complex networks
• Epidemics in partially overlapped multiplex networks
• Competing for Attention in Social Media under Information Overload Conditions
• Structure of shells in complex networks
• Triple Point in Correlated Interdependent Networks
• Betweenness Centrality of Fractal and Non-Fractal Scale-Free Model Networks and Tests on Real Networks
• Intermittent social distancing strategy for epidemic control
• Epidemic Model with Isolation in Multilayer Networks
• Theory of minimum spanning trees I: Mean-field theory and strongly disordered spin-glass model
• Fractal Boundaries of Complex Networks
• Epidemic spreading on modular networks: The fear to declare a pandemic
• Dynamic vaccination in partially overlapped multiplex network
• Triple point induced by targeted autonomization on interdependent scale free networks
• Temporal percolation of the susceptible network in an epidemic spreading
• Cascading failures in interdependent networks with finite functional components
• Universality for critical heavy-tailed network models: Metric structure of maximal components
• Transition from fractal to non-fractal scalings in growing scale-free networks
• Theory of minimum spanning trees II: exact graphical methods and perturbation expansion at the percolation threshold
• Optimization of transport protocols with path-length constraints in complex networks
• Insights into bootstrap percolation: Its equivalence with k-core percolation and the giant component
• Social distancing strategies against disease spreading
• Disease spreading with social distancing: A prevention strategy in disordered multiplex networks
• Controlling distant contacts to reduce disease spreading on disordered complex networks
• Role of bridge nodes in epidemic spreading: Different regimes and crossovers
• Weak disorder in the stochastic mean-field model of distance II
• The multiplicative coalescent, inhomogeneous continuum random trees, and new universality classes for critical random graphs
• Crossover from weak to strong disorder regime in the duration of epidemics
• Geometry of the minimal spanning tree of a random $3$-regular graph
• Scaling limit of dynamical percolation on critical Erdös-Rényi random graphs
• Critical Percolation on Random Networks with Prescribed Degrees
• Scaling limits and universality: Critical percolation on weighted graphs converging to an $L^3$ graphon
• The diameter of the minimum spanning tree of the complete graph with inhomogeneous random weights
• Recovery of Interdependent Networks