0

私は 10000 個の頂点のオーダーのネットワークを扱っており、それらを分析するためにグラフ ツールを使用しています。これらのグラフのそれぞれについて計算したいことの 1 つは、グラフ内のすべてのノードのペアにわたる最短距離の平均として定義される平均パスの長さです。だから私はこれを試しました：

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

しかし、これには永遠の時間がかかります。タスクを達成するためのより良い方法はありますか? 前もって感謝します。

4

3 に答える 3

1

できますか、

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

私はこれを試していませんが、これはうまくいくはずです。

于 2016-10-21T15:46:51.477 に答える
1

これを達成するための非常に効率的な方法を見つけました。これを行うことができます：

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 のまばらなネットワークでは数秒しかかかりません。ただし、より良い方法が存在するかどうかについては、まだ興味があります。

于 2016-09-18T05:02:44.040 に答える
0

という事実を利用することで、時間を 2 短縮できますdistance(v1,v2) == distance(v2,v1)。したがって、値の半分だけを計算します (半分で割っても、それは自動的に処理されます)。

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
于 2016-09-09T08:46:42.303 に答える