DouKaku?

ページランク - Wikipediaを求めるプログラムを作ってください。(PageRankはGoogleの商標です)

詳しい導出方法はGoogle の秘密 - PageRank 徹底解説の3章に載っていますが、 簡単に説明すると

1. ページがn枚ある場合、n×nの2次元配列を用意する。
2. ページiからページjにリンクがある場合、mat[j][i] = 1 / num_link[i]とする。ただしnum_link[i]はi番目のページから出ているリンクの総数。
3. 行列計算ライブラリを使ってできあがった2次元配列の固有値、固有ベクトルを求める。
4. 出力された固有ベクトルから合計が1になるようなPageRankを算出する

という流れになります。

Pythonで表現すると下のようになります。 ?????の部分は空行を入れて10行でしたので 何百行ものコードになってしまった場合は きっとお題の趣旨から外れていると思います。 このお題の趣旨は「行列計算ライブラリを使って」PageRankを計算することなので、 自力で固有値の計算を実装することは求められていません。

data = {
    1: [2, 3, 4, 5, 7],
    2: [1],
    3: [1, 2],
    4: [2, 3, 5],
    5: [1, 3, 4, 6],
    6: [1, 5],
    7: [5],
}

?????

print pagerank
# [0.303514376997, 0.166134185304, 0.140575079872,
#  0.105431309904, 0.178913738019, 0.0447284345048,
#  0.0607028753994]

このお題はところてんさんの「行列演算系のお題が欲しい」という要望を元に考えたものです。ありがとうございました。

行列やグラフの基本的な操作が用意されているので、
それらを使って実装しました。

隣接リストからそのまま計算してもいいのですが、
グラフを引数にする関数にしておいたほうが、
汎用性は高いでしょう。

aList = {{2, 3, 4, 5, 7}, {1}, {1, 2}, {2, 3, 5}, {1, 3, 4, 6}, {1, 5}, {5}};
graph = FromAdjacencyLists[aList, Type -> Directed];

このようにグラフを作ってから、

pageRank@graph

として計算します。結果は

{0.303514, 0.166134, 0.140575, 0.105431, 0.178914, 0.0447284, 0.0607029}

（主記憶で処理できないようなものには対応していません。）

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

Needs@"DiscreteMath`Combinatorica`";

pageRank[graph_Graph] := Module[{
  aMatrix = ToAdjacencyMatrix@graph,
  eigenVector
  },
  aMatrix = Transpose[(#/Total@#)&/@aMatrix];
  eigenVector = First@Eigenvectors@N@aMatrix;
  eigenVector/Total@eigenVector
]

グラフが疎な場合はSparseArrayを使うと劇的に速くなります。

変更点は2点です。
・行列をSparseArrayにする
・固有ベクトルを一つだけ求める
（絶対値最大固有値の固有ベクトルが返る）

使い方は変わりません。

ノード数1000、エッジ数10000のグラフで試したところ、
2桁ほど速くなりました。
（私のMathematica 5.2で30秒から0.38秒に）

1
2
3
4
5
6
7
8

pageRank2[graph_Graph] := Module[{
  aMatrix = SparseArray@ToAdjacencyMatrix@graph,
  eigenVector
},
  aMatrix = SparseArray@Transpose[(#/Total@#) & /@ aMatrix];
  eigenVector = First@Eigenvectors[N@aMatrix, 1];
  eigenVector/Total@eigenVector
]