【NetworkX】Girvan–Newmanアルゴリズムでコミュニティを抽出（台北MRTを例にして）

この記事では、NetworkXを使ったネットワークの中のコミュニティ抽出の手法を、台北の地下鉄を例にして解説します。
実際に分割されたコミュニティの可視化についてもコードを載せておきます。

Girvan–Newmanアルゴリズムとは？

Girvan–Newmanアルゴリズムはコミュニティを検出するアルゴリズムです。
手順はシンプルで、

ネットワーク内のすべてのエッジの媒介中間性を計算する
最も媒介中間性が大きいエッジを削除する
削除した状態で再びすべてのエッジの媒介中間性を計算する
エッジがなくなるまでステップ2~3を繰り返す

というものです。詳しい説明は以下の論文に書いてあります。

Calculate the betweenness for all edges in the network.

Remove the edge with the highest betweenness.

Recalculate betweennesses for all edges affected by the removal.

Repeat from step 2 until no edges remain.

Community structure in social and biological networks

台北MRTの路線図をNetworkXで描画する

台北のMRTの路線図を描いてみます。これをGirvan–Newmanアルゴリズムでコミュニティ分割します。

▼台北MRT路線図【NetworkX】Girvan–Newmanアルゴリズムでコミュニティを抽出（台北MRTを例にして）画像：台湾観光局

import matplotlib.pyplot as plt
import networkx as nx
import numpy as np
from networkx.algorithms.community.centrality import girvan_newman
import itertools

隣の駅の組み合わせをリスト化します。これ手作業でやったのでめちゃくちゃ大変でした（笑）
※桃園機場MRTは省いています

edge_list = [
('Dingpu', 'Yongning'), ('Yongning', 'Tucheng'), ('Tucheng', 'Haishan'), ('Haishan', 'Far Eastern Hospital'), ('Far Eastern Hospital', 'Fuzhong'), ('Fuzhong', 'Banqiao'), ('Banqiao', 'Xinpu'), ('Xinpu', 'Jiangzicui'), ('Jiangzicui', 'Longshan Temple'), ('Longshan Temple', 'Ximen'), ('Ximen', 'Taipei Main'), ('Taipei Main', 'Shandao Temple'), ('Shandao Temple', 'Zhongxiao Xinsheng'), ('Zhongxiao Xinsheng', 'Zhongxiao Fuxing'), ('Zhongxiao Fuxing', 'Zhongxiao Dunhua'),
('Zhongxiao Dunhua', 'Sun Yat-Sen Memorial Hall'), ('Sun Yat-Sen Memorial Hall', 'Taipei City Hall'), ('Taipei City Hall', 'Yongchun'), ('Yongchun', 'Houshanpi'), ('Houshanpi', 'Kunyang'), ('Kunyang', 'Nangang'), ('Nangang', 'Taipei Nangang Exhibition Center'), ('Taipei Nangang Exhibition Center', 'Nangang Software Park'), ('Nangang Software Park', 'Donghu'), ('Donghu', 'Huzhou'), ('Huzhou', 'Dahu Park'), ('Dahu Park', 'Neihu'), ('Neihu', 'Wende'), ('Wende', 'Gangqian'), ('Gangqian', 'Xihu'),
('Xihu', 'Jiannan Road'), ('Jiannan Road', 'Dazhi'), ('Dazhi', 'Songshan Airport'), ('Songshan Airport', 'Zhongshan Junior High School'), ('Zhongshan Junior High School', 'Nanjing Fuxing'), ('Nanjing Fuxing', 'Zhongxiao Fuxing'), ('Zhongxiao Fuxing', 'Daan'), ('Daan', 'Technology Building'), ('Technology Building', 'Liuzhangli'), ('Liuzhangli', 'Linguang'), ('Linguang', 'Xinhai'), ('Xinhai', 'Wanfang Hospital'), ('Wanfang Hospital', 'Wanfang Community'), ('Wanfang Community', 'Muzha'), ('Muzha', 'Taipei Zoo'), ('Xiangshan', 'Taipei 101 / World Trade Center'),
('Taipei 101 / World Trade Center', 'Xinyi Anhe'), ('Xinyi Anhe', 'Daan'), ('Daan', 'Daan Park'), ('Daan Park', 'Dongmen'), ('Dongmen', 'Chiang Kai-Shek Memorial Hall'), ('Chiang Kai-Shek Memorial Hall', 'National Taiwan University Hospital'), ('National Taiwan University Hospital', 'Taipei Main'), ('Taipei Main', 'Zhongshan'), ('Zhongshan', 'Shuanglian'), ('Shuanglian', 'Minquan West Road'), ('Minquan West Road', 'Yuanshan'), ('Yuanshan', 'Jiantan'), ('Jiantan', 'Shilin'),
('Shilin', 'Zhishan'), ('Zhishan', 'Mingde'), ('Mingde', 'Shipai'), ('Shipai', 'Qilian'), ('Qilian', 'Qiyan'), ('Qiyan', 'Beitou'), ('Beitou', 'Xinbeitou'), ('Beitou', 'Fuxinggang'), ('Fuxinggang', 'Zhongyi'), ('Zhongyi', 'Guandu'), ('Guandu', 'Zhuwei'), ('Zhuwei', 'Hongshulin'), ('Hongshulin', 'Tamsui'), ('Nanshijiao', 'Jingan'), ('Jingan', 'Yongan Market'), ('Yongan Market', 'Dingxi'), ('Dingxi', 'Guting'), ('Guting', 'Dongmen'), ('Dongmen', 'Zhongxiao Xinsheng'), ('Zhongxiao Xinsheng', 'Songjiang Nanjing'),
('Songjiang Nanjing', 'Xingtian Temple'), ('Xingtian Temple', 'Zhongshan Elementary School'), ('Zhongshan Elementary School', 'Minquan West Road'), ('Minquan West Road', 'Daqiaotou'), ('Daqiaotou', 'Taipei Bridge'), ('Taipei Bridge', 'Cailiao'), ('Cailiao', 'Sanchong'), ('Sanchong', 'Xianse Temple'),
('Xianse Temple', 'Touqianzhuang'), ('Touqianzhuang', 'Xinzhuang'), ('Xinzhuang', 'Fu Jen University'), ('Fu Jen University', 'Danfeng'), ('Danfeng', 'Huilong'), ('Daqiaotou', 'Sanchong Elementary School'), ('Sanchong Elementary School', 'Sanhe Junior High School'), ('Sanhe Junior High School', 'St. Ignatius High School'), ('St. Ignatius High School', 'Sanmin Senior High School'), ('Sanmin Senior High School', 'Luzhou'), ('Xindian', 'Xindian District Office'), ('Xindian District Office', 'Qizhang'),
('Qizhang', 'Xiaobitan'), ('Qizhang', 'Dapinglin'), ('Dapinglin', 'Jingmei'), ('Jingmei', 'Wanlong'), ('Wanlong', 'Gongguan'), ('Gongguan', 'Taipower Building'), ('Taipower Building', 'Guting'), ('Guting', 'Chiang Kai-Shek Memorial Hall'), ('Chiang Kai-Shek Memorial Hall', 'Xiaonanmen'), ('Xiaonanmen', 'Ximen'), ('Ximen', 'Beimen'), ('Beimen', 'Zhongshan'), ('Zhongshan', 'Songjiang Nanjing'), ('Songjiang Nanjing', 'Nanjing Fuxing'), ('Nanjing Fuxing', 'Taipei Arena'), ('Taipei Arena', 'Nanjing Sanmin'),('Nanjing Sanmin', 'Songshan')
]

