Effect of Disorder Strength on Optimal Paths in Complex Networks

Abstract

We study the transition between the strong and weak disorder regimes in the scaling properties of the average optimal path ${\ell }_{\mathrm{opt}}$ in a disordered Erdős-Rényi (ER) random network and scale-free (SF) network. Each link $i$ is associated with a weight ${\tau }_i\equiv \exp (a{r}_i)$, where $r_i$ is a random number taken from a uniform distribution between 0 and 1 and the parameter $a$ controls the strength of the disorder. We find that for any finite $a$, there is a crossover network size $N^{\ast }(a)$ at which the transition occurs. For $N\ll N^{\ast }(a)$ the scaling behavior of ${\ell }_{\mathrm{opt}}$ is in the strong disorder regime, with ${\ell }_{\mathrm{opt}}\sim N^{1/3}$ for ER networks and for SF networks with $\lambda \ge 4$, and ${\ell }_{\mathrm{opt}}\sim N^{(\lambda -3)/(\lambda -1)}$ for SF networks with $3<\lambda <4$. For $N\gg N^{\ast }(a)$ the scaling behavior is in the weak disorder regime, with ${\ell }_{\mathrm{opt}}\sim \ln N$ for ER networks and SF networks with $\lambda >3$. In order to study the transition we propose a measure which indicates how close or far the disordered network is from the limit of strong disorder. We propose a scaling ansatz for this measure and demonstrate its validity. We proceed to derive the scaling relation between $N^{\ast }(a)$ and $a$. We find that $N^{\ast }(a)\sim a^3$ for ER networks and for SF networks with $\lambda \ge 4$, and $N^{\ast }(a)\sim a^{(\lambda -1)/(\lambda -3)}$ for SF networks with $3<\lambda <4$.

6 pages, 6 figures. submitted to Phys. Rev. E

References in corpus (6)

• Statistical mechanics of complex networks
• Resilience of the Internet to random breakdowns
• Percolation Critical Exponents in Scale-Free Networks
• Optimal Paths in Disordered Complex Networks
• Minimum spanning trees on random networks
• Universal Behavior of Heavy-Fermion Metals Near a Quantum Critical Point

Cited by in corpus (20)

• Transport in weighted networks: Partition into superhighways and roads
• Fractality in complex networks: critical and supercritical skeletons
• Optimal Path and Minimal Spanning Trees in Random Weighted Networks
• Optimal Paths in Complex Networks with Correlated Weights: The World-wide Airport Network
• 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
• Percolation properties in a traffic model
• Transport and Percolation Theory in Weighted Networks
• Theory of minimum spanning trees II: exact graphical methods and perturbation expansion at the percolation threshold
• Weak disorder asymptotics in the stochastic mean-field model of distance
• The influence of memory in deterministic walks in random media: analytical calculation within a mean field approximation
• Optimization of transport protocols with path-length constraints in complex networks
• Scale-Free Networks Emerging from Weighted Random Graphs
• Simulating SIR processes on networks using weighted shortest paths
• Social distancing strategies against disease spreading
• Weak disorder in the stochastic mean-field model of distance II
• Crossover from weak to strong disorder regime in the duration of epidemics
• Flows on Graphs with Random Capacities
• Inhomogeneous substructures hidden in random networks
• Disorder Induced Limited Path Percolation