Scaling of optimal-path-lengths distribution in complex networks

Area of Science:

• Network Science
• Statistical Physics
• Graph Theory

Background:

• Optimal path lengths in networks are crucial for understanding information flow and network efficiency.
• Introducing random weights (disorder) to graph links significantly impacts pathfinding.
• Previous studies focused on average path lengths, leaving the distribution of optimal path lengths under disorder less explored.

Purpose of the Study:

• To investigate the distribution of optimal path lengths in random graphs with varying degrees of disorder.
• To propose and validate a universal form for this distribution.
• To elucidate the relationship between disorder strength, percolation, and optimal path length distribution.

Main Methods:

• Assigning link weights using an exponential function with a disorder parameter 'a'.
• Employing numerical simulations on Erdos-Rényi and scale-free graph models.
• Analyzing the distribution of optimal path lengths across different disorder strengths.

Main Results:

• A universal distribution form for optimal path lengths was identified, dependent on (1/p(c)) (l(infinity)/a).
• Numerical simulations supported this universal form for both Erdos-Rényi and scale-free graphs.
• The study demonstrated a clear transition between strong and weak disorder regimes at various network scales.

Conclusions:

• The distribution of optimal path lengths in disordered random graphs exhibits universal behavior.
• This universality is governed by the percolation threshold and the strength of the disorder.
• The findings offer a deeper understanding of network robustness and efficiency under random conditions.