Optimal Paths in Disordered Complex Networks

Abstract

We study the optimal distance in networks, ${\ell }_{opt}$, defined as the length of the path minimizing the total weight, in the presence of disorder. Disorder is introduced by assigning random weights to the links or nodes. For strong disorder, where the maximal weight along the path dominates the sum, we find that ${\ell }_{opt}\sim N^{1/3}$ in both Erdős-Rényi (ER) and Watts-Strogatz (WS) networks. For scale free (SF) networks, with degree distribution $P(k)\sim k^{-\lambda }$, we find that ${\ell }_{opt}$ scales as $N^{(\lambda -3)/(\lambda -1)}$ for $3<\lambda <4$ and as $N^{1/3}$ for $\lambda \ge 4$. Thus, for these networks, the small-world nature is destroyed. For $2<\lambda <3$, our numerical results suggest that ${\ell }_{opt}$ scales as ${\ln }^{\lambda -1}N$. We also find numerically that for weak disorder ${\ell }_{opt}\sim \ln N$ for both the ER and WS models as well as for SF networks.

5 pages, 4 figures, accepted for publication in Physical Review Letters

References in corpus (8)

• Statistical mechanics of complex networks
• The structure and function of complex networks
• Resilience of the Internet to random breakdowns
• Renormalization group analysis of the small-world network model
• Scale-Free Networks are Ultrasmall
• Small-world networks: Evidence for a crossover picture
• Erratum: Small-world networks: Evidence for a crossover picture
• Minimum spanning trees on random networks

Cited by in corpus (87)

• Epidemic processes in complex networks
• Synchronization in complex networks
• Critical phenomena in complex networks
• Self-similarity of complex networks
• Intensity and coherence of motifs in weighted complex networks
• Efficient routing on complex networks
• Network Synchronization, Diffusion, and the Paradox of Heterogeneity
• Statistical analysis of 22 public transport networks in Poland
• Unification of theoretical approaches for epidemic spreading on complex networks
• How to calculate the fractal dimension of a complex network: the box covering algorithm
• Average path length in random networks
• Average path length in uncorrelated random networks with hidden variables
• Consensus formation on adaptive networks
• Skeleton and fractal scaling in complex networks
• Optimization of Robustness of Complex Networks
• The International Trade Network: weighted network analysis and modelling
• Accuracy and Scaling Phenomena in Internet Mapping
• Traceroute sampling makes random graphs appear to have power law degree distributions
• Transport in weighted networks: Partition into superhighways and roads
• Fractality in complex networks: critical and supercritical skeletons
• Structure of shells in complex networks
• Effective Distances for Epidemics Spreading on Complex Networks
• Formation of feedforward networks and frequency synchrony by spike-timing-dependent plasticity
• Quarantine generated phase transition in epidemic spreading
• Optimal Path and Minimal Spanning Trees in Random Weighted Networks
• Effect of congestion costs on shortest paths through complex networks
• Dynamic networks and directed percolation
• The structural role of weak and strong links in a financial market network
• Universal scaling of distances in complex networks
• Screened non-bonded interactions in native proteins manipulate optimal paths for robust residue communication
• Most probable paths in temporal weighted networks: An application to ocean transport
• First passage percolation on random graphs with finite mean degrees
• Optimal Paths in Complex Networks with Correlated Weights: The World-wide Airport Network
• Width of percolation transition in complex networks
• Localization transition on complex networks via spectral statistics
• Interplay between function and structure in complex networks
• Non-consensus opinion models on complex networks
• Search in weighted complex networks
• Slow epidemic extinction in populations with heterogeneous infection rates
• The shortest path to complex networks
• Fractal Boundaries of Complex Networks
• Current Flow in Random Resistor Networks: The Role of Percolation in Weak and Strong Disorder
• Nonlocal evolution of weighted scale-free networks
• Universal behavior of optimal paths in weighted networks with general disorder
• Satellite-based photonic quantum networks are small-world
• Evolving small-world networks with geographical attachment preference
• Limited path percolation in complex networks
• Percolation properties in a traffic model
• Load distribution in weighted complex networks
• Transport on weighted Networks: when correlations are independent of degree
• Geographical networks evolving with optimal policy
• Effect of Disorder Strength on Optimal Paths in Complex Networks
• Preferential Exchange: Strengthening Connections in Complex Networks
• Extreme first passage times for random walks on networks
• Universality for critical heavy-tailed network models: Metric structure of maximal components
• Transport and Percolation Theory in Weighted Networks
• Contextual analysis framework for bursty dynamics
• Optimization of transport protocols with path-length constraints in complex networks
• The shape of shortest paths in random spatial networks
• Evolution equation for a model of surface relaxation in complex networks
• Minimal models of weighted scale-free networks
• Scale-Free Networks Emerging from Weighted Random Graphs
• Non-consensus opinion model on directed networks
• Simulating SIR processes on networks using weighted shortest paths
• Social distancing strategies against disease spreading
• Scaling behavior of an artificial traffic model on scale-free networks
• Jamming in complex networks with degree correlation
• Two-dimensional small-world networks: navigation with local information
• Quantifying Transient Spreading Dynamics on Networks
• Dynamic perturbation spreading in networks
• 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
• A probabilistic approach to the leader problem in random graphs
• Statistical thermodynamics for choice models on graphs
• Geometry of the minimal spanning tree of a random $3$-regular graph
• Random Walks in Local Dynamics of Network Losses
• Degree distribution of shortest path trees and bias of network sampling algorithms
• Disorder Induced Limited Path Percolation
• Bohman-Frieze processes at criticality and emergence of the giant component
• Inhomogeneous substructures hidden in random networks
• Temporal Correlations of Local Network Losses
• Continuum limit of critical inhomogeneous random graphs
• A Survey of Evolving Models for Weighted Complex Networks based on their Dynamics and Evolution
• Recovery of Interdependent Networks
• Equation of state for agents on graphs
• Scaling limits and universality: Critical percolation on weighted graphs converging to an $L^3$ graphon