Python の NetworkX 入門

#はじめに
NetworkX はグラフ分析に用いられる python のライブラリです．

[英語のドキュメント](https://networkx.github.io/documentation/networkx-1.9.1/index.html) しか存在しないので気軽に触りにくい印象があるかもしれませんが，非常に扱いやすいライブラリなので軽く紹介をしたいと思います．

本稿では以下の3点を中心に紹介します．

- グラフの構築方法
- matplotlib による可視化
- PageRank による中心性解析

また，python のバージョンは 3 を想定し，NetworkX のインストールについては省略します．
（インストールは [こちら](https://networkx.github.io/documentation/networkx-1.9.1/install.html) をご参照ください）

[追記：2018/10/5（金）]
本記事で使用した NetworkX のバージョンは 1 です。

#グラフの構築方法
グラフの構築方法ですが，(1)外部ファイルから読み込む方法，(2)NetworkX の関数を用いる方法の2つを紹介します．

###(1)外部ファイルから読み込む方法
ここでは NetworkX の `read_edgelist()` という関数を用いて，エッジのリストが記述された txt ファイルからグラフを構築してみます．

エッジのリストは [こちら](https://snap.stanford.edu/data/egonets-Facebook.html) の Facebook のグラフを使用します．
（リンク先のページ下部にある "facebook_combined.txt.gz" が該当ファイルです．）

ファイルには以下のようにエッジのリストが記述されています．

```txt:facebook_combined.txt
0 1
0 2
0 3
0 4
 ：
```

プログラムは以下の通りです．

```
# networkx の import
import networkx as nx

# グラフを構築
G = nx.read_edgelist('facebook_combined.txt', nodetype=int)

# ノード数とエッジ数を出力
nx.number_of_nodes(G)
nx.number_of_edges(G)
```

出力

```
4039
88234
```

簡単ですね．
`read_edgelist()` の引数 `nodetype` は txt ファイル内のノードのデータ型を指定します．

###(2)NetworkX の関数を用いる方法
NetworkX にはランダムグラフやソーシャルネットワークを生成する関数が含まれています．
これらを用いてグラフを生成することで，実際にデータを用意することなくグラフを扱う練習をすることができます．

ここでは Zachary’s Karate Club のグラフを生成する `karate_club_graph()` を使用します．

```
# グラフの構築
G = nx.karate_club_graph()

#ノード数とエッジ数を出力
nx.number_of_nodes(G)
nx.number_of_edges(G)
```

出力

```
34
78
```

とても簡単ですね．

グラフを出力する関数は [こちら](https://networkx.github.io/documentation/networkx-1.10/reference/generators.html) にまとめられているので，いろいろなグラフで遊んでみてください．

#Matplotlib による可視化
Matplotlib はグラフ描画の際に用いられる python のライブラリです．
ここでは先ほど生成した Zachary’s Karate Club のグラフを可視化してみたいと思います．

可視化には `draw_networkx_edges()` と `draw_networkx_nodes()` を用います．
それぞれグラフの "エッジ" と "ノード" を描画する関数です．

どちらの関数にもエッジとノードの座標を指定する必要があります．
networkx にはグラフのレイアウトを決める関数が用意されており，ここでは `spring_layout()' を用います．

プログラムは以下の通りです．

```
# networkx, matplotlib の import
import networkx as nx
import matplotlib.pyplot as plt

# グラフの構築
G = nx.karate_club_graph()

# レイアウトの取得
pos = nx.spring_layout(G)

# 可視化
plt.figure(figsize=(6, 6))
nx.draw_networkx_edges(G, pos)
nx.draw_networkx_nodes(G, pos)
plt.axis('off')
plt.show()
```

![karate_graph.png](https://qiita-image-store.s3.amazonaws.com/0/52644/5b8bc963-d95e-ae63-a268-9120a0b7f391.png)


これも簡単ですね．
`draw_networkx_edges()` と `draw_networkx_nodes()` の引数にグラフと座標を渡すだけです．

エッジやノードのサイズや色は変更することができます．
エッジの場合は `draw_networkx_edges()` の引数 `edge_color` や `width` を，
ノードの場合は `draw_networkx_nodes()` の引数 `node_color` や `node_size` を指定するだけです．
（デフォルトでは width は 1.0，node_size は 300 に設定してあります．）

```
# 可視化
plt.figure(figsize=(6, 6))
nx.draw_networkx_edges(G, pos, edge_color='orange', width=1.5)
nx.draw_networkx_nodes(G, pos, node_color='green', node_size=600)
plt.axis('off')
plt.show()
```

![karate_graph2.png](https://qiita-image-store.s3.amazonaws.com/0/52644/bde02e00-d2c8-8f9d-f86b-b53723c06d7b.png)


#PageRank による中心性解析
最後に，PageRank による中心性解析の方法を紹介します．

中心性とはネットワークにおけるノードの重要性を表す指標です．
ソーシャルネットワークの場合，多くの人からフォローされ，発言力の高い人物は重要な人物であると言えることができると思います．

すなわち，中心性解析はグラフの中で重要なノードを発見する分析とも言うことができます．

中心性にはいろいろな種類がありますが，ここでは PageRank を用います．
PageRank は Google の検索エンジン内で用いられている，Web ページの重要性を評価するためのアルゴリズムです．

NetworkX では `pagerank()` という関数が実装されています．
ここでは Zachary’s Karate Club のグラフに対して PageRank を計算し，各ノードの重要性を可視化してみたいと思います．

まず，プログラムは以下のようになります．

```
# pagerank の計算
pr = nx.pagerank(G)

# 可視化
plt.figure(figsize=(6, 6))
nx.draw_networkx_edges(G, pos)
nx.draw_networkx_nodes(G, pos, node_color=list(pr.values()), cmap=plt.cm.Reds)
plt.axis('off')
plt.show()
```

![karate_graph3.png](https://qiita-image-store.s3.amazonaws.com/0/52644/b043f197-78f5-78ce-9863-284a4b484f1d.png)

可視化されたグラフを見てみると，多くのノードから参照され，グラフの中心に位置しているようなノードほど重要であるということが言えそうですね．

ここからは可視化方法を解説します．

pr には各ノードの PageRank のスコアが格納されており，値が大きいほど重要なノードと言えます．

```
{0: 0.09700181758983709,
 1: 0.05287839103742701,
         ：
 33: 0.1009179167487121}
```

これを利用して，PageRank のスコアの値に応じてノードの色を変更します．

これは `draw_networkx_nodes()` の引数 `node_color` に pr の値の list を渡すことで，簡単に実現することができます．

引数 `cmap` は color map を指定するものです．
matplotlib の散布図などで使ったことがある方もいると思いますが， [こちら](https://matplotlib.org/examples/color/colormaps_reference.html) から任意の color map を選択することができます．

今回は Reds というものを使用したので，値を大きいほど濃い赤色で表示されました．

同様に，PageRank の値に応じてノードサイズを変更することも可能です．

```
# 可視化
plt.figure(figsize=(6, 6))
nx.draw_networkx_edges(G, pos)
nx.draw_networkx_nodes(G, pos, node_size=[5000*v for v in pr.values()])
plt.axis('off')
plt.show()
```

![karate_graph4.png](https://qiita-image-store.s3.amazonaws.com/0/52644/7e5e2d97-8160-e156-9cbe-36c20dd52c70.png)

`node_size` に pr の値の list を渡すだけです．
※デフォルトの node_size が 300 なのに対して pr の値は 0.1 程度なので，ここでは各値に 5000 をかけています．

#さいごに
Python の NetworkX の使用方法を紹介しました．

いずれの操作も簡単に実現できることが分かっていただけたと思います．

ただし，`facebook_combined.txt' のようなノード数が約 4000，エッジ数が約 90000 の小規模なグラフの場合でも PageRank や spring_layout の計算に数秒かかってしまっていたので，大規模なグラフを実際に分析することができるかは正直難しそうだと感じました．

python で大規模グラフを扱うことができるオススメのライブラリがあったら是非教えていただけたらと思います．