pathgephi

how gephi count the average path length

problem description

I want to know the formula to compute the average path length in the directed graph in Gephi, as the formula in wikipedia is

formula.png

but it seemed the calculate result is different from the gephi, for example,if I have a simple directed graph figure_1-1.png * Node : A,B,C,D * Edge: (A->B),(B->C),(B->D) and if I count the average shortest path length by the formula above I will get a result of 0.583 by hand(which is the same as I count by Python NetworkX),but the gephi gave a result of 1.4 which make me comfused QQ截图20170304152129.jpg

I search the wiki but it didn't give the formula and the reference for the implement algorithm does not work, so I wonder how gephi count the average path length, is it the same as average shortest path length?

Any help is appreciated, thank you

Environment

Solution

  • The definition is a bit puzzling I have to say, because it counts in the denominator, all possible vertex pairs. In practice though, not all vertex pairs can produce a valid path.

    Gephi has a slightly different logic and counts that number of the actual paths in the denominator. I found it out by looking at the code here. What they do is that they count for each node the distance from every other node and they add all distances together. They divide this sum with the total number of paths (in your case this is 5). Now the distances for every node are the following:

    A: 0
B: 1 (reachable only from A)
C: 2 (from A), 1 (from B)
D: 2 (from A), 1 (from B)

    Now average path length = (0+1+2+1+2+1)/5 = 1.4