カテゴリー: グラフ理論

前の記事でサンプルとして(折れ線グラフや棒グラフではなく、グラフ理論で言うところの)グラフを扱ったのでもう少し紹介します。
参考: 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()

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

前回の記事がNetworkXの頂点の書式についての記事だったので今回は辺の書式です。

ドキュメントは同じ場所です。
ドキュメント: draw_networkx

有向グラフの場合は矢印の形などもう少し項目が多いのですが、
無向グラフの場合は、太さと色とスタイル(単線、破線、ドットなど)が設定項目になります。

このうち、太さ(width) と 色(edge_color) は単一の値だけではなく、
辺の数と同じ長さの配列で指定することができます。

配列で指定した値は、 G.edge で取得できる辺の一覧の順番と対応するように設定されます。
(初めてNetworkXをいじった時はこの辺りをしらず、思った設定ができずにいました。)

細かいですがドキュメントにデフォルトの色は’r’ (赤)と書いてありますが、これはおそらくドキュメントの誤りです。
(何も指定しないと黒になります。)

edge_color (color string, or array of floats (default=’r’))

styleに指定できるのは次の4種類です。(スタイルの指定は辺別ではなく、全体で一つ指定する必要があります。)
solid|dashed|dotted|dashdot

それでは適当なグラフで実行してみましょう。

import networkx as nx
import matplotlib.pyplot as plt

# グラフを生成
G = nx.Graph()
G.add_cycle(range(5))

# 辺の順番を確認
print(G.edges)
# [(0, 1), (0, 4), (1, 2), (2, 3), (3, 4)]

# 可視化
nx.draw_networkx(
    G,
    edge_color=["r", "g", "m", "c", "y"],
    width=[1, 2, 3, 4, 5],
    style= "dashdot",
)
plt.show()

出力がこちら。

0と1を結んでるのが一番細い赤い線で、次に0と4を結んでるが緑の線で、
と G.edges の値と対応して設定が反映されました。

NetworkXのグラフを可視化するときに、もっと見た目を変えたいなと思うことは多々あると思います。
そのようなニーズに応えるために頂点と辺のそれぞれにいくつかのオプションが用意されています。
今回はその中から、頂点の書式に関するものをいくつか紹介します。

ドキュメント: draw_networkx

このページの node_xxx の形式で定義されているパラメーターがそれです。
この中から、node_size、node_color、node_shapeを使って、頂点の色や大きさを変えてプロットしてみましょう。
なお、node_shapeはグラフに対して1つですが、node_sizeとnode_colorは頂点ごとに設定を変えることができます。
ついでに font_family も設定して日本語のフォントを表示してみましょう。

# グラフの生成
G = nx.Graph()
for n in "あいうえお":
    G.add_node(n)

# 頂点の順番の確認。(node_size や node_color はこの順番で指定する)
print(G.nodes)
# ['あ', 'い', 'う', 'え', 'お']

nx.draw_networkx(
    G,
    node_shape="s",
    node_size=[100, 200, 300, 400, 500],
    node_color=["r", "g", "m", "c", "y"],
    font_family="IPAexGothic"
)
plt.show()

出力がこちら。

node_size はデフォルトが 300であることに注意しましよう。
node_shape には ‘so^>v<dph8’ のいずれかの文字が指定できます。

前の記事の続きです。
参考:NetworkXのグラフを可視化するときに頂点の座標を指定する
こちらの記事では、頂点を円形に並べるとき、三角関数を使って座標を指定しました。
それは自分の理解のためにやったのですが、実用上はあらかじめ用意さているレイアウト用の関数を使った方が楽です。

ドキュメント:Graph Layout
たとえば、
circular_layout
を使えば、円上にノードを配置できます。

次のコードのように使います。
グラフの構成と可視化結果は前回の記事と同じなので省略します。

pos = nx.circular_layout(G)
nx.draw_networkx(G, pos=pos, node_color="c")
plt.show()

久々のNetworkXの記事です。
今回はグラフを可視化するときに、明示的に頂点の座標を指定する方法を紹介します。

ドキュメントの Docs » Reference » Drawing
のページを見ると、draw_networkxなどの可視化関数がposという引数を受け取ることがわかります。
ここに、{頂点:(x座標, y座標), …} という形式の辞書を渡してあげると、可視化するときにその座標にノードを配置できます。
これを使って頂点を格子点においたり、一直線に並べたりできます。

