Scaling of optimal-path-lengths distribution in complex networks

Original · EN

We study the distribution of optimal path lengths in random graphs with random weights associated with each link (``disorder''). With each link i we associate a weight τᵢ = (arᵢ) where rᵢ is a random number taken from a uniform distribution between 0 and 1, and the parameter a controls the strength of the disorder. We suggest, in analogy with the average length of the optimal path, that the distribution of optimal path lengths has a universal form which is controlled by the expression 1/pcℓ∞a, where ℓ∞ is the optimal path length in strong disorder (a → ∞) and pc is the percolation threshold. This relation is supported by numerical simulations for Erdős-Rényi and scale-free graphs. We explain this phenomenon by showing explicitly the transition between strong disorder and weak disorder at different length scales in a single network.