Erdős–Rényiランダムグラフ｜ネットワーク科学

🎓 レベル：標準　|　重要度：A（必須）

📎 前提：次数・道・連結成分・次数中心性と次数分布　|　関連：パーコレーションと連結性の相転移

要点（BLUF）

G(n,p)： $n$ ノードのすべての対に、独立に確率 $p$ でエッジを張る最も単純なランダムグラフ。
平均次数 $\langle k \rangle = (n-1)p$ 。次数分布は二項分布（大 $n$ でポアソン）で、裾が薄くハブが出ない。
$\langle k \rangle = 1$ を境に巨大連結成分が突然出現する（相転移）。ランダムグラフ理論の金字塔。

概念：いちばん素朴なランダムネットワーク

「ネットワークがランダムだったら、どんな性質になるか」。その基準を与えるのが Erdős–Rényiモデル（ER）です。すべてのノード対について、コインを振って確率 $p$ で繋ぐ。たったこれだけのモデルが、連結性の相転移という美しい現象を生み、現実ネットワークと比較する「帰無仮説」になります。

数式による定義

$G(n,p)$ モデルは、 $n$ ノードの $\binom{n}{2}$ 個の各対に独立に確率 $p$ でエッジを置きます。

エッジ数の期待値： $\mathbb{E}[m] = \binom{n}{2} p$
平均次数： $\langle k \rangle = (n-1)p \approx np$
次数分布： $P(k) = \binom{n-1}{k} p^k (1-p)^{n-1-k}$ （二項分布）。 $n$ が大きく $\langle k \rangle$ 一定ならポアソン分布 $P(k) \approx e^{-\langle k\rangle}\langle k\rangle^k / k!$ に近づきます。

ポアソン分布は平均のまわりに鋭く集中するので、ER グラフには「飛び抜けて次数の大きいハブ」が存在しません。これが現実ネットワークとの決定的な違いです（スケールフリー（Barabási–Albert））。

相転移：巨大連結成分の出現

ER グラフの最重要の性質は、平均次数 $\langle k \rangle = np$ を制御パラメータとする相転移です。

\langle k \rangle < 1 \;\Rightarrow\; \text{最大成分は } O(\log n)（小さい断片だらけ）

\langle k \rangle > 1 \;\Rightarrow\; \text{サイズ } O(n) \text{ の巨大連結成分が出現}

しきい値 $\langle k \rangle = 1$ （＝ $p=1/n$ ）を超えた瞬間に、ネットワーク全体を覆う巨大な塊が立ち上がります。これはパーコレーション（パーコレーションと連結性の相転移）と本質的に同じ現象です。

コードで確認

import networkx as nx
import numpy as np

n = 500
# 平均次数 <k> = np を 0.5, 1.0, 2.0 と変えて最大連結成分を見る
for k in [0.5, 1.0, 2.0]:
    p = k / (n - 1)
    sizes = []
    for seed in range(20):
        G = nx.erdos_renyi_graph(n, p, seed=seed)
        gcc = max(nx.connected_components(G), key=len)
        sizes.append(len(gcc) / n)
    print(f"<k>={k}: 最大連結成分の割合(平均) = {np.mean(sizes):.3f}")

実行結果：

<k>=0.5: 最大連結成分の割合(平均) = 0.018
<k>=1.0: 最大連結成分の割合(平均) = 0.132
<k>=2.0: 最大連結成分の割合(平均) = 0.797

$\langle k \rangle = 0.5$ では最大成分はわずか2%（断片だらけ）。しきい値 1 を超えて $\langle k \rangle = 2$ になると、一気に約80%のノードが1つの巨大成分にまとまります。連続的にパラメータを動かしただけで、構造が質的に飛躍するのが相転移です。

数式の直観的意味

相転移のしきい値 $\langle k \rangle = 1$ は「枝分かれが自分を再生産できるか」の境目です。あるノードから出発して隣をたどると、平均 $\langle k \rangle$ 本の新しい枝が出る。 $\langle k \rangle < 1$ なら枝は世代を経るごとに細り、すぐ尽きる（小さな成分）。 $\langle k \rangle > 1$ なら枝が指数的に増殖し、ネットワーク全体に到達する（巨大成分）。これは分岐過程（branching process）の臨界条件そのものです。

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

ER は現実ネットワークの良いモデルではない：次数分布がポアソンでハブが出ず、クラスタ係数も低すぎる（ $C \approx p \to 0$ ）。あくまで基準として使います。
$G(n,p)$ と $G(n,m)$ は別物（でも漸近的に等価）：前者はエッジ数が確率変数、後者はエッジ数 $m$ を固定。
相転移は $n\to\infty$ の漸近的な話：有限 $n$ ではしきい値付近がぼやけます（上の実験の $\langle k\rangle=1$ で13%が出ているのはそのため）。

対応シミュレーション

本文のコードがそのまま検証用です。相転移の一般論はパーコレーションと連結性の相転移。