パーコレーションと連結性の相転移

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

📎 前提：Erdős–Rényiランダムグラフ・次数・道・連結成分　|　関連：攻撃耐性とロバスト性

要点（BLUF）

パーコレーション：ノード（サイト）またはエッジ（ボンド）をランダムに残す確率 $f$ を変えると、巨大連結成分が臨界点 $f_c$ で突然出現する相転移。
ER の連結性相転移（Erdős–Rényiランダムグラフ）と同じ現象を、「壊す／繋ぐ」という逆方向から見たもの。
臨界点は次数分布で決まる。スケールフリーでは $f_c \to 0$ — ランダム故障に極めて強い。

概念：繋がりは臨界点で一気に立ち上がる

ネットワークのノードを少しずつランダムに残していくと、ある割合を超えた瞬間に「全体を貫く巨大な塊」が現れます。逆にノードを抜いていくと、ある点で塊が砕け散る。この急激な切り替わりがパーコレーション転移です。ER の巨大連結成分（Erdős–Rényiランダムグラフ）と数学的に同じで、ネットワークの頑健性（攻撃耐性とロバスト性）を理解する鍵になります。

数式：臨界点

各ノードを独立に確率 $f$ で残す（サイトパーコレーション）。 $f$ が小さいとネットワークは小さな断片に分かれ、 $f$ が大きいと巨大連結成分（giant component）が存在します。その境目が浸透閾値 $f_c$ 。

Molloy–Reed の判定条件より、巨大連結成分が存在する条件は

\frac{\langle k^2 \rangle}{\langle k \rangle} > 2

ランダムに割合 $1-f$ のノードを除いた後の臨界点は、次数分布のモーメントで

f_c = \frac{1}{\dfrac{\langle k^2 \rangle}{\langle k \rangle} - 1}

ここが決定的：スケールフリーネットワーク（スケールフリー（Barabási–Albert））では $\langle k^2 \rangle$ が発散するため $f_c \to 0$ 。つまりほぼ全ノードを壊しても巨大連結成分が残る — ランダム故障に対して異常に頑健です。

コードで確認

import networkx as nx
import numpy as np

n = 1000
G = nx.barabasi_albert_graph(n, 2, seed=4)

for f in [0.2, 0.5, 0.9]:               # ノードを割合 f だけ残す
    sizes = []
    for s in range(20):
        rng = np.random.default_rng(s)
        keep = [v for v in G if rng.random() < f]
        H = G.subgraph(keep)
        if H.number_of_nodes() == 0:
            sizes.append(0); continue
        gcc = max(nx.connected_components(H), key=len)
        sizes.append(len(gcc) / n)
    print(f"ノード残存率 f={f}: 最大連結成分の割合 = {np.mean(sizes):.3f}")

実行結果：

ノード残存率 f=0.2: 最大連結成分の割合 = 0.033
ノード残存率 f=0.5: 最大連結成分の割合 = 0.379
ノード残存率 f=0.9: 最大連結成分の割合 = 0.897

残存率を上げるほど巨大連結成分が育つ。 $f=0.2$ では断片化（3%）、 $f=0.9$ ではほぼ全域（90%）が1つに繋がります。 $f$ を連続的に動かすと、最大成分の割合が臨界点付近で急に立ち上がる — パーコレーション転移の典型像です。

相転移の図解

graph LR
    Low["f < fc<br/>断片だらけ<br/>巨大成分なし"] -->|"fを上げる"| Crit["f = fc<br/>臨界点"]
    Crit -->|"さらに上げる"| High["f > fc<br/>巨大連結成分が出現"]

数式の直観的意味

条件 $\langle k^2 \rangle / \langle k \rangle > 2$ は、「ある隣をたどった先で、さらに新しい枝が平均1本以上出るか」を表します。ランダムウォークで隣に進むと、次数の大きいノードに着きやすい（サイズバイアス）ので、出発点の平均次数 $\langle k \rangle$ ではなく $\langle k^2 \rangle / \langle k \rangle$ が効く。この「枝の自己再生産」が臨界を超えると連鎖が止まらず、巨大成分が立ち上がります。スケールフリーで $f_c\to 0$ なのは、わずかに残ったハブが全体を繋ぎとめるからです。

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

サイトとボンドのパーコレーションは別物（だが似た転移）：ノードを除くか、エッジを除くか。閾値の値は異なります。
$\langle k \rangle$ ではなく $\langle k^2 \rangle/\langle k \rangle$ が効く：平均だけ見ると分布の裾の効果（ハブの威力）を見落とします。
ランダム故障に強い＝あらゆる攻撃に強い、ではない：スケールフリーはランダムには強いが、ハブ標的攻撃には脆い（攻撃耐性とロバスト性）。

対応シミュレーション

本文のコードがそのまま検証用です。標的攻撃との対比は攻撃耐性とロバスト性。