Average Shortest Path Length below 1 ?

24 views
Skip to first unread message

Gordon Julian Köhn

unread,
Jul 22, 2022, 9:42:05 AMJul 22
to networkx-discuss
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

unread,
Jul 22, 2022, 10:35:20 AMJul 22
to networkx...@googlegroups.com
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

unread,
Jul 25, 2022, 4:47:02 PMJul 25
to networkx-discuss
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

unread,
Jul 25, 2022, 7:04:26 PMJul 25
to networkx...@googlegroups.com
Yes, that is correct. Nodes that cannot be connected are counted as distance 0 when getting the numerator of the average shortest path.
Reply all
Reply to author
Forward
0 new messages