ランダムサーファーモデルでPageRankを解釈する方法
PageRankを説明するのによく用いられるランダムサーファーモデルについて簡単にまとめる。
目次
要点
- ランダムサーファー
- ランダムウォークとランダムジャンプをひたすら繰り返す
- ランダムウォーク
- 無作為にリンクを遷移する
- ランダムジャンプ
- 無作為にどっかに飛んでいく
- PageRankの値
- ランダムサーファーがそのページにいる確率のこと
ランダムサーファーを改良するポイントは2箇所
- ランダムウォークする方法を賢くする
- ランダムジャンプする方法を賢くする
ランダムサーファーとは
ランダムサーファーとは、闇雲にネットサーフィンをし続ける、極めて低知能なウェブ巡回者である。
ランダムサーファーはあるWebページにいる時、次に移動するページを次のように決定する。
- αの確率で、そのページから出ているリンクの中から1つをランダムに選び、リンク先に移動する。
- 1-αの確率で、Web上のあらゆるページの中から1つをランダムに選び、そこにジャンプする。
ランダムサーファーとPageRankの関係
Web上を動き回るランダムサーファーが1人いるとしよう。
彼はランダムウォークとランダムジャンプを繰り返しながらWeb上をひたすら動き回る。
長い時間が経つと、このランダムサーファーが個々のページに滞在している確率は、ある一定の定常状態に落ち着く。
このとき、ランダムサーファーがあるページに滞在している確率がそのページにおけるPageRankである。
ランダムサーファーの問題点
先ほど「極めて低知能」と表現した理由は次の通り
- 普通のページ閲覧者は、ランダムにリンクを選ばず、主観的によさそうなリンクを選択する
- ランダムサーファーは広告だろうが明らかなスパムリンクだろうがお構いなしに選択する。
- 普通のページ閲覧者は、興味のある事柄について書いてあるページにジャンプする
- ランダムサーファーはスパムページにも等確率でジャンプする
次回以降で紹介していくPageRankの亜種達は基本的に、ランダムサーファーをもっと賢くしようとするものだと言える。
ここまで読めば明らかなように、単純なランダムサーファーの改造方法は大きくわけて以下の2通りが考えられる
- ランダムウォークする方法を賢くする
- ランダムジャンプする方法を賢くする
余談：ランダムサーファーモデルからPageRankの式を導出してみる
冗長なので以下"ランダム"は書かない。つまり、ランダムサーファーを単にサーファーと書く。なお、イメージを掴むための説明であるから、必ずしも厳密な説明にはなっていない点を注意されたい。
あるページにサーファーが来る方法はウォークとジャンプの2通り
サーファーが来る ＝ ウォークで来る ＋ ジャンプで来る
ウォークで来るのは、リンク元ページにやってきたサーファーが、そのページへのリンクを選んだ場合
ウォークで来る ＝ Σリンク元ページからウォークでくる
一つ一つのリンクを選ぶ確率は全て等しいので
リンク元ページでちょうどリンクが選ばれる確率 ＝ 1/リンク元ページの出リンク数
また、個々のページにサーファーがいないといけないので
ウォークで来る ＝ Σリンク元ページにサーファーがいた / リンク元ページの出リンク数
ジャンプで来るのは、全てのページで等確率。
ジャンプで来る ＝ 1/全ページ数
サーファーはαでウォーク、1-αでジャンプするので、以上を合わせて考えると
サーファーが来る確率＝αΣサーファーがいた/出リンク数＋(1-α)/全ページ数
つまり、あるページpのPageRank値をpr(p)、ページpの出リンク数を|p|、全ページ数をN、ページpiのリンク元ページ集合をSiとすると
と表される。
