ネットワークグラフの中心性

前の記事でサンプルとして(折れ線グラフや棒グラフではなく、グラフ理論で言うところの)グラフを扱ったのでもう少し紹介します。
参考: Matplotlibの配色を別の処理でも流用したい

グラフについて分析するとき「どの点が重要なのか」という問いは非常に自然なものです。
そして、「中心にある点が重要なんじゃないか」と考えることもそこそこ自然な発想になります。
ただ、扱う対象が普通の幾何学的な図形ではなく、点とそれらの間にあるつながりという抽象的な概念で構成されたグラフの場合、
どの点が中心なのかというのは非自明な問題になります。
可視化してみれば確かにどれかの点が真ん中らへんにあるように見えるのですが、それは単に可視化の際にたままたそこにプロットされたというだけで、
グラフ理論で言うところの中心ではないからです。

この問題に対応するために、複数の中心が定義され、中心らしさを表す指標がいくつか提案されています。
networkxにも色々定義されているので、その中でも定義が単純でわかりやすいものを紹介します。
networkxのドキュメントではこちらに該当します。
Centrality

今回の記事では次のグラフをサンプルに使います。
何か特別な名前がついてるやつではなく、僕が今適当に構成したものです。

import matplotlib.pyplot as plt
import networkx as nx

G = nx.Graph()
G.add_edges_from([
    (0, 1),
    (1, 2),
    (2, 3),
    (3, 0),
    (1, 3),
    (0, 4),
    (4, 5),
    (5, 0),
    (5, 6),
])

# 可視化
fig = plt.figure(facecolor="w")
ax=fig.add_subplot(1, 1, 1, title="Sample Graph")
nx.draw_networkx(
    G,
    node_color="c"
)

さて、サンプルが用意できたので、次数中心性/近接中心性/媒介中心性の３種類の中心性の定義を紹介します。

次数中心性
一番単純でわかりやすいのが次数中心性(degree centrality)です。
これは、各ノードの次数(そのノードにつながっている、辺の本数)を指標とするものです。
正確には、各ノードの次数は最大でも「ノード数-1」までの値しか取れないので、「ノード数-1」で割って正規化したものを使います。
networkxではdegree_centralityで計算できます。

print("ノード番号, 次数中心性")
for k, v in nx.degree_centrality(G).items():
    print(k, ",", v)
"""
ノード番号, 次数中心性
0 , 0.6666666666666666
1 , 0.5
2 , 0.3333333333333333
3 , 0.5
4 , 0.3333333333333333
5 , 0.5
6 , 0.16666666666666666
"""

計算してみた各値を6(=7-1)倍すると、全部整数になり、各ノードから伸びてる辺の数に一致することがわかります。

近接中心性
距離がベースになっていて、円の中心などとイメージが近いのが近接中心性(closeness centrality)です。
これは、ある点から、そのほかの全ての点へのそれぞれの距離の平均値を元に決まります。
ただ、ほかの全ての点に近い(つまり距離が小さい)ほど、中心と見なしたいので、
距離の平均の逆数を取ります。
今回のグラフでは各辺に重み付けなどしていない(つまり全部重さ1とみなす)ので、ここで言う距離というのは最短経路を通った時に通過する辺の数です。
networkxではcloseness_centralityで計算できます。

※ 2020/12/24 コードに誤りがあることを教えていただき修正しました。

print("ノード番号, 近接中心性")
for k, v in nx.closeness_centrality(G).items():
    print(k, ",", v)
"""
ノード番号, 近接中心性
0 , 0.75
1 , 0.6
2 , 0.42857142857142855
3 , 0.6
4 , 0.5454545454545454
5 , 0.6
6 , 0.4
"""

試しに一つ具体的に計算しておきましょう。
0番のノードに着目します。
このノードの1~6番目までのノードの距離はそれぞれ、$1,2,1,1,1,2$ で、合計は$８$です。なので平均は$4/3$になります。
これの逆数をとったものが$3/4=0.75$なので、ライブラリの結果と一致しました。

媒介中心性
最後が媒介中心性(betweenness centrality)です。
個人的には、この記事で紹介した３種類の中では一番よく使います。
(主観的な感想です。媒介中心性がほかの二種に比べて理論的に優れているということを主張するものではありません。)
これは、着目している点以外の2点を結ぶ最短経路のうち、その点を通過するものの割合です。
networkxではbetweenness_centralityで計算できます。

print("ノード番号, 媒介中心性")
for k, v in nx.betweenness_centrality(G).items():
    print(k, v)
"""
ノード番号, 媒介中心性
0 0.6
1 0.13333333333333333
2 0.0
3 0.13333333333333333
4 0.0
5 0.3333333333333333
6 0.0
"""

