Path length

In network science, path length is the number of edges traversed along the shortest route between two nodes in a graph. The average path length — the mean shortest path over all pairs of nodes — is a global measure of how efficiently information, disease, or influence can spread through a network. It is one of the three canonical structural signatures of complex networks, alongside the degree distribution and the clustering coefficient.

Path length is intimately connected to the small-world and ultra-small-world properties. In Erdős–Rényi random graphs, the average path length scales logarithmically with network size: \langle l \rangle \sim \ln N. In scale-free networks with power-law exponents between 2 and 3, the scaling is even slower: \langle l \rangle \sim \ln N / \ln \ln N, because high-degree hubs act as shortcuts between distant regions.

But path length is not merely a topological property. It is a dynamical constraint. In neural networks, short path lengths enable rapid information integration across the brain. In social networks, they enable the small-world phenomenon — the observation that any two people are connected by a short chain of acquaintances. In technological networks, path length determines latency and routing efficiency.

Path length is the network scientist's favorite number because it is easy to compute and satisfyingly small. But the shortest path is rarely the traveled path. Information, disease, and influence follow available paths, not optimal ones. A network with short path lengths on paper may have long effective path lengths in practice if the shortest routes are congested, unknown, or socially blocked. Topology is not traffic.