pythonとnetworkxを使ったPageRank解析

pythonにはnetowrkxという便利なグラフ解析ライブラリが存在します。
このライブラリはかなり良くできていて
・Rのigraph等のライブラリと比較してサブグラフの出力結果へのアクセス手法が用意
・numpyやscipy等との連携がかなり進んでおり、大規模なグラフや高速演算を求められるグラフにおいても適している。
という特徴があります。
ここでは、同ライブラリを使ってPageRankによるグラフ解析を実施する手法を紹介します。

利用ライブラリ

networkxを利用するにあたり必要なライブラリは以下の通りです。

numpyとscipyはnetowrkxを利用するにあたり必須のライブラリではありませんが、numpyやscipyを入れておくと疎行列を扱う事ができるようになるなどメリットが大きいです。。
(というか、numpyやscipy無しの場合、グラフのノード数やエッジ数のサイズが数百ぐらいまでと限定されます)

あと、networkxやnumpyはpipコマンド一発でインストールできますが、scipyについては、内部でBLASやLAPACを利用している関係からか、pipでインストールする前に関連ライブラリをインストールしておく必要があります。
インストール方法は環境によって多様ですが、基本的にはscipyのインストール手法(http://www.scipy.org/Installing_SciPy)を参考にしてください。

今回解析する対象のグラフ

以下のグラフを対象とします。

f:id:kaita_v:20121207183930p:plain

ソースコード

この例ではダンピングファクターの値を0.9としています。

# -*- coding: utf-8 -*-
import networkx as nx

#有向グラフ
g = nx.DiGraph()

#ノードの追加(省略可能)
g.add_node(1)
g.add_node(2)
g.add_node(3)
g.add_node(4)

#エッジの追加
g.add_edge(1,2)
g.add_edge(1,3)
g.add_edge(1,4)
g.add_edge(2,3)
g.add_edge(3,4)

#pagerank値の計算
pr=nx.pagerank(g,alpha=0.9)

#pagerank値の計算(numpyを利用)
prn=nx.pagerank_numpy(g,alpha=0.9)

#pagerank値の計算(scipyを利用)
prc=nx.pagerank_scipy(g,alpha=0.9)

#計算結果表示
print("-----pagerank-----")
print(pr)

print("-----pagerank(numpy)-----")
print(prn)

print("-----pagerank(scipy)-----")
print(prc)

実行結果

-----pagerank-----
{1: 0.12058362438281975, 2: 0.15675871212474798, 3: 0.2978415539438116, 4: 0.4248161095486206}
-----pagerank(numpy)-----
{1: 0.12058362474375982, 2: 0.15675871216688764, 3: 0.29784155311708677, 4: 0.42481610997226577}
-----pagerank(scipy)-----
{1: 0.12058369059454467, 2: 0.15675865745841386, 3: 0.29784125143334383, 4: 0.42481640051369757}