简介这份资源面向参加美国数学建模竞赛MCM/ICM的学生与复杂网络初学者聚焦随机图与网络科学常见算法的代码实现帮助读者在赛题建模中快速搭建网络模型、验证拓扑特性。压缩包内共1个文件为MATLAB脚本.m体积约2KB轻量易读可直接运行或按需修改。内容围绕Erdős-Rényi随机图、Barabási-Albert无标度网络、Watts-Strogatz小世界模型等经典模型展开并可能涉及生成树、社区检测、网络动力学、稳健性分析与可视化等方向便于读者理解节点度分布、平均路径长度、聚类系数等核心指标的计算方式。目前已有149人学习适合作为赛前算法速查与代码参考通过阅读和调试脚本可加深对随机图生成机制与网络结构分析流程的掌握为美赛建模提供可复用的实现思路。1. 美赛里随机图代码到底能帮你拿什么分美赛MCM/ICM的题目里只要出现“网络”“传播”“节点”“连接”“鲁棒性”这类词八成就要用到复杂网络建模。而复杂网络里最常被翻牌的就是 random graph——随机图。很多队伍拿到题的第一反应是“建个网络”但真到写代码时才发现节点怎么连、连多少、连出来的图能不能用、跑出来的指标怎么解释全是坑。标题里这份“复杂网络 random graph 算法程序.zip”本质上就是一套帮你跳过“从零手写图生成”的参考代码集合。它解决的不是“要不要建模”的问题而是“怎么在 72 小时内把图生成、指标计算、结果可视化串成一条能写进论文的链路”。适合谁适合已经确定要用网络模型、但卡在代码实现和参数调不明白的参赛队也适合第一次做网络类赛题、想先跑通最小闭环的新手。这一章不展开代码先把随机图在美赛里的定位说清楚它不是万能的但它是你论证“网络结构如何影响结果”时最稳的起点。2. 随机图三件套ER、WS、BA 到底该选哪个2.1 三种图的数学定义与美赛适用场景随机图不是一种图而是一类图的统称。美赛里最常出现的是三种ER 随机图Erdős–Rényi、WS 小世界图Watts–Strogatz、BA 无标度图Barabási–Albert。ER 图的做法是给定 N 个节点每对节点以概率 p 独立连边。它的度分布近似泊松分布特点是“均匀”没有明显的枢纽节点。WS 小世界图从一个环状规则图出发以概率 β 随机重连边特点是平均路径短、聚类系数高适合模拟“熟人网络”“信息在局部密集但全局可达”的场景。BA 图则是“优先连接”新节点更倾向于连到已经有很多连接的节点上最终形成幂律度分布也就是少数节点拥有大量连接适合模拟“舆情传播”“供应链核心企业”“交通枢纽”这类现实网络。选哪个取决于你的赛题问的是什么。如果题目问“随机攻击下网络的鲁棒性”ER 图是基准BA 图对随机攻击更鲁棒但对蓄意攻击更脆弱这个对比本身就是论文亮点。如果题目问“信息传播效率”WS 图的小世界特性会让传播速度明显快于 ER 图。如果题目问“关键节点识别”BA 图的幂律特性会让“度中心性”和“介数中心性”的差异变得非常有讨论价值。我一般会建议先跑 ER 做基准再跑 BA 做对比如果题目涉及“局部聚集”再加 WS。三张图跑完论文的“模型对比”部分就有了。2.2 用 NetworkX 跑通三种图的最小代码下面这段代码是三种图的最小生成与指标计算模板。你不需要装额外库NetworkX 加 Matplotlib 就够。import networkx as nx import matplotlib.pyplot as plt import numpy as np # 参数设置N 节点数p 连边概率k 近邻数beta 重连概率m 新节点连边数 N 500 p 0.02 k 6 beta 0.1 m 3 # ER 随机图 er nx.erdos_renyi_graph(N, p, seed42) # WS 小世界图 ws nx.watts_strogatz_graph(N, k, beta, seed42) # BA 无标度图 ba nx.barabasi_albert_graph(N, m, seed42) # 计算核心指标 def graph_metrics(G, name): avg_deg np.mean([d for n, d in G.degree()]) avg_clust nx.average_clustering(G) # 平均路径长度只对连通图有效不连通时取最大连通子图 if nx.is_connected(G): avg_path nx.average_shortest_path_length(G) else: largest_cc max(nx.connected_components(G), keylen) avg_path nx.average_shortest_path_length(G.subgraph(largest_cc)) print(f{name}: 平均度{avg_deg:.2f}, 聚类系数{avg_clust:.4f}, 平均路径{avg_path:.2f}) graph_metrics(er, ER) graph_metrics(ws, WS) graph_metrics(ba, BA)逻辑说明erdos_renyi_graph(N, p)里 p 是每对节点独立连边的概率p 越大图越密watts_strogatz_graph(N, k, beta)里 k 是每个节点初始连接的近邻数beta 是重连概率beta0 是规则环beta1 是完全随机barabasi_albert_graph(N, m)里 m 是每个新节点连到已有节点的边数m 越大平均度越高。参数怎么调N 一般取 200 到 2000太小指标波动大太大跑得慢。p 的取值要让平均度在 4 到 10 之间也就是 p ≈ 平均度 / N。k 取偶数一般 4 到 10。beta 取 0.05 到 0.3 之间太小接近规则图太大接近随机图。m 取 2 到 5m1 会生成树状图连通性差。跑完这段你会得到三组指标。ER 的聚类系数接近 pWS 的聚类系数远高于 ER 但路径长度接近BA 的聚类系数低但度分布极不均匀。这三个差异就是你论文里“模型选择依据”的硬证据。2.3 度分布画图让评委一眼看懂你的网络类型指标是数字度分布是图。美赛论文里一张清晰的度分布对比图比三行数字更有说服力。fig, axes plt.subplots(1, 3, figsize(15, 4)) for ax, G, name in zip(axes, [er, ws, ba], [ER, WS, BA]): degrees [d for n, d in G.degree()] ax.hist(degrees, bins30, densityTrue, alpha0.7, colorsteelblue) ax.set_title(f{name} 度分布) ax.set_xlabel(度) ax.set_ylabel(频率) plt.tight_layout() plt.savefig(degree_dist.png, dpi150)这段代码的关键是densityTrue它把频数转成频率方便不同 N 的图对比。ER 的度分布像钟形WS 和 ER 接近但尾部略厚BA 的度分布是明显的长尾——少数节点度很高大部分节点度很低。如果你在论文里要论证“该网络存在关键枢纽”BA 的度分布图就是最直接的视觉证据。注意bins 不要设太小30 到 50 之间比较合适太小看不出分布形状太大图会毛糙。3. 把随机图接上传播模型SIR 与级联失效的代码实现3.1 SIR 模型在随机图上的最小实现美赛网络题里传播模型出现频率极高。SIR易感-感染-恢复是最经典的。在随机图上跑 SIR核心就三步选初始感染节点、按边传播、按概率恢复。def sir_on_graph(G, beta0.3, gamma0.1, initial_infected5, steps100): # 初始化状态S0, I1, R2 status {n: 0 for n in G.nodes()} infected np.random.choice(list(G.nodes()), initial_infected, replaceFalse) for n in infected: status[n] 1 history [] for _ in range(steps): new_infected [] new_recovered [] for n in G.nodes(): if status[n] 1: # 感染邻居 for nb in G.neighbors(n): if status[nb] 0 and np.random.rand() beta: new_infected.append(nb) # 恢复 if np.random.rand() gamma: new_recovered.append(n) for n in new_infected: if status[n] 0: status[n] 1 for n in new_recovered: status[n] 2 # 统计 s sum(1 for n in G.nodes() if status[n] 0) i sum(1 for n in G.nodes() if status[n] 1) r sum(1 for n in G.nodes() if status[n] 2) history.append((s, i, r)) if i 0: break return history逻辑说明beta是感染概率gamma是恢复概率。基本再生数 R0 ≈ beta * 平均度 / gamma。当 R0 1 时感染会扩散R0 1 时感染会自然消亡。这个结论在 ER 图和 BA 图上都成立但 BA 图上因为存在超级传播节点早期扩散速度会明显更快。参数怎么设beta 一般 0.1 到 0.5gamma 一般 0.05 到 0.2。如果你要模拟“快速传播但恢复也快”的场景beta0.4、gamma0.3 比较合适如果要模拟“慢传播长病程”beta0.15、gamma0.05。跑完之后把 history 画成三条曲线就是标准的 SIR 曲线图。3.2 级联失效节点移除顺序决定网络生死级联失效是另一个高频考点。做法是按某种策略移除节点看网络什么时候碎裂。常见策略有三种随机移除、按度从大到小移除、按介数中心性从大到小移除。def cascade_failure(G, strategydegree, removal_ratio0.3): G_copy G.copy() n_remove int(len(G_copy) * removal_ratio) if strategy random: nodes_to_remove np.random.choice(list(G_copy.nodes()), n_remove, replaceFalse) elif strategy degree: nodes_to_remove sorted(G_copy.degree, keylambda x: x[1], reverseTrue)[:n_remove] nodes_to_remove [n for n, d in nodes_to_remove] elif strategy betweenness: bc nx.betweenness_centrality(G_copy) nodes_to_remove sorted(bc, keybc.get, reverseTrue)[:n_remove] G_copy.remove_nodes_from(nodes_to_remove) # 计算最大连通子图占比 if len(G_copy) 0: return 0.0 largest_cc max(nx.connected_components(G_copy), keylen) return len(largest_cc) / len(G)逻辑说明removal_ratio是移除比例一般从 0.05 到 0.5 扫一遍画出一条“移除比例 vs 最大连通子图占比”的曲线。随机移除下ER 图和 BA 图都有一定的鲁棒性但 BA 图在蓄意移除高度节点时崩溃得极快——这就是“无标度网络对随机故障鲁棒、对蓄意攻击脆弱”的经典结论。介数中心性计算量大N500 时还能跑N2000 以上建议改用近似算法或只算前 100 个节点。这个对比实验做出来论文的“网络脆弱性分析”部分就稳了。3.3 把传播和失效结果画成论文级图表美赛论文的图第一要求是“自解释”。也就是说评委不看正文只看图和图注就能明白你在说什么。# SIR 曲线 history sir_on_graph(ba, beta0.3, gamma0.1, initial_infected5, steps80) s [h[0] for h in history] i [h[1] for h in history] r [h[2] for h in history] plt.figure(figsize(8, 5)) plt.plot(s, labelS (易感), linewidth2) plt.plot(i, labelI (感染), linewidth2) plt.plot(r, labelR (恢复), linewidth2) plt.xlabel(时间步) plt.ylabel(节点数) plt.title(BA 网络上的 SIR 传播曲线 (beta0.3, gamma0.1)) plt.legend() plt.grid(alpha0.3) plt.savefig(sir_curve.png, dpi150)图注要写清楚网络类型、节点数、关键参数。比如“图 3BA 网络N500, m3上 SIR 模型传播曲线感染概率 beta0.3恢复概率 gamma0.1初始感染节点 5 个”。这样评委不用翻正文就能看懂。级联失效的图同理横轴是移除比例纵轴是最大连通子图占比三条线分别对应随机、度优先、介数优先。线型用实线、虚线、点划线区分颜色用蓝、橙、绿打印成黑白也能分辨。4. 避坑随机图代码在美赛里最容易翻车的五个地方4.1 图不连通导致平均路径长度报错现象跑nx.average_shortest_path_length(G)时直接抛异常NetworkXError: Graph is not connected。原因ER 图在 p 较小时大概率不连通WS 图在 beta 较大时也可能出现孤立节点。解决先判断nx.is_connected(G)不连通就取最大连通子图再算或者直接报告“最大连通子图占比”这个指标。我一般会在论文里同时给出“全图指标”和“最大连通子图指标”后者更有意义。4.2 随机种子没固定结果每次跑都不一样现象同一段代码跑两次SIR 曲线形状差很多级联失效的崩溃点也漂移。原因np.random和 NetworkX 的默认随机源没有固定。解决在代码开头加np.random.seed(42)并且所有图生成函数都传seed42。美赛论文里可复现性是加分项固定种子是最低成本的“后悔药”。如果要做多次实验取平均那就跑 50 次不同种子报告均值和置信区间这样更严谨。4.3 度分布图用默认 bins 导致长尾看不见现象BA 图的度分布画出来像一坨完全看不出幂律特征。原因plt.hist默认 bins10对于度范围 1 到 100 的数据分辨率太低。解决bins 设为 30 到 50并且用densityTrue归一化。如果要做幂律拟合用scipy.stats.powerlaw或手动做 log-log 图看是否近似直线。注意log-log 图里BA 图的尾部应该是一条下降的直线ER 图则是一个快速下坠的曲线。4.4 介数中心性计算太慢比赛时卡死现象N2000 的图跑nx.betweenness_centrality超过 10 分钟。原因精确介数中心性复杂度是 O(N*M)N2000、M6000 时运算量巨大。解决用nx.betweenness_centrality(G, k100)做近似k 是采样节点数一般 50 到 200 就够。或者只对度最高的前 100 个节点算介数其他节点忽略。比赛时时间比精度重要近似结果在论文里注明“采用 k100 近似”即可。4.5 把 ER 图当成“真实网络”直接下结论现象论文里写“该网络度分布近似泊松说明是随机网络”但题目给的数据明显有枢纽节点。原因ER 图是基准模型不是现实网络的拟合模型。解决先算真实数据的度分布看是泊松还是幂律再决定用 ER 还是 BA 做对比。如果真实数据有长尾就用 BA 拟合ER 只作为“如果网络是随机的会怎样”的对照组。这个逻辑在论文里写清楚评委不会扣分反而觉得你严谨。5. 进阶用配置模型生成“指定度分布”的随机图5.1 配置模型从度序列反推图结构前面讲的 ER、WS、BA 都是“生成机制决定度分布”。但美赛里更常见的情况是题目给了你一个真实的度序列或者你从数据里统计出了度分布然后你想生成一个“具有相同度分布但其他方面随机”的图。这就是配置模型Configuration Model。# 假设我们有一个度序列 degree_sequence [3, 3, 2, 2, 2, 1, 1, 1, 1, 1] # 确保度序列是图形化的总和为偶数 if sum(degree_sequence) % 2 ! 0: degree_sequence[0] 1 # 生成配置模型图 G_config nx.configuration_model(degree_sequence, seed42) # 去掉自环和平行边 G_config nx.Graph(G_config) G_config.remove_edges_from(nx.selfloop_edges(G_config)) print(f节点数: {G_config.number_of_nodes()}, 边数: {G_config.number_of_edges()}) print(f平均度: {np.mean([d for n, d in G_config.degree()]):.2f})逻辑说明configuration_model的做法是把每个节点的“度”想象成“半条边”然后随机配对。这样生成的图度分布严格等于输入的度序列但其他性质聚类系数、路径长度是随机的。注意生成的图可能有自环和平行边必须用nx.Graph转成简单图并去掉自环。这个模型在美赛里的典型用法是从真实数据统计度序列生成配置模型作为“零模型”然后对比真实网络和零模型的聚类系数、路径长度如果真实网络的聚类系数显著高于零模型说明网络存在“局部聚集”机制不是纯随机的。5.2 用零模型做假设检验你的网络真的“特殊”吗配置模型最值钱的地方是它可以当零模型用。比如你算出真实网络的聚类系数是 0.35但你不确定这个值算高还是低。那就生成 100 个配置模型图算它们的聚类系数分布看 0.35 落在哪个分位数。def null_model_test(degree_sequence, observed_clustering, n_samples100): null_clusterings [] for i in range(n_samples): G_null nx.configuration_model(degree_sequence, seedi) G_null nx.Graph(G_null) G_null.remove_edges_from(nx.selfloop_edges(G_null)) if len(G_null) 0: null_clusterings.append(nx.average_clustering(G_null)) null_clusterings np.array(null_clusterings) mean_null np.mean(null_clusterings) std_null np.std(null_clusterings) z_score (observed_clustering - mean_null) / std_null p_value np.mean(null_clusterings observed_clustering) print(f零模型聚类系数: {mean_null:.4f} ± {std_null:.4f}) print(f真实网络聚类系数: {observed_clustering:.4f}) print(fZ-score: {z_score:.2f}, p-value: {p_value:.4f}) return z_score, p_value逻辑说明n_samples一般取 100 到 1000比赛时 100 就够。z_score大于 2 或小于 -2 就说明显著。p_value小于 0.05 说明真实网络的聚类系数显著高于随机配置。这个检验做出来你的论文就从“我建了个网络”升级到“我证明了该网络具有非随机结构”。这是美赛评委非常看重的“模型验证”环节。注意配置模型生成的图可能不连通average_clustering对不连通图仍然有效但如果你要算路径长度记得取最大连通子图。5.3 一个我踩过的坑度序列必须图形化配置模型要求度序列是“图形化的”也就是存在至少一个简单图满足该度序列。判断条件是度序列总和为偶数且按降序排列后满足 Erdős–Gallai 定理。实际比赛时你从数据里统计的度序列大概率满足但如果你手动改过某个节点的度可能就不满足了。我一般会先跑nx.is_graphical(degree_sequence)检查不满足就微调。另外配置模型生成平行边的概率在度序列方差大时很高去掉平行边后实际度分布会偏离输入这个偏差要在论文里说明。如果偏差太大改用nx.expected_degree_graph或nx.chung_lu_graph它们直接按期望度生成不要求严格匹配。最后说一个习惯我每次跑完随机图代码都会把参数、种子、指标输出到一个results.txt里和代码一起打包。美赛提交前如果评委问“这个结果怎么来的”你能直接翻出记录。这个习惯帮我省过至少两次“参数到底设了多少”的扯皮。希望帮到你。本文还有配套的精品资源点击获取
美赛随机图代码实战：ER/WS/BA与SIR传播及级联失效
简介这份资源面向参加美国数学建模竞赛MCM/ICM的学生与复杂网络初学者聚焦随机图与网络科学常见算法的代码实现帮助读者在赛题建模中快速搭建网络模型、验证拓扑特性。压缩包内共1个文件为MATLAB脚本.m体积约2KB轻量易读可直接运行或按需修改。内容围绕Erdős-Rényi随机图、Barabási-Albert无标度网络、Watts-Strogatz小世界模型等经典模型展开并可能涉及生成树、社区检测、网络动力学、稳健性分析与可视化等方向便于读者理解节点度分布、平均路径长度、聚类系数等核心指标的计算方式。目前已有149人学习适合作为赛前算法速查与代码参考通过阅读和调试脚本可加深对随机图生成机制与网络结构分析流程的掌握为美赛建模提供可复用的实现思路。1. 美赛里随机图代码到底能帮你拿什么分美赛MCM/ICM的题目里只要出现“网络”“传播”“节点”“连接”“鲁棒性”这类词八成就要用到复杂网络建模。而复杂网络里最常被翻牌的就是 random graph——随机图。很多队伍拿到题的第一反应是“建个网络”但真到写代码时才发现节点怎么连、连多少、连出来的图能不能用、跑出来的指标怎么解释全是坑。标题里这份“复杂网络 random graph 算法程序.zip”本质上就是一套帮你跳过“从零手写图生成”的参考代码集合。它解决的不是“要不要建模”的问题而是“怎么在 72 小时内把图生成、指标计算、结果可视化串成一条能写进论文的链路”。适合谁适合已经确定要用网络模型、但卡在代码实现和参数调不明白的参赛队也适合第一次做网络类赛题、想先跑通最小闭环的新手。这一章不展开代码先把随机图在美赛里的定位说清楚它不是万能的但它是你论证“网络结构如何影响结果”时最稳的起点。2. 随机图三件套ER、WS、BA 到底该选哪个2.1 三种图的数学定义与美赛适用场景随机图不是一种图而是一类图的统称。美赛里最常出现的是三种ER 随机图Erdős–Rényi、WS 小世界图Watts–Strogatz、BA 无标度图Barabási–Albert。ER 图的做法是给定 N 个节点每对节点以概率 p 独立连边。它的度分布近似泊松分布特点是“均匀”没有明显的枢纽节点。WS 小世界图从一个环状规则图出发以概率 β 随机重连边特点是平均路径短、聚类系数高适合模拟“熟人网络”“信息在局部密集但全局可达”的场景。BA 图则是“优先连接”新节点更倾向于连到已经有很多连接的节点上最终形成幂律度分布也就是少数节点拥有大量连接适合模拟“舆情传播”“供应链核心企业”“交通枢纽”这类现实网络。选哪个取决于你的赛题问的是什么。如果题目问“随机攻击下网络的鲁棒性”ER 图是基准BA 图对随机攻击更鲁棒但对蓄意攻击更脆弱这个对比本身就是论文亮点。如果题目问“信息传播效率”WS 图的小世界特性会让传播速度明显快于 ER 图。如果题目问“关键节点识别”BA 图的幂律特性会让“度中心性”和“介数中心性”的差异变得非常有讨论价值。我一般会建议先跑 ER 做基准再跑 BA 做对比如果题目涉及“局部聚集”再加 WS。三张图跑完论文的“模型对比”部分就有了。2.2 用 NetworkX 跑通三种图的最小代码下面这段代码是三种图的最小生成与指标计算模板。你不需要装额外库NetworkX 加 Matplotlib 就够。import networkx as nx import matplotlib.pyplot as plt import numpy as np # 参数设置N 节点数p 连边概率k 近邻数beta 重连概率m 新节点连边数 N 500 p 0.02 k 6 beta 0.1 m 3 # ER 随机图 er nx.erdos_renyi_graph(N, p, seed42) # WS 小世界图 ws nx.watts_strogatz_graph(N, k, beta, seed42) # BA 无标度图 ba nx.barabasi_albert_graph(N, m, seed42) # 计算核心指标 def graph_metrics(G, name): avg_deg np.mean([d for n, d in G.degree()]) avg_clust nx.average_clustering(G) # 平均路径长度只对连通图有效不连通时取最大连通子图 if nx.is_connected(G): avg_path nx.average_shortest_path_length(G) else: largest_cc max(nx.connected_components(G), keylen) avg_path nx.average_shortest_path_length(G.subgraph(largest_cc)) print(f{name}: 平均度{avg_deg:.2f}, 聚类系数{avg_clust:.4f}, 平均路径{avg_path:.2f}) graph_metrics(er, ER) graph_metrics(ws, WS) graph_metrics(ba, BA)逻辑说明erdos_renyi_graph(N, p)里 p 是每对节点独立连边的概率p 越大图越密watts_strogatz_graph(N, k, beta)里 k 是每个节点初始连接的近邻数beta 是重连概率beta0 是规则环beta1 是完全随机barabasi_albert_graph(N, m)里 m 是每个新节点连到已有节点的边数m 越大平均度越高。参数怎么调N 一般取 200 到 2000太小指标波动大太大跑得慢。p 的取值要让平均度在 4 到 10 之间也就是 p ≈ 平均度 / N。k 取偶数一般 4 到 10。beta 取 0.05 到 0.3 之间太小接近规则图太大接近随机图。m 取 2 到 5m1 会生成树状图连通性差。跑完这段你会得到三组指标。ER 的聚类系数接近 pWS 的聚类系数远高于 ER 但路径长度接近BA 的聚类系数低但度分布极不均匀。这三个差异就是你论文里“模型选择依据”的硬证据。2.3 度分布画图让评委一眼看懂你的网络类型指标是数字度分布是图。美赛论文里一张清晰的度分布对比图比三行数字更有说服力。fig, axes plt.subplots(1, 3, figsize(15, 4)) for ax, G, name in zip(axes, [er, ws, ba], [ER, WS, BA]): degrees [d for n, d in G.degree()] ax.hist(degrees, bins30, densityTrue, alpha0.7, colorsteelblue) ax.set_title(f{name} 度分布) ax.set_xlabel(度) ax.set_ylabel(频率) plt.tight_layout() plt.savefig(degree_dist.png, dpi150)这段代码的关键是densityTrue它把频数转成频率方便不同 N 的图对比。ER 的度分布像钟形WS 和 ER 接近但尾部略厚BA 的度分布是明显的长尾——少数节点度很高大部分节点度很低。如果你在论文里要论证“该网络存在关键枢纽”BA 的度分布图就是最直接的视觉证据。注意bins 不要设太小30 到 50 之间比较合适太小看不出分布形状太大图会毛糙。3. 把随机图接上传播模型SIR 与级联失效的代码实现3.1 SIR 模型在随机图上的最小实现美赛网络题里传播模型出现频率极高。SIR易感-感染-恢复是最经典的。在随机图上跑 SIR核心就三步选初始感染节点、按边传播、按概率恢复。def sir_on_graph(G, beta0.3, gamma0.1, initial_infected5, steps100): # 初始化状态S0, I1, R2 status {n: 0 for n in G.nodes()} infected np.random.choice(list(G.nodes()), initial_infected, replaceFalse) for n in infected: status[n] 1 history [] for _ in range(steps): new_infected [] new_recovered [] for n in G.nodes(): if status[n] 1: # 感染邻居 for nb in G.neighbors(n): if status[nb] 0 and np.random.rand() beta: new_infected.append(nb) # 恢复 if np.random.rand() gamma: new_recovered.append(n) for n in new_infected: if status[n] 0: status[n] 1 for n in new_recovered: status[n] 2 # 统计 s sum(1 for n in G.nodes() if status[n] 0) i sum(1 for n in G.nodes() if status[n] 1) r sum(1 for n in G.nodes() if status[n] 2) history.append((s, i, r)) if i 0: break return history逻辑说明beta是感染概率gamma是恢复概率。基本再生数 R0 ≈ beta * 平均度 / gamma。当 R0 1 时感染会扩散R0 1 时感染会自然消亡。这个结论在 ER 图和 BA 图上都成立但 BA 图上因为存在超级传播节点早期扩散速度会明显更快。参数怎么设beta 一般 0.1 到 0.5gamma 一般 0.05 到 0.2。如果你要模拟“快速传播但恢复也快”的场景beta0.4、gamma0.3 比较合适如果要模拟“慢传播长病程”beta0.15、gamma0.05。跑完之后把 history 画成三条曲线就是标准的 SIR 曲线图。3.2 级联失效节点移除顺序决定网络生死级联失效是另一个高频考点。做法是按某种策略移除节点看网络什么时候碎裂。常见策略有三种随机移除、按度从大到小移除、按介数中心性从大到小移除。def cascade_failure(G, strategydegree, removal_ratio0.3): G_copy G.copy() n_remove int(len(G_copy) * removal_ratio) if strategy random: nodes_to_remove np.random.choice(list(G_copy.nodes()), n_remove, replaceFalse) elif strategy degree: nodes_to_remove sorted(G_copy.degree, keylambda x: x[1], reverseTrue)[:n_remove] nodes_to_remove [n for n, d in nodes_to_remove] elif strategy betweenness: bc nx.betweenness_centrality(G_copy) nodes_to_remove sorted(bc, keybc.get, reverseTrue)[:n_remove] G_copy.remove_nodes_from(nodes_to_remove) # 计算最大连通子图占比 if len(G_copy) 0: return 0.0 largest_cc max(nx.connected_components(G_copy), keylen) return len(largest_cc) / len(G)逻辑说明removal_ratio是移除比例一般从 0.05 到 0.5 扫一遍画出一条“移除比例 vs 最大连通子图占比”的曲线。随机移除下ER 图和 BA 图都有一定的鲁棒性但 BA 图在蓄意移除高度节点时崩溃得极快——这就是“无标度网络对随机故障鲁棒、对蓄意攻击脆弱”的经典结论。介数中心性计算量大N500 时还能跑N2000 以上建议改用近似算法或只算前 100 个节点。这个对比实验做出来论文的“网络脆弱性分析”部分就稳了。3.3 把传播和失效结果画成论文级图表美赛论文的图第一要求是“自解释”。也就是说评委不看正文只看图和图注就能明白你在说什么。# SIR 曲线 history sir_on_graph(ba, beta0.3, gamma0.1, initial_infected5, steps80) s [h[0] for h in history] i [h[1] for h in history] r [h[2] for h in history] plt.figure(figsize(8, 5)) plt.plot(s, labelS (易感), linewidth2) plt.plot(i, labelI (感染), linewidth2) plt.plot(r, labelR (恢复), linewidth2) plt.xlabel(时间步) plt.ylabel(节点数) plt.title(BA 网络上的 SIR 传播曲线 (beta0.3, gamma0.1)) plt.legend() plt.grid(alpha0.3) plt.savefig(sir_curve.png, dpi150)图注要写清楚网络类型、节点数、关键参数。比如“图 3BA 网络N500, m3上 SIR 模型传播曲线感染概率 beta0.3恢复概率 gamma0.1初始感染节点 5 个”。这样评委不用翻正文就能看懂。级联失效的图同理横轴是移除比例纵轴是最大连通子图占比三条线分别对应随机、度优先、介数优先。线型用实线、虚线、点划线区分颜色用蓝、橙、绿打印成黑白也能分辨。4. 避坑随机图代码在美赛里最容易翻车的五个地方4.1 图不连通导致平均路径长度报错现象跑nx.average_shortest_path_length(G)时直接抛异常NetworkXError: Graph is not connected。原因ER 图在 p 较小时大概率不连通WS 图在 beta 较大时也可能出现孤立节点。解决先判断nx.is_connected(G)不连通就取最大连通子图再算或者直接报告“最大连通子图占比”这个指标。我一般会在论文里同时给出“全图指标”和“最大连通子图指标”后者更有意义。4.2 随机种子没固定结果每次跑都不一样现象同一段代码跑两次SIR 曲线形状差很多级联失效的崩溃点也漂移。原因np.random和 NetworkX 的默认随机源没有固定。解决在代码开头加np.random.seed(42)并且所有图生成函数都传seed42。美赛论文里可复现性是加分项固定种子是最低成本的“后悔药”。如果要做多次实验取平均那就跑 50 次不同种子报告均值和置信区间这样更严谨。4.3 度分布图用默认 bins 导致长尾看不见现象BA 图的度分布画出来像一坨完全看不出幂律特征。原因plt.hist默认 bins10对于度范围 1 到 100 的数据分辨率太低。解决bins 设为 30 到 50并且用densityTrue归一化。如果要做幂律拟合用scipy.stats.powerlaw或手动做 log-log 图看是否近似直线。注意log-log 图里BA 图的尾部应该是一条下降的直线ER 图则是一个快速下坠的曲线。4.4 介数中心性计算太慢比赛时卡死现象N2000 的图跑nx.betweenness_centrality超过 10 分钟。原因精确介数中心性复杂度是 O(N*M)N2000、M6000 时运算量巨大。解决用nx.betweenness_centrality(G, k100)做近似k 是采样节点数一般 50 到 200 就够。或者只对度最高的前 100 个节点算介数其他节点忽略。比赛时时间比精度重要近似结果在论文里注明“采用 k100 近似”即可。4.5 把 ER 图当成“真实网络”直接下结论现象论文里写“该网络度分布近似泊松说明是随机网络”但题目给的数据明显有枢纽节点。原因ER 图是基准模型不是现实网络的拟合模型。解决先算真实数据的度分布看是泊松还是幂律再决定用 ER 还是 BA 做对比。如果真实数据有长尾就用 BA 拟合ER 只作为“如果网络是随机的会怎样”的对照组。这个逻辑在论文里写清楚评委不会扣分反而觉得你严谨。5. 进阶用配置模型生成“指定度分布”的随机图5.1 配置模型从度序列反推图结构前面讲的 ER、WS、BA 都是“生成机制决定度分布”。但美赛里更常见的情况是题目给了你一个真实的度序列或者你从数据里统计出了度分布然后你想生成一个“具有相同度分布但其他方面随机”的图。这就是配置模型Configuration Model。# 假设我们有一个度序列 degree_sequence [3, 3, 2, 2, 2, 1, 1, 1, 1, 1] # 确保度序列是图形化的总和为偶数 if sum(degree_sequence) % 2 ! 0: degree_sequence[0] 1 # 生成配置模型图 G_config nx.configuration_model(degree_sequence, seed42) # 去掉自环和平行边 G_config nx.Graph(G_config) G_config.remove_edges_from(nx.selfloop_edges(G_config)) print(f节点数: {G_config.number_of_nodes()}, 边数: {G_config.number_of_edges()}) print(f平均度: {np.mean([d for n, d in G_config.degree()]):.2f})逻辑说明configuration_model的做法是把每个节点的“度”想象成“半条边”然后随机配对。这样生成的图度分布严格等于输入的度序列但其他性质聚类系数、路径长度是随机的。注意生成的图可能有自环和平行边必须用nx.Graph转成简单图并去掉自环。这个模型在美赛里的典型用法是从真实数据统计度序列生成配置模型作为“零模型”然后对比真实网络和零模型的聚类系数、路径长度如果真实网络的聚类系数显著高于零模型说明网络存在“局部聚集”机制不是纯随机的。5.2 用零模型做假设检验你的网络真的“特殊”吗配置模型最值钱的地方是它可以当零模型用。比如你算出真实网络的聚类系数是 0.35但你不确定这个值算高还是低。那就生成 100 个配置模型图算它们的聚类系数分布看 0.35 落在哪个分位数。def null_model_test(degree_sequence, observed_clustering, n_samples100): null_clusterings [] for i in range(n_samples): G_null nx.configuration_model(degree_sequence, seedi) G_null nx.Graph(G_null) G_null.remove_edges_from(nx.selfloop_edges(G_null)) if len(G_null) 0: null_clusterings.append(nx.average_clustering(G_null)) null_clusterings np.array(null_clusterings) mean_null np.mean(null_clusterings) std_null np.std(null_clusterings) z_score (observed_clustering - mean_null) / std_null p_value np.mean(null_clusterings observed_clustering) print(f零模型聚类系数: {mean_null:.4f} ± {std_null:.4f}) print(f真实网络聚类系数: {observed_clustering:.4f}) print(fZ-score: {z_score:.2f}, p-value: {p_value:.4f}) return z_score, p_value逻辑说明n_samples一般取 100 到 1000比赛时 100 就够。z_score大于 2 或小于 -2 就说明显著。p_value小于 0.05 说明真实网络的聚类系数显著高于随机配置。这个检验做出来你的论文就从“我建了个网络”升级到“我证明了该网络具有非随机结构”。这是美赛评委非常看重的“模型验证”环节。注意配置模型生成的图可能不连通average_clustering对不连通图仍然有效但如果你要算路径长度记得取最大连通子图。5.3 一个我踩过的坑度序列必须图形化配置模型要求度序列是“图形化的”也就是存在至少一个简单图满足该度序列。判断条件是度序列总和为偶数且按降序排列后满足 Erdős–Gallai 定理。实际比赛时你从数据里统计的度序列大概率满足但如果你手动改过某个节点的度可能就不满足了。我一般会先跑nx.is_graphical(degree_sequence)检查不满足就微调。另外配置模型生成平行边的概率在度序列方差大时很高去掉平行边后实际度分布会偏离输入这个偏差要在论文里说明。如果偏差太大改用nx.expected_degree_graph或nx.chung_lu_graph它们直接按期望度生成不要求严格匹配。最后说一个习惯我每次跑完随机图代码都会把参数、种子、指标输出到一个results.txt里和代码一起打包。美赛提交前如果评委问“这个结果怎么来的”你能直接翻出记录。这个习惯帮我省过至少两次“参数到底设了多少”的扯皮。希望帮到你。本文还有配套的精品资源点击获取
