固有ベクトル中心性とPageRank｜ネットワーク科学

🎓 レベル：発展　|　重要度：A（必須）

📎 前提：グラフの表現・次数中心性と次数分布　|　関連：ランダムウォークと拡散の数理・グラフラプラシアンとスペクトル

要点（BLUF）

固有ベクトル中心性：自分の重要度＝隣人の重要度の和、という再帰を解く。答えは隣接行列の主固有ベクトル。
べき乗法： $x \leftarrow Ax$ を繰り返して正規化すると主固有ベクトルに収束する。Google の PageRank の原型。
PageRank：有向グラフ＋ランダムジャンプ（減衰因子 $\alpha$ ）で、行き止まりや孤立を回避した安定版。

概念：重要さは伝播する

次数中心性は「友達の数」でした。でも、フォロワー1万人のうち全員が無名アカウントの人と、影響力者10人にフォローされる人 — どちらが重要でしょう。固有ベクトル中心性は「重要な相手とつながるほど自分も重要」という再帰でこれを捉えます。この自己言及をきれいに解くと、線形代数（固有値問題）が現れます。土台は統計の固有値分解（グラフラプラシアンとスペクトル経由で統計へリンク）。

数式による定義

固有ベクトル中心性 $x_v$ は「隣人の中心性の和に比例する」と定義します。

x_v = \frac{1}{\lambda} \sum_{u} A_{vu}\, x_u

全ノードまとめると、これは固有値方程式そのものです。

A\mathbf{x} = \lambda \mathbf{x}

すべての成分が非負である解は、ペロン・フロベニウスの定理により最大固有値 $\lambda_{\max}$ に対応する固有ベクトル（主固有ベクトル）だけ。これを各ノードの中心性とします。

PageRank は有向グラフ向けの改良で、確率 $\alpha$ （≈0.85）でリンクをたどり、確率 $1-\alpha$ でランダムに別ページへジャンプします。

PR(v) = \frac{1-\alpha}{n} + \alpha \sum_{u \to v} \frac{PR(u)}{\deg^{+}(u)}

ランダムジャンプ項のおかげで、行き止まり（出次数0）や孤立部分があっても破綻せず、必ず一意の定常分布に収束します。これはマルコフ連鎖の定常分布で、ランダムウォークと拡散の数理と地続きです。

べき乗法（power iteration）

主固有ベクトルは、適当な初期ベクトルに $A$ を繰り返し掛けて正規化するだけで求まります。

\mathbf{x}^{(t+1)} = \frac{A\mathbf{x}^{(t)}}{\lVert A\mathbf{x}^{(t)} \rVert}

これは「重要度を1ホップずつ伝播させる」操作の反復で、 $\lambda_{\max}$ の固有ベクトル方向に収束します。

コードで確認

import networkx as nx
import numpy as np

G = nx.karate_club_graph()
ev = nx.eigenvector_centrality(G, max_iter=1000)
pr = nx.pagerank(G, alpha=0.85)

te = max(ev, key=ev.get)
tp = max(pr, key=pr.get)
print("固有ベクトル中心性 最大:", te, "=", round(ev[te],3))
print("PageRank 最大:", tp, "=", round(pr[tp],3))
print("PageRank の総和(=1):", round(sum(pr.values()), 6))

# べき乗法を手で回して主固有ベクトルを再現
A = nx.to_numpy_array(G)
x = np.ones(A.shape[0])
for _ in range(1000):
    x = A @ x
    x = x / np.linalg.norm(x)
print("べき乗法の最大成分ノード:", int(np.argmax(x)))

実行結果：

固有ベクトル中心性 最大: 33 = 0.373
PageRank 最大: 33 = 0.097
PageRank の総和(=1): 1.0
べき乗法の最大成分ノード: 33

固有ベクトル中心性も PageRank も最大はノード33。自前のべき乗法でも主固有ベクトルの最大成分が33になり、networkx の結果と一致しました。PageRank の総和が1（確率分布）であることも確認できます。

数式の直観的意味

$A\mathbf{x}=\lambda\mathbf{x}$ は「重要度を隣に配り続けると、向きは変わらず大きさだけ $\lambda$ 倍になる安定状態」を表します。べき乗法はその安定状態を、毎ステップ「隣から重要度を集めて正規化」することで探り当てる作業。PageRank の $1-\alpha$ ジャンプは「たまにテレポートする酔歩者」で、これがあるおかげでネットワークのどこにいても抜け出せ、定常分布が一意に定まります。要するに PageRank ＝ランダムウォーカーが各ノードに滞在する確率です。

⚠️ よくある誤解・落とし穴

無向グラフでの固有ベクトル中心性は次数と相関するが別物：正則グラフでは一致するが、一般には「相手の質」を反映してずれます。
有向グラフの固有ベクトル中心性は発散・ゼロ化しやすい：行き止まりや非強連結で破綻する。だから PageRank のジャンプ項が必要。
$\alpha$ を1に近づけすぎると収束が遅く不安定：0.85 という値は経験的なバランス点です。

対応シミュレーション

本文のコードがそのまま検証用です。ランダムウォークとの等価性はランダムウォークと拡散の数理。