生物医学网络科学Biomedical Network Science
Example02 / 09

随机失效与四种攻击策略的比较，并计算 R 指标

所属专题
网络鲁棒性、渗流与级联失效
下载
Notebook · .py

策略：random（随机删点）；ID（按初始度）；RD（每删一个节点重新计算度，自适应）；RB（每次重算介数，自适应）。 R = (1/N) * sum_{Q=1}^{N} s(Q)，s(Q) 为删去 Q 个节点后最大连通分支的节点比例（Schneider 等 2011）。 为节省时间，RB 每删 1% 的节点才重算一次介数，并用 k=200 个源点近似介数。 解读：BA 网络对随机失效的 R 明显高于攻击；自适应攻击（RD、RB）比按初始度攻击更具破坏性；ER 网络各策略差距较小。

Output输出图

随机失效与四种攻击策略的比较，并计算 R 指标：输出图 1

Output文字输出

BA(m=2)
  random R = 0.424   f_c(1%规则) = 0.912
  ID     R = 0.108   f_c(1%规则) = 0.291
  RD     R = 0.102   f_c(1%规则) = 0.208
  RB     R = 0.100   f_c(1%规则) = 0.231
ER(<k>=4)
  random R = 0.400   f_c(1%规则) = 0.798
  ID     R = 0.251   f_c(1%规则) = 0.532
  RD     R = 0.202   f_c(1%规则) = 0.327
  RB     R = 0.215   f_c(1%规则) = 0.402
星形 RD 攻击 R = 0.16 (手算 4/25 = 0.16)

Code代码

# 策略：random（随机删点）；ID（按初始度）；RD（每删一个节点重新计算度，自适应）；RB（每次重算介数，自适应）。
# R = (1/N) * sum_{Q=1}^{N} s(Q)，s(Q) 为删去 Q 个节点后最大连通分支的节点比例（Schneider 等 2011）。
# 为节省时间，RB 每删 1% 的节点才重算一次介数，并用 k=200 个源点近似介数。
# 解读：BA 网络对随机失效的 R 明显高于攻击；自适应攻击（RD、RB）比按初始度攻击更具破坏性；ER 网络各策略差距较小。
import numpy as np
import networkx as nx

def attack_curve(G, strategy, seed=0, step_frac=0.01):
    H = G.copy(); N = G.number_of_nodes(); rng = np.random.default_rng(seed)
    lcc = lambda H: max((len(c) for c in nx.connected_components(H)), default=0) / N
    if strategy == "random":
        order = list(rng.permutation(list(G.nodes())))
    elif strategy == "ID":
        order = sorted(G.nodes(), key=lambda v: -G.degree(v))
    s = [lcc(H)]
    while H.number_of_nodes() > 0:
        if strategy in ("random", "ID"):
            batch = [order[len(s) - 1]]
        elif strategy == "RD":
            batch = [max(H.degree, key=lambda x: x[1])[0]]
        else:                                          # RB：分批重算近似介数
            m = max(1, int(step_frac * N))
            bc = nx.betweenness_centrality(H, k=min(200, H.number_of_nodes()), seed=seed)
            batch = sorted(bc, key=bc.get, reverse=True)[:m]
        for v in batch:
            H.remove_node(v)
            s.append(lcc(H))
    return np.array(s)

def R_index(s):
    return s[1:].sum() / (len(s) - 1)

def fc_one_percent(s):
    idx = np.argmax(s < 0.01 * s[0])
    return idx / (len(s) - 1)

N = 1000
nets = {"BA(m=2)": nx.barabasi_albert_graph(N, 2, seed=3),
        "ER(<k>=4)": nx.gnm_random_graph(N, 2 * N, seed=3)}
curves = {}
for name, G in nets.items():
    print(name)
    for st in ["random", "ID", "RD", "RB"]:
        s = attack_curve(G, st)
        curves[name, st] = s
        print("  %-6s R = %.3f   f_c(1%%规则) = %.3f" % (st, R_index(s), fc_one_percent(s)))

import matplotlib.pyplot as plt
fig, axes = plt.subplots(1, 2, figsize=(10, 4), sharey=True)
for ax, name in zip(axes, nets):
    for st, ls in zip(["random", "ID", "RD", "RB"], ["-", "--", "-.", ":"]):
        s = curves[name, st]
        ax.plot(np.arange(len(s)) / (len(s) - 1), s, ls=ls, lw=2, label="%s (R = %.3f)" % (st, R_index(s)))
    ax.set_xlim(0, 0.6); ax.set_xlabel("fraction removed f"); ax.set_title(name); ax.legend(fontsize=8)
axes[0].set_ylabel("largest component s(f)")
fig.suptitle("Adaptive attacks are most damaging, especially on BA")
plt.tight_layout(); plt.show()

# 手算小例子：星形与路径（N = 5）
star = nx.star_graph(4); path = nx.path_graph(5)
print("星形 RD 攻击 R =", round(R_index(attack_curve(star, "RD")), 3), "(手算 4/25 = 0.16)")

Run在浏览器中运行

首次加载 Python 环境约需 20–40 秒；可以修改参数后重新运行。

随机失效与四种攻击策略的比较，并计算 R 指标