いい感じに座標の辞書を作ってくれる関数もいくつか用意されているのですが、
今回は自分で直接円周上のてんを定義してやってみます。

まず一つ目の例は座標は指定せずにそのまま可視化したものです。

import matplotlib.pyplot as plt
import networkx as nx
import numpy as np

# 12個の頂点と、ランダムに引いた辺を持つグラフを定義
node_labels = "abcdefghijkl"
G = nx.Graph()
G.add_nodes_from(node_labels)
for i in range(len(G.nodes)):
    for j in range(i+1, len(G.nodes)):
        if np.random.uniform() < 0.3:
            G.add_edge(node_labels[i], node_labels[j])

# 座標を指定せずに描写する
nx.draw_networkx(G, node_color="c")
plt.show()

結果がこちら。頂点はある程度バラバラに配置されていますね。

次にグラフはそのままで座標を指定してみます。

# 各頂点に対して円周上の座標を割り当てる
pos = {
        n: (np.cos(2*i*np.pi/12), np.sin(2*i*np.pi/12))
        for i, n in enumerate(G.nodes)
    }
print(pos)
'''
{'a': (1.0, 0.0),
 'b': (0.8660254037844387, 0.49999999999999994),
 'c': (0.5000000000000001, 0.8660254037844386),
 'd': (6.123233995736766e-17, 1.0),
 'e': (-0.4999999999999998, 0.8660254037844388),
 'f': (-0.8660254037844387, 0.49999999999999994),
 'g': (-1.0, 1.2246467991473532e-16),
 'h': (-0.8660254037844388, -0.4999999999999998),
 'i': (-0.5000000000000004, -0.8660254037844384),
 'j': (-1.8369701987210297e-16, -1.0),
 'k': (0.5, -0.8660254037844386),
 'l': (0.8660254037844384, -0.5000000000000004)}
'''

# 指定した座標を用いてグラフを可視化する
nx.draw_networkx(G, pos=pos, node_color="c")
plt.show()

結果がこちらです。

きちんと円周上に頂点が並びました。

せっかくgraphvizではなくNetworkXを動かしているので、何か実装されているアゴリズムを試しておこうというのが今回の趣旨です。
とりあえずグラフ中の二点間の最短経路を探す関数を試してみましょう。
(SNSのフォローや友達関係のネットワークで共通の知り合い等を探すのに使えますね)

まず、ランダムにグラフデータを作成します。

import networkx as nx
import matplotlib.pyplot as plt
import numpy as np

G = nx.Graph()

for i in range(30):
    for j in range(i+1, 30):
        # 1/10の確率でnode間を線で結ぶ
        if np.random.randint(10) == 0:
            G.add_edge(i, j)

# 可視化
fig = plt.figure(figsize=(8, 8))
nx.draw_networkx(G)

出来上がったのはこちら。

ここで2点を指定して、最短経路を求めるにはshortest_pathを使います。
ドキュメント:Shortest Paths

パスが存在しない時にshortest_pathを実行するとエラーになるので、
パスの存在を判定する関数も合わせて試してみます。

# 特定の２つのnode間の最短経路を探す
print(nx.shortest_path(G, source=9, target=20))
# [9, 10, 13, 24, 12, 20]

# source か target を省略すると、その点と他の各点の最短経路を求める
print(nx.shortest_path(G, source=5))
# {5: [5], 6: [5, 6], 29: [5, 29], 21: [5, 6, 21]}

# パスが存在するか判定する
print(nx.has_path(G, source=6, target=10))
# False

ネットワークやグラフ構造の可視化はgraphvizでできるのですが、分析となると、networkX等、別のライブラリを使う必要が出てきます。

このブログでnetworkXを取り上げるのは初なので、とりあえず今回は非常に単純なグラフを書いて可視化してみました。
チュートリアルを見ながらいろいろいじると楽しいのでオススメです。

import networkx as nx
import itertools
import matplotlib.pyplot as plt
# グラフオブジェクトの作成
G = nx.Graph()
# ５つの点を相互に全て結ぶ
for edge in itertools.combinations(range(5), 2):
    G.add_edge(*edge)
# さらに5つの点を追加し、既存の点と結ぶ
for i in range(5):
    G.add_edge(i, i+5)
# 後から追加した5つの点を環状に結ぶ
for i in range(4):
    G.add_edge(i+5, i+6)
G.add_edge(9, 5)
# 可視化
nx.draw_networkx(G)

出力結果がこちら。
点の配置に乱数が使われているので、何度か施行していい感じになったのを保存しました。