SE Can't Code

A Tokyo based Software Engineer. Not System Engineer :(

PythonでPageRankを実装する

この世界で最も有名なプロダクトの一つであるGoogle検索エンジンですが、その検索エンジンを実現しているPageRankというアルゴリズムについてPythonで実装したいと思います。

PageRank

Webで文字列の検索をかけると最も適したWebページが検索結果の上位に表示されます。この「適したWebページ」のランク付けを行っているのが、Google先生が開発したPageRankというアルゴリズムになります。PageRankはリンクを元にページをランク付けしており、その考え方は学術論文の評価と似ています。

  • 学術論文の重要性を測る指標としては、被引用数がよく使われる。重要な論文はたくさんの人によって引用されるので、被引用数が多くなると考えられる。同様に、注目に値する重要なウェブページはたくさんのページからリンクされると考えられる。
  • また、被引用数を用いる考え方以外にも、「被引用数の多い論文から引用されている論文は、重要度が高い」とする考え方が以前から存在した。ウェブページの場合も同様に、重要なページからのリンクは価値が高いと考えられる。
  • ただし、乱発されたリンクにはあまり価値がないと考えられる。リンク集のように、とにかくたくさんリンクすることを目的としている場合には、リンク先のウェブページに強く注目しているとは言い難い。
    (Wikipedia引用)


このPageRankが優れている点としては、当時のスパムを回避して適切な検索結果を導き出したところにあります。意図的に乱発されたリンクを設定しているスパムは検索順位を上げようとした試みであるわけですが、PageRankアルゴリズム上、数多くのリンクを持つページからのリンクであると、人気度は下がります。逆に少ないリンクを持つページからのリンクであると人気度が上がることになります。このため、ごくわずかなリンクを持つページには価値があり、長いリンク集のリストを持つページはランクにあまり影響を与えません。


数式

ページ{ \displaystyle
p=Page
}

ページ数{ \displaystyle
N=Number Of Pages
}   

タイムステップ{ \displaystyle
t=TimeStep}

減衰定数{ \displaystyle
d=0.8(Damping Constant)
}


ベースケース
{ \displaystyle
rank(0, url)
}{ \displaystyle
1/N
}

再帰ケース
{ \displaystyle
rank(t, url)
} → \( \mathcal\sum_{p∈inlinks[url]}rank(t-1, p)/outlinks[p]*d+(1-d)/N\ \)


ベースケースで全てのページのランクを1と定義します。また、各リンクに対して同じランクを付けたくないため、外部リンクの数(N)で割ることで変化をもたせます。
リンクを自動的に辿っていく仕組みをランダムサーファーモデルと言います。ランダムサーファーはページの人気度を測るためにランダムでページを選択しリンクを辿ります。その行為をアルゴリズムが、timestepが0になるまで再帰的に繰り返した末、各ページに辿り着いた数を数えれば、それが最終的なページのランクとなります。
計算の際に注意しなければいけないことは、どこからもリンクが貼られていないページはランクが0になることです。そうしたケースは持ちたくないので、ランダムサーファーがリンクがあるページに辿りつくようにランダムな可能性を持たせます。そのために減衰関数dを定めます。減衰値の典型的な数値は1未満で、よい数値で0.8ぐらいです。合理的な幅に収めたいのならば1から開始するのではなく、その値をページの合計数(N)で割ります。


コード

以下がPythonで実装したコードになります。

実際にPageRankを実装している関数は compute_ranks()となります。
このコードのみだとテストページがないので結果は得られませんが、Udacityのテストケースを使うと以下のような結果が得られます。

テスト結果

{'http://udacity.com/cs101x/urank/kathleen.html': 0.11661866666666663,  
 'http://udacity.com/cs101x/urank/zinc.html': 0.038666666666666655,  
 'http://udacity.com/cs101x/urank/hummus.html': 0.038666666666666655,  
 'http://udacity.com/cs101x/urank/arsenic.html': 0.054133333333333325,  
 'http://udacity.com/cs101x/urank/index.html': 0.033333333333333326, 
 'http://udacity.com/cs101x/urank/nickel.html': 0.09743999999999997}

この検索ランキングのインデックスが作り終えたら、検索したい文字列に引っかかるページをクイックソート等を使って順番に表示すれば、簡単な検索エンジンの完成です。たった100行超で書けてしまうところが感動ものですね。
その先としては、形態素解析N-gramといった文字列の扱いによって検索の質を考えることになるのですが、それはまたいずれやりたいです。


参考資料

https://www.udacity.com/course/cs101

http://cl.naist.jp/~shimbo/courses/2008_advanced_information_science_ii_and_iv/pdf/lecture_1.pdf

http://homepage2.nifty.com/baba_hajime/wais/pagerank.html