Math Insight

Mean path length definition


In a network, the mean path length is the average shortest path between two nodes.

Let $d_{ij}$ be the length of the shortest path between nodes $i$ and $j$. In a network, the length of a path is the number of edges that the path contains. The shortest path between two points is called geodesic. There will typically be many geodesics between a pair of nodes, but, by definition, they will all have the same length $d_{ij}$.

The mean path length is the average of the shortest path length, averaged over all pairs of nodes. For an undirected graph of $N$ nodes, the mean path length is \begin{gather*} \ell = \frac{1}{N(N-1)} \sum_{i \ne j} d_{ij}, \end{gather*} where the sum is over all pairs of distinct nodes.

If two nodes are disconnected, meaning there is no path between them, then the path length between them in infinite. As a consequence, if a network contains disconnected components (collections of nodes that have no paths between them), then the mean path length $\ell$ also diverges to infinity. One way to avoid this problem is to calculate $\ell$ only from nodes in the largest connected component.