PageRank中心性
- 提唱者
- Page, Brin, Motwani & Winograd
- 年
- 1999
- 種類
- Iterative link-based centrality algorithm
- 系統
- Centrality
この文章は機械翻訳で、まだ確認されていません。 英語の原文を読む
何をする手法か?
PageRankは、リンクベースの中心性アルゴリズムであり、高質なノードがどれだけ多くそのノードを指しているかを測定することによって、有向グラフ内の各ノードに重要度スコアを割り当てる。1999年にスタンフォード大学のラリー・ペイジ、セルゲイ・ブリン、ラジーブ・モトワニ、テリー・ウィノグラードによって導入されたこのアルゴリズムは、Google検索エンジンの数学的基盤となり、ネットワーク科学と情報検索における最も影響力のあるアルゴリズムの一つであり続けている。
手法の背後にある直感
ランダムにリンクをクリックし、時折リンクをたどる代わりに完全にランダムなページにジャンプするランダムウェブサーファーを想像してください。このサーファーが無限にクリックした後、各ページで過ごす時間の割合が、そのページのPageRankです。多くの人気ページがリンクしているため、頻繁に訪問されるページは高いスコアを受け取ります。減衰係数(通常0.85)は、ジャンプするのではなくクリックを続ける確率をモデル化します。
歴史学
PageRankは、ラリー・ペイジとセルゲイ・ブリンによってスタンフォード大学で、彼らのBackRub検索プロジェクトの中核的なランキングメカニズムとして開発され、1998年にGoogleとなった。ラジーブ・モトワニとテリー・ウィノグラードとの共著による基礎技術レポートは1999年に発表された。このアルゴリズムは、大規模な有向ネットワークにおける固有ベクトルベースの中心性の使用を普及させ、HITSやTrustRankを含む後続のリンク分析アルゴリズムに直接的なインスピレーションを与えた。
使うべき場面
PageRankは、有向グラフ内のノードをグローバルな構造的重要性によってランク付けする必要がある場合に特に適しています。特にエッジの方向が承認や影響力(ハイパーリンク、引用、ソーシャルフォロー)をエンコードする場合です。グラフをマルコフ連鎖としてモデル化できると仮定し、クリーンな収束には連結または強連結成分が必要です。無向ネットワークにはあまり適しておらず、HITSやBetweenness Centralityが好まれる場合があり、リンクスパムや人為的に誇張された入次数に敏感になる可能性があります。
限界と注意点
- 有向グラフが必要。無向ネットワークへの適用には規約の選択が必要
- 収束速度は遷移行列のスペクトルギャップに依存し、接続性の低いグラフでは遅くなる可能性がある
- 減衰係数dの選択に敏感。異なる値はランキングを大幅に変更する可能性がある
- リンクファーム操作や人為的に構築されたインリンクに対して脆弱
出典に示された条件は、独立した科学的レビューや分析エンジンによる検証の代わりにはなりません。
強み
- ランダムサーファーマルコフ連鎖モデルによる原理的な確率的基盤
- 疎行列ベクトル積とべき乗法による非常に大規模なグラフへのスケーラビリティ
- グローバルなグラフトポロジーを捉え、他の高スコアノードからの承認を受けたノードを評価する
- ウェブ、引用、生物学、ソーシャルネットワークのドメイン全体で広く検証されている
応用
- ウェブ検索エンジンのランキング:ウェブページのグローバルな権威によって検索結果を順序付けする
- 学術引用分析:科学文献ネットワークにおける影響力のある論文やジャーナルを特定する
- ソーシャルネットワークの影響力測定:フォロワーの評判によってユーザーをランク付けする
- 生物学的ネットワーク分析:タンパク質相互作用および遺伝子調節ネットワークにおけるハブタンパク質または遺伝子を見つける
- 推薦システム:ユーザーアイテム二部グラフを通じて選好シグナルを伝播させる
使い方
使い方
グラフ内のすべてのノードは、ノード総数Nに対して1/Nの等しいPageRankスコアから始まります。この均一な初期化により、どのノードも人工的な先行優位を持たず、最初の反復の前にネットワーク全体で有効な確率分布を提供します。
数式
PR^{(0)}(v_i) = \frac{1}{N}, \quad \forall\, i \in \{1, \ldots, N\}グラフの隣接構造から、列確率行列(column-stochastic transition matrix)Mが構築されます。各エントリM_ijは、jからiへのエッジが存在する場合はノードjの出次数で割った値1、それ以外の場合はゼロです。ダングリングノード( outgoing edges がないノード)は、通常、そのスコアをすべてのノードに均等に再分配することによって処理されます。
数式
M_{ij} = \begin{cases} \frac{1}{\text{out}(v_j)} & \text{if } (v_j \to v_i) \in E \\ 0 & \text{otherwise} \end{cases}PageRankベクトルは、ランダムサーファーの公式を使用して反復的に更新されます。減衰係数d(デフォルト0.85)を使用すると、各ノードは、それをリンクするすべてのノードからのスコアの加重合計のd倍に、(1-d)/Nの基本テレポート確率を受け取ります。このステップは、スコアが安定するまで繰り返されます。
数式
PR^{(t+1)}(v_i) = \frac{1-d}{N} + d \sum_{v_j \in \mathcal{B}(v_i)} \frac{PR^{(t)}(v_j)}{\text{out}(v_j)}各反復後、スコアベクトルの変化のL1ノルムが、小さな許容誤差ε(例:1e-6)と比較されます。変化がこの閾値を下回ると、アルゴリズムは収束し、現在のスコアベクトルが最終的なPageRank分布として返されます。
数式
\left\| PR^{(t+1)} - PR^{(t)} \right\|_1 < \varepsilonよくある落とし穴
- ダングリングノード( outgoing edges がないノード)を無視すると、遷移行列の確率的性質が損なわれ、不正確なスコアにつながる可能性がある
- PageRankを無向グラフに適用する際に、対称遷移モデルに変換せずに使用すると、誤解を招く中心性推定値が生じる可能性がある
- 許容誤差の設定が緩すぎると早期収束につながり、きつすぎるとスコアの変更なしに計算が増加する
- PageRankを特定のグラフコンテキスト内での相対的なランキングではなく、絶対的な重要度指標として解釈すること
よくある質問
減衰係数dは何を表し、どのように選択すべきか?
減衰係数d(通常0.85)は、ランダムサーファーがリンクをたどる確率とランダムノードにテレポートする確率の比率です。1に近い値はアルゴリズムをグラフ構造に敏感にしますが、収束が遅くなり、ランクシンク(rank sink)になりやすくなります。0に近い値は均一なランキングに近づきます。値0.85は、ペイジとブリンによってウェブグラフに対して経験的に検証され、標準的なデフォルト値となっています。
PageRankは次数中心性とどのように異なるか?
次数中心性は、ノードへの直接的な着信リンクの数のみをカウントし、すべてのソースを等しく扱います。PageRankは、各着信リンクをリンク元のノードのスコアで重み付けするため、高ランクノードからの承認は低ランクノードからの承認よりも大きく貢献します。この再帰的な定義は、局所的な接続性だけでなく、グローバルなグラフ構造を捉えます。
PageRankは無向グラフに適用できるか?
はい、ただし注意が必要です。無向グラフは、各無向エッジを2つの有向エッジに置き換えることによって有向表現に変換する必要があります。結果として得られるPageRankスコアはノード次数に比例する関数となり、アルゴリズムは重み付き次数中心性に還元されます。無向ネットワークの場合、固有ベクトル中心性やBetweenness Centralityなどの代替中心性尺度がより情報量が多いことがよくあります。
関連する手法
参考文献
Page, L., Brin, S., Motwani, R., & Winograd, T. (1999). The PageRank citation ranking: Bringing order to the web. Stanford InfoLab Technical Report.
出版物の文献を開くコピーしました。