WebマイニングにおけるPageRankアルゴリズムとは？仕組みと計算方法を徹底解説

PageRankアルゴリズムとは

PageRank（ページランク）は、人間の興味・関心に着目しながら、Webページを機械的かつ客観的に評価する手法です。Web検索エンジンは、検索に不慣れなユーザーへの対応や、従来のランキングサービスを不正に操作しようとするページへの対処を迫られてきました。Webページの複製可能な性質を単純にカウントするだけの評価手法は、こうした操作に対して無防備です。

そこで課題となるのが、Webのハイパーリンク構造を活用し、すべてのWebページに対してグローバルな重要度ランキングを生成することです。このランキングこそが「PageRank」と呼ばれるものです。

バックリンクによる重要度の評価

Webの仕組みは、約1億5,000万のノード（Webページ）と17億のエッジ（ハイパーリンク）からなる巨大なグラフ構造に基づいています。WebページAとBがページCへリンクしている場合、AとBはCの「バックリンク（被リンク）」と呼ばれます。一般に、多くのリンクを受けたページほど重要であり、バックリンクの数も多くなります。一方で、質の高い重要なバックリンクは、その数が少ないという特徴があります。

例えば、Yahooのような著名サイトから1本だけバックリンクを受けているページは、無名の個人サイトから多数のバックリンクを受けているページよりも高く評価されるべきです。つまり、あるページのランクは、そのバックリンク元ページのランクの合計が大きいほど高くなります。

PageRankの簡略化された計算式

以下はPageRankの簡略版です。u、vをWebページとし、Buをページuを指し示すページの集合、Nvをページvからの発リンク数、c（c < 1）を正規化係数とします。すると、PageRankの簡略化された解釈である単純なランキングRは、次のように表せます。

$$\mathrm{R(u)\:=\:c\displaystyle\sum\limits_{v\in{Bu}}\frac{R(v)}{N_v}}$$

ページのランクは、そのページからの発リンク先に均等に分配され、リンク先ページのランクに加算されます。この式は再帰的な構造を持っていますが、この簡略化された関数にはいくつかの問題点があります。

ランクシンク（rank sink）の問題

2つのWebページが互いにのみリンクし合い、さらに別のあるページがそのうちの1つを指しているような場合、反復計算の過程でループが発生します。このループはランクを蓄積し続けるものの、外部へは一切ランクを分配しません。このように、グラフ内のループによって生じる落とし穴は「ランクシンク（rank sink）」として知られています。

PageRankアルゴリズムの処理手順

PageRankアルゴリズムは、まずデータベース内のすべてのURLを数値に変換することから始まります。次に、整数IDでWebページを識別しながら、各ハイパーリンクをデータベースに保存します。その後、リンク構造を親IDでソートし、ダングリングリンク（発リンクを持たないページへのリンク）を除去した上で、反復計算が開始されます。

収束を高速化するには、最適な初期値の割り当てを選択することが重要です。現在の時刻ステップの重みはメモリ上に保持され、前回の重みはディスクから線形時間で読み出されます。重みが収束した後、ダングリングリンクを再度挿入し、ランキングを再計算します。この計算は良好に動作しますが、収束条件を緩めたり、より効率的な最適化手法を採用したりすることで、さらなる高速化も可能です。