Mímisbrunnr知恵の泉

← ネットワーク科学 一覧

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

📎 前提：パーコレーションと連結性の相転移・スケールフリー（Barabási–Albert）　|　関連：拡散と感染症モデル（SI・SIS・SIR）

要点（BLUF）

概念：壊し方で強さが変わる

「このネットワークは頑健か」という問いには、「どう壊すか」を添えないと答えられません。ランダムに故障するのか、敵が要所を狙い撃つのか。パーコレーション（パーコレーションと連結性の相転移）はランダム除去でしたが、現実にはハブを狙う攻撃もあります。スケールフリー（スケールフリー（Barabási–Albert））はこの2つで正反対の挙動を見せます。

数式：頑健性の指標

ノードを順に除去しながら、残った最大連結成分のサイズ S(q)S(q)（qq＝除去割合）を追います。頑健性の代表的な指標は

R=1n∑q=1/n1S(q)R = \frac{1}{n} \sum_{q=1/n}^{1} S(q)

除去の全過程で巨大成分がどれだけ大きく保たれたかの平均。除去順序が2通りあります。

コードで確認

import networkx as nx
import numpy as np

def robustness(G, order):
    n = G.number_of_nodes()
    H = G.copy()
    fracs = []
    for v in order:
        if v in H:
            H.remove_node(v)
        if H.number_of_nodes() > 0:
            gcc = max(nx.connected_components(H), key=len)
            fracs.append(len(gcc) / n)
        else:
            fracs.append(0)
    return fracs

G = nx.barabasi_albert_graph(500, 2, seed=8)
rng = np.random.default_rng(0)
rand_order = list(rng.permutation(list(G.nodes())))                 # ランダム故障
targ_order = [v for v, _ in sorted(G.degree(), key=lambda x: -x[1])] # 標的攻撃(次数降順)

print("100ノード除去後の最大連結成分割合:")
print(f"  ランダム故障 : {robustness(G, rand_order[:100])[-1]:.3f}")
print(f"  標的攻撃(ハブ): {robustness(G, targ_order[:100])[-1]:.3f}")

実行結果：

100ノード除去後の最大連結成分割合:
  ランダム故障 : 0.778
  標的攻撃(ハブ): 0.028

同じ500ノードのスケールフリーから100ノード（20%）を除去。ランダム故障なら巨大成分は78%も残るのに、ハブから狙い撃つと**わずか3%**まで崩壊。同じ数を抜いても、どこを抜くかで結果が桁違いです。

「robust yet fragile」の図解

graph TD
    SF["スケールフリー<br/>ネットワーク"] --> R["ランダム故障<br/>→ 低次数ノードが大半<br/>→ 巨大成分は保たれる（頑健）"]
    SF --> T["標的攻撃（ハブ除去）<br/>→ 全体を繋ぐ要が消える<br/>→ 急速に断片化（脆弱）"]

数式の直観的意味

スケールフリーが「ランダムに強くハブに弱い」のは、次数分布の偏りそのものの帰結です。ランダムに1ノード選ぶと、ほぼ確実に低次数の末端（数は多いが繋がりへの貢献は小さい）が当たる — だから抜いても全体は揺らがない。一方ハブは全体の連結を一手に担っており、fc→0f_c\to 0（パーコレーションと連結性の相転移）の頑健性も、その少数のハブに依存している。だからハブを狙えば一気に崩れる。頑健性の源泉（ハブ）が、同時に最大の弱点でもある、というのがこの二面性の核心です。免疫戦略（拡散と感染症モデル（SI・SIS・SIR））でハブを優先接種するのも同じ理由です。

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

対応シミュレーション

本文のコードがそのまま検証用です。

関連