Universal scaling of distances in complex networks

TLDR

Across diverse networks such as Erdos‑Renyi, scale‑free, collaboration, biological, Internet AS, and public transport, the mean distance between nodes of degrees \(k_i\) and \(k_j\) follows the universal scaling law \(\langle l_{ij}\rangle = A - B\log(k_i k_j)\). The study proposes a simple theory explaining the emergence of this universal distance scaling. The theory links the scaling parameters \(A\) and \(B\) to the mean nearest‑neighbor degree and the network’s clustering coefficient. The scaling law remains valid across several decades of network size.

Abstract

Universal scaling of distances between vertices of Erdos-Renyi random graphs, scale-free Barabasi-Albert models, science collaboration networks, biological networks, Internet Autonomous Systems and public transport networks are observed. A mean distance between two nodes of degrees k_i and k_j equals to <l_{ij}>=A-B log(k_i k_j). The scaling is valid over several decades. A simple theory for the appearance of this scaling is presented. Parameters A and B depend on the mean value of a node degree <k>_nn calculated for the nearest neighbors and on network clustering coefficients.