networkitが速いらしい
( install pip install networkit
)
内部アルゴリズムはC ++で記述され, openMPによるスレッド並列がなされているようです.
使用される並列数などは networkit.engineering こちらのAPIから確認と設定ができます.
また networkit.nxadapter.nx2nk 関数でnetworkxからnetworkitへのグラフの変換ができるので, 局所的にnetworkitを使うことも簡単ですね.
Package Version ----------------------------- ----------- networkit 9.0 networkx 2.6.3
import networkit as nk import networkx as nx import numpy as np # [nx] generate random graph # [nx] ランダムグラフの作成 n = 1000 p = 0.2 G = nx.gnr_graph(n, p).to_undirected() # [nx] calculate average shortest path length using networkx function # [nx] networkxの関数を用いて平均経路長の算出 aspl_nx = nx.average_shortest_path_length(G) # [nk] cast to networkit graph from networkx one # [nk] networkxからnetworkit グラフへの変換 nkG = nk.nxadapter.nx2nk(G) # [nk] generate All-Pairs Shortest-Paths algorithm instance # [nk] APSPインスタンスの作成 apsp = nk.distance.APSP(nkG) # [nk] initialize for APSP instance # [nk] APSPインスタンス初期化 apsp.run() # [nk] calculate average shortest path length using networkit function # [nk] networkitの関数を用いて平均経路長の算出 aspl_nk = np.tril(apsp.getDistances()).sum() / ( n * (n-1) / 2)
少しだけ補足すると, APSP.getDistances()で全てのノード間の経路長行列D_ijが出力され, 今回は無向(undirected)グラフで作成しているので, この行列は対称行列になります. そのため, np.trilで下三角行列を取り出して, その要素の和をノードペアの個数で割って平均経路長を算出しています.
時間比較 ( in 私のノートPC )
- グラフ生成関数 nx.gnr_graph
- p = 0.2 枝張り確率固定
- ノード数 を 2**i where i = 5 .. 14 に変えながら実験
確かに速くなっていますね.
計測用コード
import networkit as nk import networkx as nx import numpy as np import time import random random.seed(0) ns = [2**i for i in range(5, 14)] nx_times = [] nk_times = [] for n in ns: p = 0.2 G = nx.gnr_graph(n, p).to_undirected() elapsed_time = - time.time() aspl = nx.average_shortest_path_length(G) elapsed_time += time.time() print(f"average shortest path length {aspl:.3f}, elapsed {elapsed_time:.3f}s") nx_times.append(elapsed_time) elapsed_time = - time.time() nkG = nk.nxadapter.nx2nk(G) APSP = nk.distance.APSP(nkG) APSP.run() # execute before .getDistances() aspl = np.tril(APSP.getDistances()).sum() / ( n * (n-1) / 2) elapsed_time += time.time() print(f"average shortest path length {aspl:.3f}, elapsed {elapsed_time:.3f}") nk_times.append(elapsed_time) import matplotlib.pyplot as plt fig, ax = plt.subplots() ax.plot(ns, nx_times, linestyle="--", marker="o", label="network") ax.plot(ns, nk_times, linestyle="--", marker="o", label="networkit") ax.set_xlabel("#nodes") ax.set_ylabel("Time [s]") ax.legend() fig.savefig("tmp.png", bbox_inches="tight")