简介本资源是面向美国数学建模竞赛MCM/ICM参赛者的复杂网络核心算法参考代码包聚焦Random Graph建模与分析适用于需快速实现网络结构生成、社区识别及动力学模拟的中高级建模选手。压缩包仅含1个MATLAB源文件randomgraph.m体积精简至2KB代码覆盖ER随机图、BA无标度网络、WS小世界模型三大经典生成机制并隐含生成树与社区检测逻辑便于直接调用、参数调试与结果可视化。已有149人下载学习适合作为赛题中网络建模模块的快速启动脚本、算法原理验证工具及代码结构参考范例——尤其利于在有限时间内理解模型差异、比对拓扑指标如平均路径长度、聚类系数并嵌入完整建模流程。1. 美赛中真正能跑通、可调试、带验证的复杂网络随机图生成代码不是模板套壳而是工程级复用美赛MCM/ICM里一提到“复杂网络建模”很多队伍立刻翻出 Barabási-Albert 或 Erdős–Rényi 的 Python 示例——但真正交卷前夜跑不通、参数调不准、结果无法复现、图结构无法可视化验证才是高频痛点。这个标题里的.zip文件本质不是“参考代码”而是可嵌入解题流程的模块化工具集它把 random graph 生成、拓扑指标计算、邻接矩阵导出、基础可视化封装成独立函数不依赖 Jupyter Notebook 环境不硬编码节点数或边概率所有参数通过config.py或命令行传入。适合数学建模中需要快速验证“网络鲁棒性随连接密度变化趋势”“关键节点识别对随机失效的敏感度”等子问题的队伍。如果你正在写 Problem C 的 Network Resilience 部分或需要为图论模型提供真实拓扑输入这套代码不是锦上添花而是避免在 deadline 前两小时还在 debugnx.gnp_random_graph(100, 0.02)返回空图的救命方案。2. 用 NetworkX NumPy 实现四种主流随机图模型支持参数化生成与结构校验复杂网络建模在美赛中绝非仅调用一个nx.erdos_renyi_graph()就能过关。评审关注的是你是否理解不同模型的生成机制是否验证了理论期望值与实际样本的偏差是否控制了连通性、度分布、聚类系数等关键属性本节给出可直接运行、带断言校验、支持批量生成的最小可行实现覆盖美赛最常考的四类模型。2.1 ER 模型G(n,p)严格按边概率生成附连通性与度分布验证Erdős–Rényi 模型是复杂网络的起点但直接使用networkx.generators.random_graphs.erdos_renyi_graph存在隐式假设默认seedNone导致每次结果不可复现未校验实际边数是否接近理论期望p * n*(n-1)/2未检查是否生成孤立节点影响后续中心性计算。以下代码补全这些缺口import networkx as nx import numpy as np from typing import Tuple, Dict, Any def generate_er_graph(n: int, p: float, seed: int 42) - nx.Graph: 生成 G(n,p) 随机图强制设置 seed 并返回带元数据的图对象 :param n: 节点数 :param p: 每条边存在的概率 :param seed: 随机种子确保结果可复现 :return: NetworkX Graph 对象含 n, p, actual_edges 属性 G nx.erdos_renyi_graph(nn, pp, seedseed, directedFalse) # 记录关键元数据 G.graph[n] n G.graph[p] p G.graph[actual_edges] G.number_of_edges() G.graph[expected_edges] round(p * n * (n - 1) / 2, 2) # 断言实际边数应在期望值 ±10% 范围内大 n 下成立 expected p * n * (n - 1) / 2 if not (0.9 * expected G.number_of_edges() 1.1 * expected): raise ValueError(fER 图边数异常期望 {expected:.1f}实际 {G.number_of_edges()}偏离超阈值) return G # 使用示例生成 200 节点、边概率 0.015 的图 G_er generate_er_graph(n200, p0.015, seed123) print(fER 图{G_er.graph[n]} 节点理论边数 {G_er.graph[expected_edges]}实际 {G_er.graph[actual_edges]})提示美赛中若需对比不同p下的网络特性必须固定seed。否则同一p多次运行结果差异过大无法支撑“随p增加平均路径长度单调下降”的结论。此处seed123是示例实际应统一设为队伍编号或题目编号衍生值如seedint(2024C001)保证报告中所有图可复现。2.2 BA 模型实现带优先连接的无标度网络控制初始核大小与增长步长Barabási–Albert 模型模拟真实网络的“富者愈富”现象但nx.barabasi_albert_graph默认m1每次添加 1 条边易导致度分布过陡峭且不暴露内部连接逻辑。美赛要求展示“如何通过调整m控制度分布斜率”因此我们重写核心逻辑def generate_ba_graph(n: int, m: int, seed: int 42) - nx.Graph: 手动实现 BA 模型显式控制初始核与连接规则 :param n: 最终节点数 :param m: 每个新节点连接的已有节点数 :param seed: 随机种子 :return: BA 无标度网络 rng np.random.default_rng(seed) # 初始化m1 个节点的完全图最小连通核 G nx.complete_graph(m 1) G.graph[n_initial] m 1 G.graph[m] m # 逐个添加新节点 for new_node in range(m 1, n): # 计算每个现有节点的度作为连接概率权重 degrees [d for _, d in G.degree()] nodes list(G.nodes()) # 按度比例采样 m 个目标节点允许重复即允许多连同一节点 targets rng.choice(nodes, sizem, pnp.array(degrees) / sum(degrees), replaceTrue) # 添加边 for target in targets: G.add_edge(new_node, target) G.graph[final_n] n G.graph[actual_m] m return G # 生成 500 节点、m3 的 BA 网络 G_ba generate_ba_graph(n500, m3, seed456) print(fBA 图初始核 {G_ba.graph[n_initial]} 节点m{G_ba.graph[m]}最终 {G_ba.graph[final_n]} 节点)2.1.1 BA 模型的三个必调参数及其美赛意义参数取值范围美赛中典型用途调参建议m每次新增边数≥1 整数控制度分布幂律指数 γm1时 γ≈3m3时 γ≈2.5若题目要求“模拟社交网络强连接”选m≥2若模拟互联网路由m1更合理n总节点数≥100影响统计显著性n100时度分布波动大难以拟合幂律美赛推荐n300~1000兼顾计算效率与分布稳定性seed任意整数保证多组实验如不同m间可比性统一设为int(problem_id team_id)如2024C0012.3 WS 小世界模型精确控制重连概率避免nx.watts_strogatz_graph的环形陷阱Watts-Strogatz 模型用于生成高聚类、短路径的网络但nx.watts_strogatz_graph默认k2每个节点连左右各 1 个邻居且重连后可能产生自环或多重边。美赛中若需分析“重连概率β对平均路径长度L和聚类系数C的影响”必须确保重连过程严格符合原始论文定义def generate_ws_graph(n: int, k: int, beta: float, seed: int 42) - nx.Graph: 严格实现 Watts-Strogatz 模型先构建环状 k-近邻图再以概率 beta 重连每条边 :param n: 节点数 :param k: 每个节点的初始邻居数必须为偶数 :param beta: 每条边被重连的概率 :param seed: 随机种子 :return: WS 小世界网络 if k % 2 ! 0: raise ValueError(k 必须为偶数以保证环状对称连接) rng np.random.default_rng(seed) G nx.empty_graph(n) # 步骤1构建环状 k-近邻图每个节点 i 连接 i±1, i±2, ..., i±k//2 mod n for i in range(n): for j in range(1, k // 2 1): neighbor (i j) % n G.add_edge(i, neighbor) neighbor (i - j) % n G.add_edge(i, neighbor) # 步骤2遍历每条边以概率 beta 重连 edges list(G.edges()) for u, v in edges: if rng.random() beta: # 移除原边 G.remove_edge(u, v) # 随机选择新目标节点不能是自身、不能已存在边、不能是原邻居 candidates [w for w in range(n) if w ! u and not G.has_edge(u, w) and w ! v] if candidates: new_v rng.choice(candidates) G.add_edge(u, new_v) G.graph[n] n G.graph[k] k G.graph[beta] beta return G # 生成 400 节点、k4、重连概率 0.3 的 WS 网络 G_ws generate_ws_graph(n400, k4, beta0.3, seed789) print(fWS 图{G_ws.graph[n]} 节点k{G_ws.graph[k]}β{G_ws.graph[beta]})注意nx.watts_strogatz_graph在beta0时生成的是k-正则图但其内部实现可能导致某些节点度略低于k。本实现手动构建环状结构确保beta0时每个节点度严格为k满足美赛中“验证小世界阈值”的精度要求。3. 从图结构到可提交数据邻接矩阵导出、拓扑指标批量计算与 LaTeX 表格生成美赛论文中网络模型的价值最终要落于量化指标。单纯画一张图不够必须提供L,C,γ等数值并嵌入正文表格。本节提供端到端流水线将生成的图对象自动计算 6 项核心指标导出为 CSV 供 Excel 分析并生成 LaTeX 表格代码直接粘贴进论文。3.1 六大拓扑指标的计算逻辑与美赛解释力指标计算方式美赛中解释意义是否需归一化平均路径长度Lnx.average_shortest_path_length(G)网络信息传递效率越小说明传播越快否但需注明inf处理聚类系数Cnx.average_clustering(G)局部聚集程度高C表示社区结构明显否度分布幂律指数γ对度序列k取log(k)与log(P(k))线性拟合斜率判定是否无标度2γ3为典型无标度是需剔除k0节点介数中心性均值np.mean(list(nx.betweenness_centrality(G).values()))关键节点影响力均值高说明网络脆弱否连通分量数量nx.number_weakly_connected_components(G.to_undirected())网络鲁棒性1表示存在孤岛否最大连通分量占比max(len(c) for c in nx.connected_components(G)) / G.number_of_nodes()主干网络规模低于 0.8 需预警是3.2 批量计算并导出为 LaTeX 表格的完整脚本import pandas as pd from tabulate import tabulate def compute_network_metrics(G: nx.Graph, model_name: str) - Dict[str, float]: 计算单图六大指标返回字典 metrics {Model: model_name} # 1. 平均路径长度处理不连通图 try: metrics[L] round(nx.average_shortest_path_length(G), 3) except nx.NetworkXError: # 不连通时计算最大连通分量内的 L largest_cc max(nx.connected_components(G), keylen) G_lcc G.subgraph(largest_cc).copy() metrics[L] round(nx.average_shortest_path_length(G_lcc), 3) if len(G_lcc.nodes()) 1 else float(inf) # 2. 聚类系数 metrics[C] round(nx.average_clustering(G), 3) # 3. 度分布幂律指数 γ仅对 BA 等无标度图有意义 degrees [d for _, d in G.degree()] if len(set(degrees)) 10: # 度值足够分散才拟合 from scipy import stats k_counts pd.Series(degrees).value_counts().sort_index() k_vals k_counts.index[k_counts 0].values p_vals k_counts[k_vals].values / len(degrees) # 取 log-log 后线性拟合 log_k np.log10(k_vals) log_p np.log10(p_vals) slope, _ stats.linregress(log_k, log_p) metrics[γ] round(-slope, 3) else: metrics[γ] float(nan) # 4. 介数中心性均值 bc nx.betweenness_centrality(G) metrics[BC_mean] round(np.mean(list(bc.values())), 4) # 5. 连通分量数量 metrics[Components] nx.number_connected_components(G) # 6. 最大连通分量占比 largest_cc_size max(len(c) for c in nx.connected_components(G)) metrics[LCC_ratio] round(largest_cc_size / G.number_of_nodes(), 3) return metrics def generate_latex_table(metrics_list: list) - str: 将指标列表转为 LaTeX 表格代码 df pd.DataFrame(metrics_list) # 重命名列名适配 LaTeX df.columns [模型, 平均路径长度 $L$, 聚类系数 $C$, 幂律指数 $\\gamma$, 介数中心性均值, 连通分量数, 最大连通分量占比] # 生成 LaTeX 表格tabulate 格式 latex_table tabulate(df, tablefmtlatex_raw, headerskeys, floatfmt.3f) return latex_table.replace(nan, --) # NaN 显示为 -- # 示例对三种模型计算指标 metrics_data [] for name, G in [(ER, G_er), (BA, G_ba), (WS, G_ws)]: metrics_data.append(compute_network_metrics(G, name)) latex_code generate_latex_table(metrics_data) print(LaTeX 表格代码复制粘贴至 .tex 文件) print(latex_code)3.2.1 输出示例LaTeX 片段\begin{tabular}{lrrrrrr} \hline 模型 平均路径长度 $L$ 聚类系数 $C$ 幂律指数 $\gamma$ 介数中心性均值 连通分量数 最大连通分量占比 \\ \hline ER 3.214 0.015 -- 0.0021 1 1.000 \\ BA 2.876 0.023 2.451 0.0087 1 1.000 \\ WS 2.103 0.482 -- 0.0034 1 1.000 \\ \hline \end{tabular}提示美赛论文中此表格应放在“模型构建与验证”章节紧接在图生成代码之后。务必在表格下方加注“所有网络均生成于相同节点数n400参数经预实验校准以确保可比性γ仅对 BA 模型报告因 ER 与 WS 不具无标度特性”。4. 美赛现场调试技巧三步定位 random graph 生成失败原因当美赛限时 96 小时凌晨三点发现generate_ba_graph(n1000, m5)报错NetworkXError: Graph not connected或G.number_of_edges()返回 0不要重写代码——用以下三步快速定位4.1 第一步检查输入参数合法性5 秒解决 70% 问题def validate_params(n: int, m: int, p: float None, beta: float None) - bool: 参数合法性检查美赛现场直接粘贴运行 errors [] if n 2: errors.append(n 必须 ≥2) if m 1 or not isinstance(m, int): errors.append(m 必须为 ≥1 的整数) if p is not None and (p 0 or p 1): errors.append(p 必须在 [0,1] 区间) if beta is not None and (beta 0 or beta 1): errors.append(beta 必须在 [0,1] 区间) if errors: print(参数错误, ; .join(errors)) return False return True # 现场调试时第一行就加 assert validate_params(n1000, m5), 参数非法4.2 第二步用nx.info(G)和G.nodes()快速诊断图状态# 生成图后立即执行 print(nx.info(G_ba)) # 输出Name: , Type: Graph, Number of nodes: 1000, Number of edges: 2985... print(前10个节点度, [d for _, d in list(G_ba.degree())[:10]]) print(是否存在孤立节点, any(d 0 for _, d in G_ba.degree()))关键线索若Number of edges: 0说明m设置过大导致rng.choice无候选节点如n10, m10若Number of nodes小于预期说明nx.add_edge时节点 ID 超出范围常见于手写循环索引错误。4.3 第三步启用详细日志捕获重连/连接失败瞬间修改generate_ws_graph中的重连部分加入失败计数# 在重连循环中添加 failed_reconnects 0 for u, v in edges: if rng.random() beta: G.remove_edge(u, v) candidates [w for w in range(n) if w ! u and not G.has_edge(u, w) and w ! v] if not candidates: failed_reconnects 1 G.add_edge(u, v) # 恢复原边 else: new_v rng.choice(candidates) G.add_edge(u, new_v) if failed_reconnects 0: print(f警告{failed_reconnects} 条边重连失败已恢复原连接)4.3.1 常见报错与对应修复表报错信息根本原因修复动作ValueError: probabilities contain NaNdegrees全为 0图为空检查n和m是否合理BA 模型n必须 m1NetworkXError: Graph not connectednx.average_shortest_path_length输入不连通图改用largest_cc子图计算或增加pER、减小betaWSIndexError: list index out of range手动循环中range(n)与节点 ID 不匹配统一用list(G.nodes())获取节点列表而非range(n)ZeroDivisionError: float division by zero计算C时图无边在nx.average_clustering前加if G.number_of_edges() 0: metrics[C] 0.05. 美赛加分项将 random graph 生成器封装为命令行工具支持批量实验与参数扫描美赛高分论文常包含“参数敏感性分析”图表例如绘制L随p变化的曲线。手动改 20 次p值再运行太低效。本节将前述代码封装为 CLI 工具一行命令完成 100 组实验输出 CSV 供 Matplotlib 绘图。5.1 创建graph_generator.py支持模型选择、参数范围、输出目录#!/usr/bin/env python3 # graph_generator.py —— 美赛专用随机图批量生成器 import argparse import os import json from pathlib import Path def main(): parser argparse.ArgumentParser(description美赛复杂网络随机图批量生成器) parser.add_argument(--model, choices[er, ba, ws], requiredTrue, help模型类型) parser.add_argument(--n, typeint, default500, help节点数) parser.add_argument(--param_min, typefloat, default0.005, help参数最小值p 或 beta) parser.add_argument(--param_max, typefloat, default0.05, help参数最大值) parser.add_argument(--steps, typeint, default10, help参数步数) parser.add_argument(--output_dir, typestr, defaultoutput, help输出目录) args parser.parse_args() # 创建输出目录 Path(args.output_dir).mkdir(exist_okTrue) # 生成参数序列 if args.model er: params np.linspace(args.param_min, args.param_max, args.steps) param_name p elif args.model ws: params np.linspace(args.param_min, args.param_max, args.steps) param_name beta else: # ba params range(int(args.param_min), int(args.param_max)1) param_name m # 批量生成并保存 results [] for i, param_val in enumerate(params): seed 1000 i # 每组实验不同 seed if args.model er: G generate_er_graph(args.n, param_val, seedseed) elif args.model ba: G generate_ba_graph(args.n, int(param_val), seedseed) else: # ws G generate_ws_graph(args.n, k4, betaparam_val, seedseed) metrics compute_network_metrics(G, f{args.model}_{param_val}) metrics[param_name] param_val results.append(metrics) # 保存邻接矩阵为 CSV供后续 MATLAB/Python 读取 adj_matrix nx.to_numpy_array(G) np.savetxt(f{args.output_dir}/{args.model}_{param_name}_{param_val:.3f}.csv, adj_matrix, delimiter,, fmt%d) # 保存指标汇总 CSV pd.DataFrame(results).to_csv(f{args.output_dir}/{args.model}_metrics.csv, indexFalse) print(f✅ 已生成 {len(results)} 组实验结果保存至 {args.output_dir}/) if __name__ __main__: main()5.2 美赛现场一键执行参数扫描# 生成 ER 模型在 p0.005~0.05 间的 10 组数据 python graph_generator.py --model er --n 300 --param_min 0.005 --param_max 0.05 --steps 10 --output_dir er_sweep # 生成 BA 模型在 m2~6 间的 5 组数据 python graph_generator.py --model ba --n 500 --param_min 2 --param_max 6 --steps 5 --output_dir ba_sweep5.2.1 输出文件结构说明er_sweep/ ├── er_p_0.005.csv ← 邻接矩阵300×300 整数矩阵 ├── er_p_0.015.csv ├── ... ├── er_metrics.csv ← 包含 p,L,C,γ 等列的汇总表 └── README.md ← 自动生成的参数说明可手动补充美赛引用实战技巧美赛最后 24 小时用此工具生成p从 0.001 到 0.1 的 20 组 ER 数据用pandas.read_csv(er_metrics.csv)读取后一行代码绘图df pd.read_csv(er_sweep/er_metrics.csv) plt.plot(df[p], df[L], o-, labelL(p)) plt.xlabel(边概率 p); plt.ylabel(平均路径长度 L); plt.legend() plt.savefig(L_vs_p.png, dpi300)此图可直接插入论文“模型敏感性分析”小节证明你的结论具有鲁棒性。本文还有配套的精品资源点击获取