Average Shortest Path Length below 1 ?

[Gordon Julian Köhn]

Hey Community, 

I am a little confused as I keep getting an average shortest path length below 1 for my directed scale free graph. It allows self-connections,  but I checked there are not many, enough to cause this. 

a=0.15 # Prob of adding new node with connection --> existing node
b=0.8 # Prob of adding edge from existing node to existing node
g=0.05 # Prob of adding new node with connection <-- existing node

n =250
d_in = 0.2
d_out = 0

G = nx.scale_free_graph(n,alpha = a, beta=b, gamma=g, delta_in=d_in, delta_out=d_out)

nx.average_shortest_path_length(G)
Out[564]: 0.41439357429718876

type(G)
Out[565]: networkx.classes.multidigraph.MultiDiGraph

any idea what is happening ? 

[Dan Schult]

The denominator counts all possible pairs of nodes (in both directions).

So `G=nx.DiGraph([(1, 2)])` gives an average path length of 0.5.  

The treatment for the case of weakly_connected_graphs (that are not 

strongly connected) has never been satisfactory to my mind.

From one perspective, there is no path from 2 to 1 so one might expect the

answer to be infinity. But that's not useful. And the sum of the paths that are

not infinite is potentially useful I guess. In any case, the API chosen for this

function is that we take the sum of the finite length shortest paths and divide

by the number of pairs of nodes in the DiGraph.

This should probably be explained better in the documentation.

It's a question of how you want to handle pairs of nodes where you can't

get from one to the other. 

[Gordon Julian Köhn]

Ah, I see. I did not realise that it would take all those possibilities into account. 

It is also the case that, nodes that can not be connected contribute with 0, right? 

I remember seeing this somewhere (might have been in outdated documentation of networkX or source code.).

Thank you for your lines! - Greatly Appreciated.

Gordon

[Dan Schult]

Yes, that is correct. Nodes that cannot be connected are counted as distance 0 when getting the numerator of the average shortest path.