CODEWITHSUNDEEP
python-3.xgraphgraph-tool
Peaceful
Peaceful

Reputation: 5450

How can I calculate the average path length of the graph efficiently in graph-tool?

I am dealing with networks of the order of 10000 vertices and I am using graph-tool to analyze them. One of the things that I want to calculate for each of these graphs is the average path length which is defined as the average of the shortest distances over all the pairs of nodes in the graph. So I tried this:

ave_path_length = 0
tot = 0

for v1 in G.vertices():
    print(v1)
    for v2 in G.vertices():
        if v1 != v2 :
            tot += 1
            ave_path_length += gt.shortest_distance(G, v1, v2)

ave_path_length /= tot

However, this is taking eternity. Is there a better method to achieve the task? Thanks in advance.

Upvotes: 1

Views: 3829

Answers (3)

Peaceful
Peaceful

Reputation: 5450

I found a much efficient way to achieve this. One can do this:

import graph_tool.all as gt
dist = gt.shortest_distance(G)
ave_path_length = sum([sum(i) for i in dist])/(G.num_vertices()**2-G.num_vertices())

This takes only few seconds for sparse networks of size 10000. However, I am still curious as whether a better method exists.

Upvotes: 1

ssm
ssm

Reputation: 640

Can you do,

all_sp = gt.shortest_distance(G)
vertex_avgs = graph_tool.stats.vertex_average(G, all_sp)
avg_path = numpy.mean(vertex_avgs[0])

I haven't tried this, but this should work.

Upvotes: 1

Jean-François Fabre
Jean-François Fabre

Reputation: 140168

you can cut the time by 2 by using the fact that distance(v1,v2) == distance(v2,v1). So compute only the half of the values (and divide by half too, but that's handled automatically)

vert = G.vertices()  # not sure it is a list. If not just convert to a list first
for i,v1 in enumerate(vert):
    for j in range(i+1,len(vert)):
        tot += 1
        ave_path_length += gt.shortest_distance(G, v1, vert[j])

ave_path_length /= tot

apart from that, you could avoid computing tot:

tot = (len(vert)-1)*(len(vert)-2)//2

Upvotes: 0

Related Questions