この隣の駅のリストをadd_edges_fromでグラフとして読み込み、描画してみます。

# グラフ作成
G = nx.Graph()
G.add_edges_from(edge_list)

# 描画
plt.figure(figsize=(10, 15))
pos = nx.kamada_kawai_layout(G)
nx.draw(G, pos, with_labels=True, font_size=9, node_size=500, node_color="orange", font_color="black")

はい、こんな感じです。

▼NetworkXで描画した台北MRT路線図【NetworkX】Girvan–Newmanアルゴリズムでコミュニティを抽出（台北MRTを例にして）

媒介中心性を計算してみましょう。
大きい順にTop5を並べてみます。

between_centers = nx.betweenness_centrality(G)
sorted(between_centers.items(), key=lambda x: x[1], reverse=True)[:5]

▼実行結果

>[('Minquan West Road', 0.4594251454769881),
> ('Songjiang Nanjing', 0.3815229530359139),
> ('Zhongshan', 0.32528654558279),
> ('Zhongxiao Fuxing', 0.3118468230176916),
> ('Nanjing Fuxing', 0.2861282548639271)]

民権西路（Minquan West Road）の媒介中心性が一番大きいですね。
感覚的には台北車站（Taipei Main Station）かなと思いましたがTop5にすらランクインしていませんでした。

路線図をコミュニティに分割する

期待としては、上で描画したグラフの上部にあるループや、下に伸びている3本の路線がそれぞれ分割されると良いなと。
girvan_newmanを使って、実際にコミュニティを分割するコードを書きます。
以下のコードのkは分割の数を表します。k=4にすると5つのコミュニティに分割されるわけです。

k = 4
comp = girvan_newman(G)
for communities in itertools.islice(comp, k):
  list_community = []
  for c in communities:
    list_community.append(list(c))

分割したそれぞれコミュニティに色付けをします。これでコミュニティをわかりやすく可視化できます。

color_map = []
for node in G.nodes():
    if node in list_community[0]:
        color_map.append('skyblue')

    elif node in list_community[1]:
        color_map.append('lightgreen')

    elif node in list_community[2]:
        color_map.append('yellow')

    elif node in list_community[3]:
        color_map.append('pink')

    else: 
        color_map.append('orange')

描画します！

plt.figure(figsize=(10, 15))
pos = nx.kamada_kawai_layout(G)
nx.draw(G, pos, with_labels=True, font_size=9, node_size=500, node_color=color_map, font_color="black")

▼コミュニティ分割の可視化【NetworkX】Girvan–Newmanアルゴリズムでコミュニティを抽出（台北MRTを例にして）

まあ、なんとなく期待通りの分割になりました。

まとめ

今回はGirvan–Newmanアルゴリズムを使ってみましたが、他にも様々なコミュニティ分割の手法があるので、また試してみたいと思います。

▼参考文献

データアナリストのメモ帳

IT企業で働くデータアナリストのブログ

【NetworkX】Girvan–Newmanアルゴリズムでコミュニティを抽出（台北MRTを例にして）

Girvan–Newmanアルゴリズムとは？

台北MRTの路線図をNetworkXで描画する

路線図をコミュニティに分割する

まとめ