Problem Detail: 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?
Asked By : Xara
Answered By : Simon S
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$.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/7535
