Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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. – Xara Dec 21 '12 at 15:10
up vote 7 down vote accepted

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$.

share|cite|improve this answer
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. – 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).$

share|cite|improve this answer
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. – Simon S Dec 21 '12 at 13:31
As far as I know this is how CPL is defined. See for example page 4 here… – Jernej 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. – Paresh 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. – Paresh Dec 21 '12 at 14:58

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.