Average path length

Average path length is a concept in network topology that is defined as the average number of steps along the shortest paths for all possible pairs of network nodes. It is a measure of the efficiency of information or mass transport on a network.

Average path length is one of the three most robust measures of network topology, along with its clustering coefficient and its degree distribution. Some examples are: the average number of clicks which will lead you from one website to another, or the number of people you will have to communicate through, on an average, to contact a complete stranger. It should not be confused with the diameter of the network, which is defined as the longest geodesic, i.e., the longest shortest path between any two nodes in the network (see Distance (graph theory)).

The average path length distinguishes an easily negotiable network from one, which is complicated and inefficient, with a shorter average path length being more desirable. However, the average path length is simply what the path length will most likely be. The network itself might have some very remotely connected nodes and many nodes, which are neighbors of each other.

Consider an unweighted directed graph ${\displaystyle G}$ with the set of vertices ${\displaystyle V}$. Let ${\displaystyle d(v_{1},v_{2})}$, where ${\displaystyle v_{1},v_{2}\in V}$ denote the shortest distance between ${\displaystyle v_{1}}$ and ${\displaystyle v_{2}}$. Assume that ${\displaystyle d(v_{1},v_{2})=0}$ if ${\displaystyle v_{2}}$ cannot be reached from ${\displaystyle v_{1}}$. Then, the average path length ${\displaystyle l_{G}}$ is:

...
Wikipedia