3
$\begingroup$

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?

Improve this question
$\endgroup$
2

2 Answers 2

Reset to default
7
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • $\begingroup$ Is this exactly what I did in the example (mentioned in my question)? $\endgroup$
    – Xara
    Commented Dec 21, 2012 at 15:47
  • 1
    $\begingroup$ 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. $\endgroup$
    – Simon S
    Commented Dec 21, 2012 at 15:56
3
$\begingroup$

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

Improve this answer
$\endgroup$
5
  • 1
    $\begingroup$ 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. $\endgroup$
    – Simon S
    Commented Dec 21, 2012 at 13:31
  • 1
    $\begingroup$ As far as I know this is how CPL is defined. See for example page 4 here google.com/… $\endgroup$
    – Jernej
    Commented Dec 21, 2012 at 14:41
  • 1
    $\begingroup$ @SimonS None of the definitions I saw matches that given by the OP. See for example this and this. $\endgroup$
    – Paresh
    Commented Dec 21, 2012 at 14:48
  • $\begingroup$ Well I am more confused now because in some definitions they are taking median and in some they are not. $\endgroup$
    – Xara
    Commented Dec 21, 2012 at 14:56
  • 2
    $\begingroup$ @Zara Can you also provide a link to that definition in your question, so that people can read and answer in the right context. $\endgroup$
    – Paresh
    Commented Dec 21, 2012 at 14:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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