ランダムウォークと拡散の数理

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

📎 前提：グラフの表現・固有ベクトル中心性とPageRank　|　関連：グラフラプラシアンとスペクトル・スペクトルクラスタリング

要点（BLUF）

ランダムウォーク：いまいるノードの隣へ等確率で移る確率過程。遷移行列 $P = D^{-1}A$ で表される。
無向連結グラフの定常分布は次数に比例： $\pi_v = \deg(v)/2m$ 。PageRank はこれにランダムジャンプを加えたもの。
拡散方程式・スペクトル・コミュニティ検出を貫く共通言語。「歩き方」がネットワークの幾何を映す。

概念：グラフの上を歩く

ネットワークの構造を探る最も汎用的な道具がランダムウォークです。いまいるノードから、隣のどれかへランダムに1歩動く。これを繰り返すと、どのノードに長く滞在するか（定常分布）、どれくらいで全体を巡るか（被覆時間）といった量が、ネットワークの幾何を反映します。PageRank（固有ベクトル中心性とPageRank）、スペクトルクラスタリング（スペクトルクラスタリング）、拡散はすべてこの上に立っています。

数式による定義

次数対角行列を $D = \mathrm{diag}(\deg(v))$ 、隣接行列を $A$ とすると、ランダムウォークの遷移行列は

P = D^{-1} A, \qquad P_{vu} = \frac{A_{vu}}{\deg(v)}

各行が確率分布（和が1）。時刻 $t$ の分布 $\mathbf{p}^{(t)}$ は $\mathbf{p}^{(t+1)} = \mathbf{p}^{(t)} P$ で更新されます。

定常分布 $\boldsymbol{\pi}$ は $\boldsymbol{\pi} = \boldsymbol{\pi} P$ を満たす分布。無向・連結・非二部グラフでは一意で、きれいに次数に比例します。

\pi_v = \frac{\deg(v)}{2m}

「次数が高いノードほど、ランダムウォーカーが長く滞在する」。これは固有ベクトル中心性・PageRank が次数と相関する根拠でもあります。

コードで確認

import networkx as nx
import numpy as np

G = nx.karate_club_graph()
A = nx.to_numpy_array(G)
deg = A.sum(axis=1)
P = A / deg[:, None]            # 各行を確率化 = 遷移行列

pi = np.ones(len(A)) / len(A)   # 一様分布から開始
for _ in range(2000):           # べき乗法で定常分布へ
    pi = pi @ P
pi = pi / pi.sum()

theory = deg / deg.sum()        # 理論: 定常分布 ∝ 次数

print("数値計算の定常分布(上位5):", [round(float(x), 4) for x in sorted(pi, reverse=True)[:5]])
print("理論 k/2m   (上位5)     :", [round(float(x), 4) for x in sorted(theory, reverse=True)[:5]])
print("両者の最大差            :", round(float(np.max(np.abs(pi - theory))), 8))

実行結果：

数値計算の定常分布(上位5): [0.1039, 0.0909, 0.0823, 0.0714, 0.0628]
理論 k/2m   (上位5)     : [0.1039, 0.0909, 0.0823, 0.0714, 0.0628]
両者の最大差            : 0.0

数値的に求めた定常分布が、理論値 $\deg(v)/2m$ と完全に一致しました（最大差ゼロ）。ランダムウォーカーの滞在確率は、純粋に次数で決まります。

拡散・PageRank・スペクトルとの接続

graph TD
    RW["ランダムウォーク P=D⁻¹A"] --> PR["PageRank<br/>+ランダムジャンプ"]
    RW --> Diff["拡散方程式<br/>連続時間極限"]
    RW --> Spec["正規化ラプラシアン<br/>L = I - D⁻¹A"]
    Spec --> SC["スペクトルクラスタリング"]

連続時間極限ではランダムウォークは拡散方程式になり、その生成作用素が正規化グラフラプラシアン $L = I - D^{-1}A$ （グラフラプラシアンとスペクトル）。ラプラシアンの固有値・固有ベクトルがコミュニティ構造を露わにするのがスペクトルクラスタリング（スペクトルクラスタリング）です。

数式の直観的意味

定常分布 $\pi_v = \deg(v)/2m$ が成り立つ理由は、詳細釣り合いで見えます。エッジ $(u,v)$ を $u\to v$ に渡る確率流は $\pi_u P_{uv} = \frac{\deg(u)}{2m}\cdot\frac{1}{\deg(u)} = \frac{1}{2m}$ 。逆向き $v\to u$ も同じ $\frac{1}{2m}$ 。どのエッジでも両方向の流れが釣り合うので、次数比例の分布が動かない（定常）。要するに「ランダムウォークは、つながりが多い場所に比例して時間を使う」。これがネットワーク上のあらゆる拡散現象の基礎リズムです。

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

二部グラフでは定常分布に収束しない：周期2で振動する。非二部性（奇数閉路）が収束の条件です（または遅延ウォークを使う）。
定常分布 ≠ PageRank：PageRank はランダムジャンプ項を足したもの。ジャンプがあるから非連結・行き止まりでも一意収束します。
「次数中心性と同じでは?」：定常分布は次数に比例するが、それは無向グラフの話。有向グラフのランダムウォーク定常分布は次数では書けず、まさに PageRank が必要になります。

対応シミュレーション

本文のコードがそのまま検証用です。ラプラシアンとスペクトルはグラフラプラシアンとスペクトル。