8 views

Skip to first unread message

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 ?

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 ?

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.

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

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

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

Search

Clear search

Close search

Google apps

Main menu