如何在图形工具中有效地计算图形的平均路径长度?
How can I calculate the average path length of the graph efficiently in graph-tool?
我正在处理大约 10000 个顶点的网络,我正在使用 graph-tool 来分析它们。我想为这些图中的每一个计算的一件事是平均路径长度,它被定义为图中所有节点对的最短距离的平均值。所以我尝试了这个:
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
然而,这需要永恒。有没有更好的方法来完成任务?提前致谢。
你可以利用 distance(v1,v2) == distance(v2,v1)
的事实将时间缩短 2。所以只计算一半的值(也除以一半,但这是自动处理的)
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
除此之外,您可以避免计算 tot
:
tot = (len(vert)-1)*(len(vert)-2)//2
我找到了一种非常有效的方法来实现这一点。可以这样做:
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())
对于大小为 10000 的稀疏网络,这只需要几秒钟。但是,我仍然很好奇是否存在更好的方法。
你能做到吗,
all_sp = gt.shortest_distance(G)
vertex_avgs = graph_tool.stats.vertex_average(G, all_sp)
avg_path = numpy.mean(vertex_avgs[0])
我还没有尝试过,但这应该可行。
我正在处理大约 10000 个顶点的网络,我正在使用 graph-tool 来分析它们。我想为这些图中的每一个计算的一件事是平均路径长度,它被定义为图中所有节点对的最短距离的平均值。所以我尝试了这个:
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
然而,这需要永恒。有没有更好的方法来完成任务?提前致谢。
你可以利用 distance(v1,v2) == distance(v2,v1)
的事实将时间缩短 2。所以只计算一半的值(也除以一半,但这是自动处理的)
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
除此之外,您可以避免计算 tot
:
tot = (len(vert)-1)*(len(vert)-2)//2
我找到了一种非常有效的方法来实现这一点。可以这样做:
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())
对于大小为 10000 的稀疏网络,这只需要几秒钟。但是,我仍然很好奇是否存在更好的方法。
你能做到吗,
all_sp = gt.shortest_distance(G)
vertex_avgs = graph_tool.stats.vertex_average(G, all_sp)
avg_path = numpy.mean(vertex_avgs[0])
我还没有尝试过,但这应该可行。