Proof for the Characteristic Path Length

Question

Where is there proof on the characteristic path length I have been looking online and can't seem to find any? I find the equation a lot however, I don't seem to find any actual proof is there a mathematical paper that can be referenced.

Answer 1

The formula $$ \frac1{|V|(|V|-1)} \sum_{v \in V} \sum_{w \in V \setminus \{v\}} d(v, w) $$ gives us the average of all distances between vertices in the graph. There are $|V|(|V|-1)$ pairs $(v,w)$ of distinct vertices; for each of them, the double sum has a $d(v,w)$ term. Then we divide by $|V|(|V|-1)$ terms to get the average.

For example, in a directed graph with three vertices $x,y,z$, this formula would give us $$ \frac{d(x,y) + d(x,z) + d(y,x) + d(y,z) + d(z,x) + d(z,y)}{6}. $$ If the graph were undirected, then $d(v,w) = d(w,v)$ for every pair of vertices $v,w$. That doesn't make the formula wrong, but it makes it have redundant terms; we could simplify the average in that case to $$ \frac{2d(x,y) + 2d(x,z) + 2d(y,z)}{6} = \frac{d(x,y) + d(x,z) + d(y,z)}{3}. $$ (Of course, in a $3$-vertex graph, all these distances are very boring, but that's not the point.)

The formula doesn't have a proof, as such, because it's the definition of characteristic path length. However, that definition is motivated by wanting to average all distances in the graph.