さて、これは個別に解説したいと思います。
まず、2, 4, 6 の媒介中心性は0になっています。
これは、可視化した図を見るとわかるのですが、それぞれの点について、ほかの２点をどう選んでも、対象の点を通ると遠回りになるからです。

次にわかりやすいのは
5番です。まず、５番以外の6点から２点を選ぶ方法は全部で$6*5/2=15$通りあります。
その中で、5番を経由すると最短になるのは、６番の点と、そのほかの5点のどれかを結ぶ5通りです。
そのため、5版のノードの媒介中心性は$5/15=1/3$になります。
0番も同様に数えると、4,5,6のどれかと、1,2,3のどれかを結ぶ$3*3=9$通りの最短経路が0番を通過し、
媒介中心性は$9/15=3/5=0.6$になります。

さて、のこるは同じ値になっている1番と3番です。
まずは1番の方ですが、最短経路で１番のノードを通るのは２番のノードと、0,4,5,6のどれかを結ぶ4本になります。
となると、媒介中心性は$4/15=2.666…$になっても良さそうなのですが、実際にはこの$1/2$の値になっています。
実はこれは２番のノードと、0,4,5,6のどれかを結ぶ最短経路がそれぞれ複数あるのが原因です。
１番のノードの代わりに3番のノードを通っても良いわけです。
ということで、1番を通る最短経路を数える時に$0.5$倍して数えるので上の計算例の値になります。
３番も同様です。

辺の媒介中心性
さて、ノードの中心性を3つ紹介しましたが、最後の媒介中心性はノードだけではなく、辺についても定義できます。
ノードの場合は自分以外の2点でしたが、辺の場合はグラフ中の全てのノードから２点選び、
それらの最短経路のうち何本が自身を通過するかで定義されます。
networkxではedge_betweenness_centralityで計算できます。

計算結果が少数が複雑で、ぱっと見わかりにくかったので、
ノードの組みの場合の数、つまり$7*6/2=21$通りを掛けて、整数化したものを表示してみました。

print("辺, 辺の媒介中心性*21")
for k, v in nx.edge_betweenness_centrality(G).items():
    print(k, v*21)
"""
辺, 辺の媒介中心性*21
(0, 1) 6.0
(0, 3) 6.0
(0, 4) 4.0
(0, 5) 8.0
(1, 2) 3.0
(1, 3) 1.0
(2, 3) 3.0
(4, 5) 2.0
(5, 6) 6.0
"""

(1, 3) が 1 なのは、まさにその1と3をつなぐ時以外は通らないからですね。
一方で(5, 6)は、6とほかの点をつなぐ時は必ず通らないといけないので、中心性が高くなっています。

可視化した図では(5, 6)のエッジはかなり端っこにあるように見えるのですが、
媒介中心性は２位タイの高さということで、
可視化した時に真ん中にあるかどうかと、グラフ理論で言うところの中心は違うと言うことの雰囲気が伝わればと思います。

最後に、もう少し大きめのグラフで、それぞの中心性を算出して比較してみましょう。
計算した中心性はノードのサイズで示しました。

# ランダムにグラフデータ生成
while True:
    G=nx.random_graphs.fast_gnp_random_graph(25, 0.1)
    if nx.is_connected(G):
        # 連結なグラフができたら抜ける
        break


# ３種類の中心性をそれぞれ計算
dc_dict = nx.degree_centrality(G)
dc_list = np.array([dc_dict[n] for n in G.nodes])

cc_dict = nx.closeness_centrality(G)
cc_list = np.array([cc_dict[n] for n in G.nodes])

bc_dict = nx.betweenness_centrality(G)
bc_list = np.array([bc_dict[n] for n in G.nodes])

# 中心性をノードのサイズで表して可視化
pos = nx.spring_layout(G, iterations=300)
fig = plt.figure(facecolor="w", figsize=(8, 24))

ax=fig.add_subplot(3, 1, 1, title="Degree centrality ")
nx.draw_networkx(
    G,
    pos=pos,
    ax=ax,
    node_color="c",
    node_size=dc_list*300/np.mean(dc_list),
)
ax=fig.add_subplot(3, 1, 2, title="Closeness centrality")
nx.draw_networkx(
    G,
    pos=pos,
    ax=ax,
    node_color="c",
    node_size=cc_list*300/np.mean(cc_list),
)
ax=fig.add_subplot(3, 1, 3, title="Betweenness centrality")
nx.draw_networkx(
    G,
    pos=pos,
    ax=ax,
    node_color="c",
    node_size=bc_list*300/np.mean(bc_list),
)
plt.show()

出力された結果がこちら。