# PageRank ## 定義 PageRank は、Web ページ間のハイパーリンク構造からページの「引用重要度」を再帰的に定義する指標である。ページ A にリンクするページを T1...Tn とし、`C(T)` をページ T から出るリンク数、`d` をダンピング係数(通常 0.85)とすると、`PR(A) = (1-d) + d(PR(T1)/C(T1) + ... + PR(Tn)/C(Tn))` と定義される。全 Web ページの PageRank の総和が 1 になる確率分布であり、正規化されたリンク行列の主固有ベクトルに相当する反復計算で求まる。直観的には「ランダムサーファー」モデル(確率 `d` でリンクをクリックし続け、確率 `(1-d)` で飽きて別のランダムページに移るユーザーが、あるページを訪れる確率)として解釈できる。(Source: [[@1998__Computer Networks__The Anatomy of a Large-Scale Hypertextual Web Search Engine]] Section 2.1) ## 横断的知見 - **固有ベクトル中心性は PageRank と独立に、異常検知の文脈で同じ数学的枠組みへ収束した**: [[@2005__Machine Learning__Principle Components and Importance Ranking of Distributed Anomalies]](Begnum & Burgess, 2005)は、ホスト間の相関行列を閾値化した隣接行列 `A` の主固有ベクトル(`Av=λv`)を「ホストの重要度(中心性)ランキング」として使う手法を提案した。これは PageRank の定義(リンク行列の主固有ベクトルに相当する反復計算)と数学的に同型であり、Bonacich (1987) の固有ベクトル中心性を明示的な出典として引用する。両者は「重要なノードは重要な隣接ノードを多く持つ」という同一の循環的定義を、Web ページのハイパーリンク構造(PageRank, 1998)とホスト間の相関ネットワーク(Begnum & Burgess, 2005)という異なるドメインへ独立に応用した点で軌を一にする——**ただし PageRank はダンピング係数 `d` によるランダムサーファーモデル(有向・確率遷移行列)なのに対し、Begnum & Burgess は閾値で 2 値化した無向相関グラフの隣接行列であり、行列の構成方法(有向確率行列 vs 無向 2 値行列)が異なる**。(Source: [[@1998__Computer Networks__The Anatomy of a Large-Scale Hypertextual Web Search Engine]] Section 2.1, [[@2005__Machine Learning__Principle Components and Importance Ranking of Distributed Anomalies]] §5) - **「重要度ランキング」の目的が逆転する応用例がある**: PageRank は最も重要(=よく接続された)ページを見つけることを目的とするのに対し、Begnum & Burgess (2005) は最も接続の弱いノード(complement graph)、すなわち低中心性のホストを異常の指標として着目する。同じ主固有ベクトル計算でも、「上位ランクを探す」か「下位ランクを異常として探す」かは応用ドメインの目的で反転しうることを示す一例。(Source: [[@2005__Machine Learning__Principle Components and Importance Ranking of Distributed Anomalies]] §5) - **統計学の教科書はPageRankを「教師なし学習」の一事例として、マルコフ連鎖の定常分布へ再定式化する**: [[@2009__Springer__The Elements of Statistical Learning - Chapter 14 Unsupervised Learning]] §14.10 は、原論文([[@1998__Computer Networks__The Anatomy of a Large-Scale Hypertextual Web Search Engine]])と同じ再帰的定義 $p_i=(1-d)+d\sum_j(L_{ij}/c_j)p_j$ から出発しつつ、これを行列形式 $p=Ap$ の主固有ベクトル問題として提示し、べき乗法(power method)による反復解法を明示する。さらに $A$ をランダムサーファーの遷移確率行列とみなすと、PageRank解(を $N$ で割ったもの)は既約・非周期的マルコフ連鎖の定常分布に一致すると指摘する。原論文もランダムサーファーモデルとして直観的に提示するが、教科書はこれを「主固有ベクトル計算」という同じ数学的操作を異なる保証(マルコフ連鎖理論による固有値1の一意性の保証)で裏付け直しており、[[@2005__Machine Learning__Principle Components and Importance Ranking of Distributed Anomalies]] の固有ベクトル中心性による異常検知応用と合わせて、「主固有ベクトルによる重要度ランキング」という同一操作が(1)Web検索、(2)分散システムの異常検知、(3)統計的機械学習の教材、という3つの独立した文脈でそれぞれ異なる保証・解釈のもとに再発見されていることが分かる。(Source: [[@1998__Computer Networks__The Anatomy of a Large-Scale Hypertextual Web Search Engine]] Section 2.1, [[@2009__Springer__The Elements of Statistical Learning - Chapter 14 Unsupervised Learning]] §14.10) - **Personalized PageRank (PPR) は「Fault Localization における根本原因ランキング」という第四の独立した文脈で、PageRank の反復更新式をほぼそのまま再利用する**: [[@2026__TSC__A Decentralized Root Cause Localization Approach for Edge Computing Environments]] は、マイクロサービスの依存トポロジグラフに対して `r^(k+1) = αP r^(k) + (1-α)S` という PPR の標準更新式を適用し、異常伝播グラフの中心に近いノードほど根本原因である可能性が高いという仮定のもとで局所化を行う。通常の PageRank が全ノードへ等確率でテレポートするのに対し、パーソナライゼーションベクトル `S` を「異常スコアが高いノード・エッジほど高い事前確率を持つ」ように構成する点が鍵であり、この設計により収束に必要な反復回数を減らしつつ根本原因候補へ収束を誘導する。これは、Begnum & Burgess (2005) の固有ベクトル中心性ベース異常検知(閾値化した無向相関グラフ、非パーソナライズ)とは異なり、有向・重み付き・パーソナライズドな遷移行列を明示的に使う点で、より PageRank 原論文の定式化に忠実な応用である。(Source: [[@2026__TSC__A Decentralized Root Cause Localization Approach for Edge Computing Environments]] Section II-C, III-A) - **PPR の「探索空間削減による高速化」は、グラフ分割という古典的な発想と組み合わせることで、単一の巨大グラフに対する反復計算コストを削減できる**: 同論文は、PPR の時間計算量が O(k·|L|)(辺数 |L| と反復回数 k に比例)であることを踏まえ、通信・コロケーションを考慮してグラフをクラスタに分割し、各クラスタ内でローカルに PPR を実行することで実効的な辺数を縮小する。これは PageRank/PPR 自体のアルゴリズムを変更せず、入力グラフの構造を事前に縮小することで高速化する手法であり、論文が言及する Wang et al. (2022, VLDB Endowment)の edge-based local push のような PPR 近似アルゴリズムとは異なるアプローチである。(Source: [[@2026__TSC__A Decentralized Root Cause Localization Approach for Edge Computing Environments]] Section II-D, III-B) - **分散環境での PPR 近似は、JXP アルゴリズム(P2P Web 検索向け分散 PageRank 近似)を Fault Localization 向けに転用することで実現されている**: クラスタをまたぐ稀な異常伝播ケースに対し、同論文はクラスタ間で低次元の平均近似異常スコアのみを一度交換し、各クラスタが独立に PPR を実行するプロトコルを提案する。これは Parreira et al. (2006, VLDB) の JXP アルゴリズム(P2P Web 検索ネットワーク向けの効率的・分散的な PageRank 近似)の改変版であり、PageRank/PPR の分散近似という 2006 年の問題設定が、20 年後にマイクロサービス障害診断という全く異なるドメインで再利用されていることを示す。(Source: [[@2026__TSC__A Decentralized Root Cause Localization Approach for Edge Computing Environments]] Section III-C) - **教科書向けの平易な解説(MCS 第20章)は、原論文(1998)の定式化を「素朴な入次数カウントがなぜ失敗するか」という失敗例から積み上げて再導出しており、原論文が省略した動機づけを補っている**: [[@2015__MIT__Mathematics for Computer Science - Chapter 20 Random Walks]] §20.2.1 は、まず「入次数の多さ=重要度」という素朴な最初のアイデアを提示し、ダミーページを大量生成して自ページへリンクさせる、あるいは他ページへのリンクを乱発する(「早期投票・頻繁投票」)といった具体的な不正操作の手口を示してこの素朴な指標を退ける。その上で§20.2.2-20.2.3 でランダムサーファーモデル・定常分布としての PageRank を導入する。原論文([[@1998__Computer Networks__The Anatomy of a Large-Scale Hypertextual Web Search Engine]])は既に完成した定式化(ランク行列・ダンピング係数)を提示するのに対し、教科書は「なぜこの定式化が必要か」という設計動機を、入次数ベースの指標に対する具体的な攻撃例から再構成している点が異なる。また MCS はダンピング係数 0.85 について「初期のPageRankでは恣意的にこの値が設定された」(§20.2.2)と明記しており、既存の未解決の問い(ダンピング係数の根拠不明)に対し、少なくとも「当初は経験的というより恣意的(arbitrarily set)な値だった」という追加情報を与える。(Source: [[@2015__MIT__Mathematics for Computer Science - Chapter 20 Random Walks]] §20.2.1-§20.2.2, [[@1998__Computer Networks__The Anatomy of a Large-Scale Hypertextual Web Search Engine]] Section 2.1) - **PageRank を支える数学的保証(定常分布の存在・一意性・収束性)は、原論文が言及しない詳細を MCS 第20章が明示的に扱う**: 原論文はランダムサーファーモデルを直観的に提示するにとどまるが、MCS §20.2.3 は「強連結なグラフは一意な定常分布を持つ」ことを最大希釈率による議論で示し、スーパー頂点の追加(全頁への均等リンク)がグラフを強連結にすることでこの一意性を保証する仕組みを明らかにする。さらに、一般の有向グラフでは定常分布が複数存在しうること、存在しても収束しない場合があることを注意しており、[[定常分布]]の概念ページで詳述する通り、[[@2009__Springer__The Elements of Statistical Learning - Chapter 14 Unsupervised Learning]] のべき乗法による数値計算の記述と合わせて「存在・一意性の保証」(MCS)と「実際の計算法」(ESL)という補完的な役割分担が見える。(Source: [[@2015__MIT__Mathematics for Computer Science - Chapter 20 Random Walks]] §20.2.3) - [出典] PageRank の元祖である Stanford InfoLab テクニカルレポート(1998-01-29 草稿)を追加。既存の主要出典 [[@1998__Computer Networks__The Anatomy of a Large-Scale Hypertextual Web Search Engine]] より詳細な定式化(ランクシンク対策としての Definition 1、ダングリングリンク処理、収束計算アルゴリズム)と実験(3億件超のリンクでの収束が約50反復、log n にほぼ比例)を含む。(Source: [[@1998__TechReport__The PageRank Citation Ranking - Bringing Order to the Web]]) - [出典] E ベクトルのパーソナライズ実験(Netscape ホームページ視点 vs John McCarthy ホームページ視点)により、E を変えることでパーソナライズされたランキングが得られ、かつ E が一様/ルートサーバー全体の場合には操作耐性に差があることを実証している。(Source: [[@1998__TechReport__The PageRank Citation Ranking - Bringing Order to the Web]]) - **Newman (2003) のサーベイは PageRank と Kleinberg の HITS を同一の固有ベクトル問題の枠組みで対比する**: PageRank は隣接行列 A の固有ベクトル方程式 Ax=λx(Perron–Frobenius 定理により非負固有ベクトルは一意)として定式化されるのに対し、HITS は有向網へ拡張し hub 重み y_i・authority 重み x_i を Ay=λx, A^T x=μy で定義する。authority 重みを消去すると AA^T x=λμx となり、両手法の違いは隣接行列を対称積 AA^T に置き換える点にあると整理される。この対比は本 wiki の他ソースには無い視点であり、PageRank と固有ベクトル中心性(ホスト重要度ランキング等)の関係を、リンク構造の非対称性(有向 vs 対称化)という軸でさらに一般化する。(Source: [[wiki/sources/@2003__SIAMReview__The structure and function of complex networks - Chapter 8 Processes taking place on networks|@2003__SIAMReview__...Chapter 8]]) - **Chapter 14 は PageRank を「反復改善の原理」に基づく行列反復として定式化し、原論文が示さない収束の厳密証明を Perron の定理で与える**: 原論文 [[@1998__Computer Networks__The Anatomy of a Large-Scale Hypertextual Web Search Engine]] は PageRank をランダムサーファーモデルとして直観的に導入し、d=0.85 を「経験的な値」として与えるにとどまるが、[[@2010__CambridgeUP__Networks, Crowds, and Markets - Chapter 14 Link Analysis and Web Search]] §14.6-B は、スケール版の更新行列 Ñ が全要素正であることから Perron の定理を適用し、最大固有値 1 に対応する正の固有ベクトルへどの初期ベクトルからも収束することを証明する。原論文はこの収束を前提として扱っている。 - **スケーリングなし PageRank の rank leak(rank sink)問題を、章は具体的な 8 ノード例で可視化する**: 原論文もランクシンク(強連結成分の外への「漏れ」)には言及するが、[[@2010__CambridgeUP__Networks, Crowds, and Markets - Chapter 14 Link Analysis and Web Search]] §14.3 Fig.14.8 は F・G が互いにしかリンクしない例を使い、スケーリングなしでは他の全ノードの PageRank が厳密に 0 に収束し F・G が 1/2 ずつを独占することを具体的に示す。8 ノードという小規模では s=0.8〜0.9 のスケーリングでも「漏れ」の是正が不完全である(F・G が依然大半を占める)ことも脚注で注記されており、原論文にはこの規模依存の注意は無い。 - **Chapter 14 は PageRank を hubs/authorities(HITS)の一段版として位置づける対比を提供する**: 原論文は HITS に触れず PageRank 単独で提示するのに対し、章 §14.3 は「PageRank は直接推薦(direct endorsement)モデル」「HITS は hub と authority を分離する二段モデル」という対比を明示し、競合企業のように直接リンクしないが共通の hub からリンクされる商業的クエリでは HITS が、学術・政府ページのような直接引用が支配的な場面では PageRank が自然、という使い分けの直観を与える。この対比は Newman(2003)サーベイの AA^T への統合的視点(既存の横断的知見参照)とは異なる角度(モデルの想定する推薦様式の違い)からの整理である。 ## 未解決の問い - **PPR ベースの根本原因ランキングにおいて、ダンピング係数 `α` の値は「経験的な値」か、それとも異常伝播の平均ホップ数のような測定可能な系特性から導出できるか**: [[@2026__TSC__A Decentralized Root Cause Localization Approach for Edge Computing Environments]] は `α` を TPE ベースのベイズ最適化でチューニングしているが、原論文が扱うダンピング係数 `d=0.85` の経験的性質(下記)と同様、体系的な感度分析や理論的根拠は示されていない。低い `α` ほど収束が速いことは示されているが、精度とのトレードオフの理論的特徴づけは未解決である。(Source: [[@2026__TSC__A Decentralized Root Cause Localization Approach for Edge Computing Environments]] Section II-C) - PageRank のダンピング係数 `d=0.85` は論文中で「経験的な値」として扱われているが、根拠となる感度分析は本論文(短縮版)には含まれていない。長編版または参考文献 [7](Page, Brin, Motwani, Winograd の "The PageRank citation ranking" マニュスクリプト)にあたる必要がある。[[@2015__MIT__Mathematics for Computer Science - Chapter 20 Random Walks]] §20.2.2 は「初期のPageRankではこの値は恣意的に0.15(=1-d)に設定された(arbitrarily set)」と述べるのみで、この記述も感度分析の欠如という同じ空白を埋めていない。 - PageRank と、本 wiki に既存の他のランキング手法(例: [[アラートランキング]]・[[LLMランキング]]・[[pairwiseランキング]])との関係は未整理。いずれも「複数候補への重要度スコアリング」という共通点があるが、リンク構造ベースか学習ベースかで前提が異なる。AIOps 領域のランキング手法設計に PageRank のグラフ伝播的発想がどこまで応用されているか、今後の ingest で確認する。 - Begnum & Burgess (2005) の閾値化(相関が閾値以上なら 1、未満なら 0)は、PageRank のような重み付き遷移確率でなく 2 値の隣接行列を使う。閾値の選び方がランキング結果に与える感度は論文内で定量評価されておらず、PageRank のダンピング係数 `d` の感度分析同様、この閾値パラメータの頑健性も未解決である。(Source: [[@2005__Machine Learning__Principle Components and Importance Ranking of Distributed Anomalies]]) - **Chapter 14 は PageRank の「重要度低下」説(2003〜2004 年頃の Hilltop 導入等)を紹介するが、この主張の一次資料や定量的根拠(ランキング関数内での重み変化の実測)は章内に示されていない**: 原論文執筆時点(1998年)には存在しなかった事後的な評価であり、原論文・Chapter 14 のどちらの範囲でも検証できない。Google 側の一次資料や第三者による実証研究に当たる必要がある。 ## 関連 - ソース: [[@1998__Computer Networks__The Anatomy of a Large-Scale Hypertextual Web Search Engine]] / [[@2005__Machine Learning__Principle Components and Importance Ranking of Distributed Anomalies]] / [[@2009__Springer__The Elements of Statistical Learning - Chapter 14 Unsupervised Learning]] / [[@2026__TSC__A Decentralized Root Cause Localization Approach for Edge Computing Environments]] / [[@2015__MIT__Mathematics for Computer Science - Chapter 20 Random Walks]] / [[@1998__TechReport__The PageRank Citation Ranking - Bringing Order to the Web]] / [[wiki/sources/@2003__SIAMReview__The structure and function of complex networks - Chapter 8 Processes taking place on networks|Newman 2003 Ch.8]] - entity: [[Sergey Brin]] / [[Lawrence Page]] / [[Google]] / [[Stanford University]] / [[Mark Burgess]] / [[Kyrre Begnum]] - 概念: [[異常検知]] / [[クラスタリング]](同じ教科書内で教師なし学習の一事例として並置される) / [[Fault Localization]](Personalized PageRank による根本原因ランキング) / [[ランダムウォーク]] / [[定常分布]] / [[有向グラフ]] - エンティティ: [[Rajeev Motwani]] / [[Terry Winograd]] / [[Jon Kleinberg]] ## 出典 - [[@1998__Computer Networks__The Anatomy of a Large-Scale Hypertextual Web Search Engine]] - [[@2005__Machine Learning__Principle Components and Importance Ranking of Distributed Anomalies]](§5 固有ベクトル中心性による重要度ランキングの定式化、式 14–16) - [[@2009__Springer__The Elements of Statistical Learning - Chapter 14 Unsupervised Learning]](§14.10、式14.107–14.111) - [[@2026__TSC__A Decentralized Root Cause Localization Approach for Edge Computing Environments]](Section II-C Personalized PageRank の定式化、III-A/B/C 分散実行と JXP ベースの近似) - Eric Lehman, F. Thomson Leighton, Albert R. Meyer, *Mathematics for Computer Science*, revised 2015-05-18, Chapter 20 §20.2.1-§20.2.3(入次数ベース指標の失敗例、ランダムサーファーモデル、定常分布としてのPageRank定義) - [[@1998__TechReport__The PageRank Citation Ranking - Bringing Order to the Web]](PageRank の元祖テクニカルレポート。Definition 1(ランクソース E)、ランダムサーファーモデル、収束計算アルゴリズム、実験(収束速度・検索比較・パーソナライズ・被リンク予測)) - [[wiki/sources/@2003__SIAMReview__The structure and function of complex networks - Chapter 8 Processes taking place on networks|Newman 2003 Ch.8]](PageRank と HITS の固有ベクトル問題としての対比)