PageRank とか HITS といったリンク解析ではグラフの計算が頻発するのだが、Python でそのあたり書くときの話をまとめてみる。グラフは行列で表現できる(ノード×ノード次元の行列 A を考えて、ノード i からノード j にエッジがあるとき、A[i,j] に値を入れておけばよい。無向グラフのときは A[i,j] = A[j,i] なので対称行列になる)ので、要は行列を手軽に扱えるライブラリの紹介である。
実は Python の行列演算ライブラリはどれも lapack/blas を内部的に呼んでいるので、C/C++ 等と比較してもそんなに遅くない。それどころか、自動的に並列化できるところは並列化してくれたりするので、まれに C より速いこともあるらしい。特に巨大なグラフを作る場合、ほとんどの処理は C などで書かれた関数に飛ぶので、速度的な問題は無視してもいいくらいである(逆に、小さい行列をひたすら計算する場合、Python とのやりとりのオーバーヘッドが気になってくるが)。
- SciPy
- Python で科学技術計算をしたいならまずこれ、というくらい有名なライブラリ。大体の環境でパッケージが用意されている。ただ、実環境でありがちな疎行列(scipy.sparse)の計算をしたいとき、新しめのバージョンでないと(最新版は2009年2月11日にリリースされた 0.7.0)固有値計算(scipy.sparse.linalg)ができなかったりするので、自分でインストールしたほうがいいかもしれない。あと、Ubuntu の apt-get でインストールされるバージョンは blas/atlas/lapack を使ってくれないようで、速くしたいのであればいずれにせよ自分でビルドしたほうがいい。
- NumPy
- 実は上記 SciPy も NumPy を用いているのだが、疎行列の計算が必要ないときは NumPy で十分だったりする(numpy.matrix)。
- PySparse
- 逆に疎行列しか扱う予定がなければこちらの PySparse がいいかも。(インストールには NumPy が必要) 個人的には最新版の SciPy があれば PySparse は使わなくていいとは思うが、PySparse のほうが歴史があってこなれているので、変なことが起こりにくいかもしれない。
- CVXOPT
- Python で凸最適化するためのパッケージ。最新バージョン(1.1.1)で疎行列を扱えるようになった(cvxopt.spmatrix)。いろんなソルバーを使いたいときはこれ。(単に固有値計算したいとか、power method 使いたいだけであれば、上記3つのどれかでよい) ちなみにConvex Optimization という本が全部 PDF ダウンロードでき、その例題のソースコードがこれ使って書かれている。
というのも、4月から NAIST に来る id:smly さんがリンク解析とか: 重要度尺度と von Neumann カーネルで Python を使って PageRank や HITS や von Neumann を書いているので、紹介しようと思った次第。リンク解析おもしろいですよね ;-)
cf.
