きまぐれ日記: page popularity と page quality と randomness (PageRank 編)

昨日の話の続きです。よくよく考えてみると、PageRank も無作為性を取り入れたアルゴリズムでした。 PageRank は、Web Page の quality を求める方法の一つです。基本的な考え方は、ネットサーファーが ε の確率で無作為に選んだページにジャンプし、1-ε の確率で現在のページ内のリンクを辿ります。サーファがこの手続きを延々と続けていき、定常状態でのページの滞在時間が PageRank です。 このときの ε で無作為のページにジャンプする行為が、無作為性そのものです。 PageRank に似たアルゴリズムとして、Kleinberg の HITS があります。これは、たくさんのリンクを放出する HUB度 と、たくさんのリンクをもらう Authority度 という二つの quality を page に与え、HUB度 の高いページからリンクされると Authority

[abe_hn]

HITSは無作為性がないため、ゆらぎの問題あり

[mind]

ネットサーファーが ε の確率で「無作為に」選んだページにジャンプし、1-ε の確率で現在のページ内のリンクを辿ります。サーファがこの手続きを延々と続けていき、定常状態でのページの滞在時間が PageRank です。

[yorihito_tanaka]

無作為性への評価