python-igraph を触ってみた:Rで学ぶデータサイエンス8 ネットワーク分析を python で:その1

ネットワーク分析 (Rで学ぶデータサイエンス 8)という、グラフ分析 の本を買ったのだがこれがなかなか面白い。
グラフ分析とかグラフ理論とかっていうと、Facebook とかのソーシャルメディアが真っ先に思い浮かぶ感じだが、レコメンドとかコンテンツの分析とか、もっと色々応用できそうな感じ。
ただ本のレビューするのもつまんないので、書籍でRで紹介されているサンプルを python だったらどうやるのか?を考えつつ、読んでいく、そのログ。

python-igraph を触ってみた:Rで学ぶデータサイエンス8 ネットワーク分析を python で:その1

グラフって?

小学校で習った棒グラフとか円グラフとか・・・お約束なボケは置いといて。

グラフ(英: Graph)とは、ノード(頂点)群とノード間の連結関係を表すエッジ(枝)群で構成される抽象データ型、and・orその実装である具象データ型である。グラフ理論によるグラフの実装であり、同理論にもとづく豊富なアルゴリズムの基盤である。
Wikipedia 「グラフ (データ構造)」より

人や物など、様々な情報の関係性を「ノード」と呼ばれる頂点とそれを結ぶ線「エッジ」で表現することで、数学的に取り扱えるようにしたもの、って理解でよいのかな?

python-igraph について

ネットワーク分析 (Rで学ぶデータサイエンス 8)でも実際に使われているのだが、データ分析の定番言語 R では、igraph というパッケージが存在する。(※他にも sna を使った例も紹介されてる)

・・・でも、ほとんど R を触ったことがないので python でも似たようなのないか探してみたら、あった、そのものズバリ、python 版の igraph があったじゃないか。

http://igraph.org/

ちなみに C 用のもあるってさ。

python-igraph をインストールする

pip でインストールできるのでカンタン。

pip install python-igraph   

python-igraph をとりあえず触ってみる

バージョン確認

お約束(?)、まあ、とりあえず。

import igraph  
print igraph.__version__  

グラフ オブジェクトを作る

何はともあれ、グラフのオブジェクトを作ります

from igraph import *  
g = Graph()  

ノードの追加

Graph オブジェクトの add_vertices() メソッドを使う

g.add_vertices(3)  

引数にはグラフを構成するノードの数を指定する。

エッジの追加

Graph オブジェクトの add_edges() メソッドを使う

g.add_edges([(0,1), (1,2)])  

引数は、(接続元のノード, 接続先のノード)という形の tuple の list。つまり、上の例では、0番のノードから1番のノードへ線が引かれてて、その1番からさらに2番へ線が引かれてる感じ。
ちなみに、「接続元・接続先」という表現は有向グラフの場合であって、無向グラフの場合は単に繋がっている2点を表すだけ。

グラフの表示

とりあえず、python のインタラクティブ シェル でグラフを表示するとどうなるのか?

print(g)  
IGRAPH U--- 3 2 --  
+ edges:  
0--1 1--2 <-- 確かに 0-11-2 が繋がってます  

隣接行列の取得

g.get_adjacency()  
Matrix([[0, 1, 0], [1, 0, 1], [0, 1, 0]])  

エッジリストの取得

g.get_edgelist()  
[(0, 1), (1, 2)]  

・・・なるほど、一度グラフオブジェクトを作ってしまえば、そこから隣接行列やエッジリストを取得するのはカンタンってことね。

最後に、最短ルートを求めてみる

g.get_shortest_paths(0,2)  
[[0, 1, 2]]  

0 --> 1 --> 2 という1方向だけ・分岐のないグラフなのでイマイチありがたみがわからないが、もっと複雑に入り組んだグラフでも同じようにメソッド一発で最短ルートを返してくれるってのはすごい。

ぼちぼちと読んでログ書いとこ。

参考:
Get Started with python-igraph(英語)

ネットワーク分析 (Rで学ぶデータサイエンス 8)

ネットワーク分析 (Rで学ぶデータサイエンス 8)