Google PageRank
ここで PageRank という手法 [2] を紹介する．Web page 間の影響力というものをどう考えるかについて，Sergey Brin と Lawrence Page という二人は，Web page のリンクを隣接関係として考え，その固有値問題を解くことでWeb の重要度を計算し，それを Web page のサーチの基礎として利用することを提案した．後にこの二人はこのアルゴリズムを使ったサーチエンジンの会社Google を設立する．この論文には，Jon Kleinberg が既に Web 環境を用いて引用関係をリンクによって表現する場合，これを固有値問題として考えることを提案していると記されている．固有値問題そのものは線形代数で基本的なものとして長年研究されてきた．では PageRank そのものは新しくなく，この二人は運が良かっただけではないかというと私はそうは思わない．シンプルでソリッドなアイデアを実際に世界規模で使えるように実装したというところがすごいことだと思う．また，Web のサイズを考えれば，単に固有値を求めるということも単純ではない．ここでの私の説明は，文献 [9] の書法に従っているが，PageRank の論文[2] ではちょっと違う書法を用いているので注意しておく．
PageRank の論文中, page 4, 2nd paragraph では固有値が，\(R=cAR\)となる c となっている．ここでは\(Mx = \lambda x\) の \(\lambda\)と記述した．したがって，\(\lambda = \frac{1}{c}\) である．PageRank の論文では，Web のグラフは不完全であるため，そのまま固有値計算をすることはできないことを説明している．たとえば，リンク切れを除くことや，リンクがループしている場合などを挙げ，その対策を述べている．基本的にはユーザがリンクをランダムにクリックしていくが，時々リンクとはまったく関係ないランダムなページにも移動するという考えを用いている．すなわち，PageRank は，Web をスキャンして隣接行列を作成し，リンク切れやループなどの処理を行なった後，ランダムに移動する項を加え，Markov matrix を作成して，固有値問題を解くということになる．もちろん，大規模なWeb であるから，固有値を求める手法にも工夫がなされている．
私はこの論文を読んだ時に，線形代数をかくもエレガントに使うアルゴリズムに心酔した．しかもそれが実用として使い易いというところにも感動した．論文そのもの自体興味深いので一読することをおすすめする．その感動は論文を読んでから何年も心のどこかにあったのだろう．友人からの質問を聞いた瞬間に私はこの論文を思い出した．そこでこのような blog を書いているわけである．現在のGoogle のアルゴリズムはスパム対策など様々な改良がなされていると聞いているが，基本的な考えは同じであると思う．
今回で理論編は終了する．次回からは実験編としてここまでに述べた方法を著者のグラフに適用した結果を述べよう．
References
[2] Sergey Brin, Lawrence Page, ``The PageRank Citation Ranking: Bringing Order to the Web,'' Stanford University, Technical Report, 1998[9] Gilbert Strang, ``Introduction to Linear Algebra, 4th Edition'', Wellesley-Cambridge Press, 2009
Comments
Post a Comment