igraph + Pythonによるネットワーク分析

世の中の様々なシステムは、"グラフ"で表現することが可能だ。例えば、SNSにおける人の繋がりは、人を点（ノード）、人との関係を線（リンク）として、グラフが描ける。同様に、交通網、インターネット、プログラムのソースコード、脳内の神経回路なども、ノードとリンクでグラフとして表現することが出来る。

システムをグラフとして表現することで、グラフ理論の観点からシステムを解析・分析することが可能となる。その結果、何らかの新しい知見が得られる可能性がある。例えば、人の繋がりでは、最も発言力のある人間を、定量的に示すことが出来るし、交通網では渋滞などを迂回しつつ最短な経路を計算することも可能となる。

システムをグラフとして表現し、解析するためのプログラミングライブラリに、igraphがある。igraphは、2006年から開発・公開されている、C/Python/R用のグラフライブラリであり、現在、ハーバード大学のGabor Csardi氏と、エトヴェシュ・ロラーンド大学のTamás Nepusz氏の二人によって、開発・保守が行われている。バグ報告や質問用のメーリングリストには、一日に5通ほどメールが流れており、両氏が迅速かつ丁寧に対応しており、コミュニティも比較的活発である。グラフ理論系の論文などでも、"igraphを利用して計算した"と記述されているものがあり、どうやら研究者の間でigraphはよく使われているようだ。

グラフ系のライブラリには、NetworkXやC++のboost graph libraryなどもあるが、

• グラフ理論系の関数の量が多い
• 丁寧なドキュメントがある
• 他のグラフ系のソフトウェアとの親和性が良い（データフォーマットなどの点で）

ことなどを理由に、自分はigraphを使っている。 

igraphは、日本人の間でも少なからず使われているようだ。Googleで言語を日本語にセットしてigraphと検索すると、多くのwebページがヒットする。

が、しかしなぜか、みなさん、Rでigraphを使っており、pythonでigraphを使っている人が少ない（C言語に至っては、皆無？）。もし「グラフを、自分の定義したクラスで表現して、計算だけigraphの力を借りたい」とか、より柔軟にプログラムを設計したいのであれば、pythonを利用することはよい選択肢だと思う。

そこで、今回、Python+igraphの利用例について、一つ書いていきたいと思う。


まずは試しに、以下のようなことをやってみよう。

『以下のようなリンクリストで表現されたグラフを読み取り、グラフをモジュール分割して、その中の最大のモジュールのグラフを、graphmlファイルで出力する』

0 1
2 1
3 4
4 5
3 1

上のデータは、各行がリンクを表しており、一行目は『ノード0とノード1の間にリンクが存在』することを示している。

モジュールとは、グラフ内にある、リンクで密に繋がったノードの部分集合である。グラフ内のリンクが"均一"に張られているケースはまれで、たいて いの場合、"むら"がある。この"むら"によって、リンクで密に繋がったノードの集合が現れる。例えばSNSの場合、モジュール分割をすることで、仲良しグループなどを抽出することが出来る。上のお題でやりたいのは、例えばSNSの人間関係のグラフから、最も大きな仲良しグループを取り出す、ということである。

graphmlとは、グラフを表現するためのデータフォーマットの一つであり、igraphだけでなく、gephiというグラフ描画ソフトウェアなどでも用いられている。XMLに近い記法で、ノードやリンクの詳細な情報を付加して記述することが可能である。

これほど、ごちゃごちゃとしそうな処理が、igraph+pythonなら、なんとたったの5行で書ける。（Rでも簡単に書けるとは思う。）

from igraph import *
g = Graph.Read("sample_graph_edge_list.txt", format = "edgelist", directed=False)
communities = g.community_multilevel()
giant_graph = communities.giant()
giant_graph.write("result.graphml", format = "graphml")

一行目では、pythonでigraphのライブラリをインポートしている。
二行目では、ファイルを読み込んで、グラフを作っている。gがグラフである。
三行目では、モジュール分割が行われている。igraphでは、現在9種類（！）のモジュール分割法が実装されている。
四行目では、最もノード数の大きなモジュールが取りだされている。
五行目では、graphml形式で、グラフがファイル出力されている。

igraphでは、グラフの計算など処理がC言語で記述されているため、計算時間は比較的早いはずである。

もし、あなたがグラフ系の処理を書こうとしているなら、igraphは自信を持って進められるライブラリだと思う。これからも、気が向いたらこのブログで、igraphとPythonの応用例について、書いていこうと思う。

また、igraphのドキュメントは、丁寧で読みやすい英語ではあるものの、基本的なことがドキュメントのどこに記載されているのか見つけにくい場合がある。なので、igraphをPythonで使う際の基礎的な部分についても、そのうちまとめようと思う。

さらに、C言語から使う方法についても、気が向いたらまとめようと思う。