PageRankとHITSアルゴリズム

PageRankとHITSは、ウェブページの重要性や権威を、ページコンテンツのみからではなく、ハイパーリンクトラフの構造から推定するリンク解析アルゴリズムである。

Definition

PageRankは、各ページにクエリに依存しない重要度スコアを割り当てる。このスコアは、発リンクをダンピング確率でたどり、それ以外の場合はテレポートするランダムサーファーの下での定常確率に等しい。一方HITSは、クエリ依存のサブグラフに対して、価値あるコンテンツを持つページのオーソリティスコアと、優れたオーソリティにリンクするページのハブスコアを計算し、それぞれが互いを強化する。

Scope

このトピックでは、リンク解析の2つの基礎的なアルゴリズムについて扱う。1つは、テレポートを伴うランダムサーファーモデルに基づく、クエリに依存しないページ重要度を測るPageRank、もう1つは、相互に強化し合うハブスコアとオーソリティスコアを計算するクエリ依存型のHITSである。これらのアルゴリズムの根底にあるランダムウォークと固有ベクトルによる定式化、ダンピングとテレポートの役割、収束、およびトピックに特化したバリアントについて論じる。これらのスコアがテキスト特徴とどのように組み合わされて最終的なランキングを形成するかについては、ウェブ検索ランキングの範疇であるため、本トピックでは扱わない。

Core questions

• ランダムサーファーモデルはPageRankを定常分布としてどのように定義するのか？
• PageRankが明確に定義されるために、ダンピングまたはテレポート因子が必要なのはなぜか？
• HITSにおけるハブスコアとオーソリティスコアはどのように互いを強化し合うのか？
• これらのスコアはどのように反復的に計算され、いつ収束するのか？
• PageRankとHITSは、クエリ独立型とクエリ依存型でどのように異なるのか？

Key concepts

• PageRank
• ランダムサーファーモデル
• ダンピング因子とテレポート
• 定常分布 / 主固有ベクトル
• HITS
• ハブとオーソリティ
• クエリ独立型 vs. クエリ依存型スコアリング
• べき乗法と収束

Key theories

PageRankランダムサーファーモデル

ダンピング因子に等しい確率でリンクをたどり、それ以外の場合はランダムなページにジャンプするサーファーをモデル化すると、マルコフ連鎖が生成される。その一意な定常分布は、長期的な訪問によってページにスコアを付け、安定したクエリに依存しない重要度尺度を提供する。

HITSハブとオーソリティ

クエリに焦点を当てたサブグラフ内で、HITSは各ページに、そのページにリンクするページのハブスコアに比例するオーソリティスコアと、そのページがリンクするページのオーソリティスコアに比例するハブスコアを割り当てる。これらは、相互に強化し合う関係を収束するまで反復して計算される。

Clinical relevance

PageRankは大規模なウェブ検索の台頭において中心的役割を果たし、グラフにおける重要性と権威の概念的な参照点として現在も残っている。リンク解析のアイデアは、ウェブを超えて引用ネットワーク、ソーシャルネットワークにおける影響力、詐欺検出、レコメンデーションなど、推薦のようなリンクが情報を運ぶあらゆる分野に一般化される。

History

1998年と1999年に、ハイパーリンクが権威を符号化していることを示す2つのほぼ同時期の提案があった。クラインバーグのHITSと、ペイジおよびブリンのPageRankである。PageRankのクエリに依存しないグローバルに計算されるスコアは、ウェブスケールでのサービス提供に非常に適していることが証明され、主要な検索エンジンの基盤となった。一方、HITSはトピック抽出やその後のグラフランキング研究に影響を与えた。

Key figures

• Larry Page
• Sergey Brin
• Jon Kleinberg
• Rajeev Motwani

Seminal works

• page1999
• kleinberg1999
• brin1998

Frequently asked questions

PageRankとHITSの違いは何ですか？

PageRankは、ウェブグラフ全体から事前に各ページに対して単一のクエリに依存しない重要度スコアを計算します。一方HITSは、検索時にクエリを中心に構築された小さなサブグラフ上で、クエリに依存するハブスコアとオーソリティスコアを計算します。PageRankはウェブサービスにより容易にスケールします。

PageRankにダンピング因子が必要なのはなぜですか？

ダンピング因子がないと、ランダムサーファーは発リンクのないページやサイクルに閉じ込められる可能性があり、定常分布が一意でなかったり、明確に定義されなかったりする可能性があります。ダンピング（テレポート）確率は、サーファーが時折ランダムなページにジャンプすることを可能にし、一意で適切に振る舞うスコアを保証します。