Stability of shortest paths in complex networks with random edge weights

Abstract

We study shortest paths and spanning trees of complex networks with random edge weights. Edges which do not belong to the spanning tree are inactive in a transport process within the network. The introduction of quenched disorder modifies the spanning tree such that some edges are activated and the network diameter is increased. With analytic random-walk mappings and numerical analysis, we find that the spanning tree is unstable to the introduction of disorder and displays a phase-transition-like behavior at zero disorder strength $\epsilon =0$. In the infinite network-size limit ($N\to \infty$), we obtain a continuous transition with the density of activated edges $\Phi$ growing like $\Phi \sim {\epsilon }^1$ and with the diameter-expansion coefficient ${\rm Y}$ growing like ${\rm Y}\sim {\epsilon }^2$ in the regular network, and first-order transitions with discontinuous jumps in $\Phi$ and ${\rm Y}$ at $\epsilon =0$ for the small-world (SW) network and the Barabási-Albert scale-free (SF) network. The asymptotic scaling behavior sets in when $N\gg N_c$, where the crossover size scales as $N_c\sim {\epsilon }^{-2}$ for the regular network, $N_c\sim \exp [\alpha {\epsilon }^{-2}]$ for the SW network, and $N_c\sim \exp [\alpha |\ln \epsilon |{\epsilon }^{-2}]$ for the SF network. In a transient regime with $N\ll N_c$, there is an infinite-order transition with $\Phi \sim {\rm Y}\sim \exp [-\alpha /({\epsilon }^2\ln N)]$ for the SW network and $\sim \exp [-\alpha /({\epsilon }^2\ln N/\ln \ln N)]$ for the SF network. It shows that the transport pattern is practically most stable in the SF network.

9 pages, 7 figure

Cited by in corpus (23)

• The structure and dynamics of multilayer networks
• Analysis of weighted networks
• Exact scaling properties of a hierarchical network model
• Spectral dimensions of hierarchical scale-free networks with shortcuts
• A Parameterized Centrality Metric for Network Analysis
• Weight-driven growing networks
• Search in weighted complex networks
• Nonlocal evolution of weighted scale-free networks
• Load distribution in weighted complex networks
• The Competition for Shortest Paths on Sparse Graphs
• Effect of shortest path multiplicity on congestion of multiplex networks
• Time-Varying Graphs and Social Network Analysis: Temporal Indicators and Metrics
• Condensation transitions in a model for a directed network with weighted links
• Statistics of Weighted Networks
• Minimal models of weighted scale-free networks
• Heider Balance under Disordered Triadic Interactions
• Centrality Metric for Dynamic Networks
• The Futility of Being Selfish -- The Impact of Selfish Routing on Uncoordinated and Optimized Transportation Networks
• Strength Distribution in Derivative Networks
• Optimal transport with constraints: from mirror descent to classical mechanics
• Individual versus Social Benefit on the Heterogeneous Networks
• Degree weighted recurrence networks for the analysis of time series data
• Random Walks on Complex Networks