# 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?

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)?
– Xara
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. 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).$

• I think this doesn't match exactly the given definition, since you are taking the mean of any shortest path, instead of taking the mean for every vertex each, and then the median. Dec 21 '12 at 13:31
• As far as I know this is how CPL is defined. See for example page 4 here google.com/… Dec 21 '12 at 14:41
• @SimonS None of the definitions I saw matches that given by the OP. See for example this and this. Dec 21 '12 at 14:48
• Well I am more confused now because in some definitions they are taking median and in some they are not.
– Xara
Dec 21 '12 at 14:56
• @Zara Can you also provide a link to that definition in your question, so that people can read and answer in the right context. Dec 21 '12 at 14:58