networkit, networkx によるグラフのクラスタ係数の算出

networkit と networkxのクラスタ係数算出関数の比較

networkx ... networkx.algorithms.cluster.average_clustering — NetworkX 2.6.2 documentation
netwokit ... networkit.globals

Package                       Version
----------------------------- -----------
networkit                     9.0
networkx                      2.6.3

import networkit as nk
import networkx as nx

# [nx] generate random graph
# [nx] ランダムグラフの作成
n = 100
m = 1000
G = nx.dense_gnm_random_graph(n, m).to_undirected()

# [nx] calculate average local cluster coefficients using networkx
# [nx] networkxの関数を用いて平均クラスタ係数の算出
cc_nx = nx.average_clustering(G)


# [nk] cast to networkit graph from networkx one
# [nk] networkxからnetworkit グラフへの変換
nkG = nk.nxadapter.nx2nk(G)

# [nk] calculate average local cluster coefficients using networkit
# [nk] networkitの関数を用いて平均クラスタ係数の算出
cc_nk = nk.globals.ClusteringCoefficient.avgLocal(nkG)

簡単な比較 (in 私のmac book)

• グラフ生成関数 nx.dense_gnm_random_graph
• 枝数: 完全グラフの 50%
• ノード数 を int(1.7**i) where i = 5 .. 14 に変えながら実験

結果: networkitは確かに速かった

実験コード

import networkit as nk
import networkx as nx
import numpy as np
import time

import random
random.seed(0)

ns = [int(1.7**i) for i in range(5, 14)]
nx_times = []
nk_times = []
print(ns)

for n in ns:
    # [nx] generate random graph
    # [nx] ランダムグラフの作成
    m = int( n * (n-1) / 2 * 0.5 )
    G = nx.dense_gnm_random_graph(n, m).to_undirected()

    elapsed_time = - time.time()
    cc = nx.average_clustering(G)
    elapsed_time += time.time()
    print(f"{n}: average cluster coefficients {cc:.3f}, elapsed {elapsed_time:.3f}s")
    nx_times.append(elapsed_time)

    elapsed_time = - time.time()
    nkG = nk.nxadapter.nx2nk(G)
    cc = nk.globals.ClusteringCoefficient.avgLocal(nkG)
    elapsed_time += time.time()
    print(f"{n}: average cluster coefficients {cc:.3f}, elapsed {elapsed_time:.3f}s")
    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")

関連