サブロウ丸

サブロウ丸

主にプログラミングと数学

networkit, networkx によるグラフの平均経路長の算出

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 に変えながら実験

f:id:inarizuuuushi:20211129222344p:plain

確かに速くなっていますね.

計測用コード

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")