# Characteristic path length

I am unable to understand that what the characteristic path length (CPL) of a graph is.

In one of its definitions, it is written that

it is defined as the median of the means of the shortest path lengths connecting each vertex to all other vertices.

This is what I understand. Is it right?

Suppose we have 3 nodes A, B and C. A can reach to B and C through different paths. We consider just the two paths, AB and AC. These two are the shortest path lengths from which A can reach to B and C respectively. We will then take the mean of AB and AC. Similarly, we will calculate two more means for B and C like I calculated it for A. In the end, we will take the median of the 3 means.

Am I right?

-
Is this definition from "Small-Worlds: Strong Clustering in Wireless Networks" by Matthias R. Brust and Steffen Rothkugel? Their definition differs from the usual. Do you want an explanation of this particular definition or the usual definition? –  Simon S Dec 21 '12 at 15:01
Well, I need explanation for this particular definition that I mentioned here. –  Zara Dec 21 '12 at 15:10

To get the CPL by this definition you first take the average distance from a certain vertex to any other vertex: $$d_v = {{\sum_{v \ne w} d(v,w)} \over {|V(G)| - 1}}$$ After doing so for every vertex $v \in V(G)$, calculate the median of all previously calculated $d_v$.

-
Is this exactly what I did in the example (mentioned in my question)? –  Zara Dec 21 '12 at 15:47
Yes, assuming the graph only consists of the vertices A,B,C, otherwise calculating the mean for a vertex includes calculating the shortest path to any other node as well. –  Simon S Dec 21 '12 at 15:56
Let $d_G(x,y)$ be the distance between the vertices $x,y \in V(G)$ for a connected graph $G.$ The characteristic path length is then defined as $$\frac{\sum_{x,y \in V(G)} d_G(x,y)}{n(n-1)} = \frac{\sum_{v \in V(G)} \sum_{u \in V(G) \setminus \{v\}} d_G(x,y)} { {n \choose 2}}$$ where $n$ is the number of vertices in $G$ and the sum ranges among all pairs of vertices of $G.$
In more graph theoretical terms the characteristic path length is the Wiener index of $G$ dividied by $n(n-1).$