简介：面向美赛建模参赛者与复杂网络研究初学者，这份压缩包提供了一套Random Graph（随机图）算法的MATLAB实现。核心程序文件覆盖ER随机图、BA无标度网络、WS小世界模型等经典模型的生成与基础指标计算，可直接运行并用于模拟社交网络、生物网络等场景，帮助理解网络相变、度分布及聚类系数等概念。程序采用函数化设计，输入节点数与连边概率等参数即可输出网络邻接矩阵，便于嵌入数学建模流程或作为二次开发基础。包内共1个文件，为.m源码文件，整体仅2KB，轻量易用，适合快速调用。目前已有150人学习下载，说明其在竞赛备赛群体中具备一定参考价值。通过学习该程序，读者能掌握随机图模型的编程实现思路，并在此基础上扩展社区检测、网络鲁棒性分析等进阶功能，为美赛中的网络建模题提供可直接套用的代码基础。
1. 美赛复杂网络题里的第一步，为什么是 random graph
每次美赛或者其他数学建模比赛一碰到网络类题目，很多队伍第一反应就是找真实数据集，或者手搓一个复杂拓扑，然后把社区发现、传播模型往上堆。结果模型越堆越复杂，到了写论文解释“为什么是这个结果”的时候，才发现没有参照物——你根本说不清网络里出现的那些指标到底是数据本身有规律，还是随机波动恰好长这样。random graph 的价值就在这里：它用最朴素的概率规则生成一张“没有内在规律”的对照网络。把真实网络和随机图放在一起比，差异立刻量化出来。这篇文章以美赛常见的参考代码为背景，讲清楚 complex network 与 random graph 算法的原理、NetworkX 实现的每一步以及最容易翻车的坑，适合想在有限赛时内制造可靠对照基准的参赛者。
2. 先看懂三件事：随机图模型选择、网络度量与对照基准
2.1 G(n,p) 与 G(n,m)：两种模型生成逻辑与适用场景
在写代码之前，先搞清楚标题里“random graph 算法”到底指什么。它并不是一个单独算法，而是一族模型，最基础也最常被引用的是 Erdős–Rényi 模型的两种形式：G(n,p) 与 G(n,m)。
G(n,p) 的规则是：给定 n 个节点，每对节点以独立概率 p 连边。生成过程看起来简单，但它隐含了一个重要性质——边的数量不是固定的，而是一个随机变量，期望值是 p * n*(n-1)/2。G(n,m) 则相反：固定总边数为 m，再从所有可能的边里等概率地抽出 m 条，边数恒定，但边之间的相关性天然存在。
美赛实战里两种都要会。假设你要讨论传播动力学阈值，通常用 G(n,p)，因为你可以从概率层面推导临界值。假设你的题目给定了网络边数约束，例如通信链路预算固定，此时 G(n,m) 更贴合题目条件。另一个常见做法是：先用 G(n,p) 生成多张随机图作为蒙特卡洛样本，再用 G(n,m) 生成一张固定规模的对照网络，两者互为补充。
用 NetworkX 生成这两类网络只需要两行代码：
import networkx as nx n = 100 # 节点数量 p = 0.05 # 边存在概率 m = 250 # 固定边数 G_p = nx.gnp_random_graph(n, p, seed=42) G_m = nx.gnm_random_graph(n, m, seed=42) print("G(n,p) 边数:", G_p.number_of_edges()) print("G(n,m) 边数:", G_m.number_of_edges())逻辑说明：nx.gnp_random_graph与nx.gnm_random_graph都封装好了高效生成算法，内部不会真的逐对抛硬币，而是按解析方法先采样边数再均匀生成，所以性能比手动双层循环好很多。seed参数很重要，它控制随机数生成器的初始状态，固定同一个seed，同一台机器上每次运行结果完全一致，这是后续实验可复现的前提。
参数说明：p一般设为 0.01 到 0.1 之间，太大图会稠密到失去分析意义，太小则可能出现大量孤立点。m的选择要参照真实网络尺度，比如题目中提到“节点间通信链路共 250 条”，那m=250就是直接映射题目约束。seed我习惯设成一个固定整数，比如年份或题号数字，便于赛后复盘。
2.2 度分布、平均最短路径与聚类系数：网络结构的三个特征值
生成一张随机图只是开始，真正影响建模结论的是从图中提取的统计指标。美赛常见参考代码里，几乎每个网络分析脚本都要计算三个量：度分布、平均最短路径长度、聚类系数。
度分布描述的是“随机抽一个节点，它的邻居数等于 k 的概率”。G(n,p) 的度分布近似二项分布，当 n 足够大时趋向泊松分布，集中在均值 n*p 附近，不会出现特别多的大度节点。这是随机图与真实复杂网络最显著差异之一——现实社交网络往往存在幂律度分布，少数节点拥有极大量连接。
平均最短路径长度衡量信息从任意一个节点传到任意另一个节点需要跳几步。ER 随机图的最短路径通常很短，呈现“六度分隔”效应，因为随机连边让网络拓扑相当紧密。聚类系数则刻画“你的朋友之间是否也是朋友”的程度，用节点邻居之间实际存在的边数除以最多可能边数来算。ER 随机图的聚类系数约等于 p，数值很小；而真实社交网络聚类系数通常很高。
这三个指标在论文里最常以对照表形式出现：真实网络一行数字，随机图一行数字，差值就是建模要解释的对象。比如真实网络聚类系数 0.62、随机图 0.04，你才有底气说社交网络存在明显社区结构；如果没有随机图作对照，你根本无法判断 0.62 是高还是低。
2.3 为什么 random graph 能当“零模型”：复杂网络研究的基准逻辑
在复杂网络研究里，random graph 最重要的角色不是作为最终模型，而是作为“零模型”。所谓零模型，就是一张没有结构规律的参照网络。研究者想证明某个网络存在非随机结构，就要先构造一张与真实网络同等规模、同等边数的随机图，然后对比两者的统计指标差异。
美赛题目里常见的一类问法是：给一个现实网络的边表，要求分析其拓扑特征并建模。很多参赛选手拿到数据就开始跑社区发现算法，然后输出一堆社区编号。这一步其实有逻辑漏洞——社区发现算法在纯随机图上也能输出社区，因为随机波动天然存在。正确做法是先建随机图对照组，计算模块度等指标，再与真实网络对比，差异显著才说明真实网络有可挖掘的结构。
我一般会建议参赛者把 random graph 生成代码封装成一个函数，输入节点数与目标边数，输出随机图对象以及它的三个基础指标。这样在论文里写“我们以同等规模随机图作为零模型进行对照”时，计算过程可以完整复现，评委也能直观看到对照数值。这也是这篇文章标题指向的参考代码包里最核心的复用单元。
3. 用 NetworkX 实现 random graph 算法：核心代码与参数拆解
3.1 最小可运行代码：生成 G(n,p) 并输出节点与边信息
搭建环境只需要pip install networkx，它不依赖额外的复杂数值库，但建议装 numpy 和 pandas，后面存数据、做矩阵运算会用到。先从一个最简脚本开始，它能生成随机图并打印基础信息。
import networkx as nx n = 100 p = 0.1 seed = 2025 G = nx.gnp_random_graph(n, p, seed=seed) print("节点数:", G.number_of_nodes()) print("边数:", G.number_of_edges()) print("平均度:", 2 * G.number_of_edges() / G.number_of_nodes())逻辑说明：nx.gnp_random_graph返回一个无向图对象，节点编号默认从 0 到 n-1。number_of_edges()实际输出是随机变量，不同 p 值对应的边数波动范围很大。平均度手动计算，公式是边数乘以 2 再除以节点数，因为每条边贡献了两个度。
参数说明：本例 p=0.1 时，期望边数约为 10099/20.1 = 495，平均度约 9.9，网络既不稀疏也不过于稠密。如果 p 小于 0.01，网络会出现大量孤立点；如果 p 大于 0.5，网络几乎完全连通，随机性的差异会被稠密边淹没。具体题目中 p 的选择可参照真实网络的平均度反向估算，公式是 p = 平均度 / (n-1)。
3.2 生成 G(n,m) 并导出边表与邻接矩阵
G(n,m) 在题目给出明确链路数限制时非常有用，因为边数固定，不会出现抽样波动。生成后通常需要导出两种格式：边表 CSV 与邻接矩阵，前者用于外部工具分析，后者用于论文中的矩阵可视化。
import networkx as nx import pandas as pd import numpy as np n = 200 m = 400 seed = 7 G = nx.gnm_random_graph(n, m, seed=seed) edges = list(G.edges()) df_edges = pd.DataFrame(edges, columns=["source", "target"]) df_edges.to_csv("random_graph_edges.csv", index=False) node_list = sorted(G.nodes()) adj_matrix = nx.to_numpy_array(G, nodelist=node_list) np.save("random_graph_adj.npy", adj_matrix)逻辑说明：nx.gnm_random_graph生成边数为 m 的随机图，生成算法保证了 m 条边一定均匀随机分布。边表每行代表一条无向边，存储为 CSV 后可以直接被 Gephi 或 R 语言读取。to_numpy_array输出 n 阶方阵，矩阵第 i 行第 j 列是 1 表示节点 i 与 j 之间有边，对角线为 0。nodelist参数强制指定节点排列顺序，否则矩阵行列顺序可能与节点编号不一致，后续算指标时容易错位。
参数说明：m 要小于等于 n*(n-1)/2，也就是 200 个节点最多 19900 条边，m=400 属于稀疏网络，平均度只有 4。邻接矩阵适合 n 小于几千的规模；当 n 达到 1 万以上，dense 矩阵占用内存约 1e8 个浮点数，接近 800MB，那时候必须改用稀疏矩阵格式。
3.3 计算核心指标：度分布、平均最短路径长度与聚类系数
指标计算脚本是美赛论文里直接产生数据表格的部分，我建议把计算逻辑固定成下面这种结构，避免赛场上临时拼凑。
import networkx as nx from collections import Counter n = 200 p = 0.03 seed = 12 G = nx.gnp_random_graph(n, p, seed=seed) # 度分布统计 degree_seq = [d for _, d in G.degree()] degree_count = Counter(degree_seq) # 聚类系数 avg_clustering = 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), key=len) subG = G.subgraph(largest_cc).copy() avg_path = nx.average_shortest_path_length(subG) print("警告: 原图不连通，已使用最大连通子图") print("平均聚类系数:", avg_clustering) print("平均最短路径长度:", avg_path) print("度分布:", sorted(degree_count.items())[:10])逻辑说明：G.degree()返回每个节点的度，Counter统计每个度值出现的频次，用于画出度分布直方图或验证泊松分布形状。nx.average_clustering计算全局平均聚类系数，内部按每个节点的局部聚类系数求平均。最关键的是平均最短路径分支：只有连通图所有节点对之间才有路径，若图不连通直接调用会报NetworkXError或返回无穷大，所以先用nx.is_connected判断，若不连通则取最大连通子图再计算。
参数说明：p=0.03 时 200 个节点期望度仅为 6，图大概率连通但不算密集。如果发现频繁触发不连通分支，可以调整 p 到 0.05 再试。nx.average_shortest_path_length对大规模图计算较慢，n 超过 5000 时建议改用随机抽样节点对来估算，否则比赛时间会耗在等待上。
4. random graph 算法实践的四个常见坑：现象、原因与解决方案
4.1 坑一：每次运行边数和指标都不一样，实验结果无法复现
现象：同样一段代码，上午跑出来的边数是 489，下午是 502，队友再跑一次又变成 497，整个论文里的数字对不上。
原因：随机图算法本质依赖随机数生成器，不同时间启动的进程会拿不同的随机种子，导致每张图不同。这是 random graph 的特性，但如果做参数实验时不固定种子，实验结论等于每次换了一套数据基础，前后没有可比性。
解决：给生成函数最核心的参数seed一个固定值，并让它在实验脚本里明确可见。比赛中我会把赛题编号或队员学号后四位作为种子，例如题号是 A 题，种子定成 1；B 题定成 2，复盘时能对应上具体思路。在此基础上如果还要做多次随机采样，可以对不同种子循环，得到一组结果再做平均。
import networkx as nx def build_random_graph(n, p, seed=42): return nx.gnp_random_graph(n, p, seed=seed)逻辑说明：把种子收敛到函数参数层，而不是写在模块顶层，这样不同题目、不同试验组之间调用同一个函数也不会相互干扰。
4.2 坑二：平均最短路径长度报错或返回 inf，图根本不连通
现象：脚本运行到nx.average_shortest_path_length(G)直接抛异常，错误信息提示Graph not connected。换用nx.shortest_path_length后算出来的距离出现 inf。
原因：sparse ER 随机图非常容易不连通。当平均度低于连接阈值（通常为 ln(n)）时，图几乎必然包含孤立点或多个连通分量，而平均最短路径的定义要求所有节点对之间都存在路径。
解决：不要把目标锁定在整张图上。先判断是否连通，不连通则提取最大连通子图，用子图计算平均路径长度，同时记录丢弃了多少节点。这个做法在论文里要主动写出来，例如“网络存在部分孤立节点，我们在最大连通分量上计算全局指标”，这是合理的近似，评委不会认为掩盖问题。
def avg_path_on_largest_component(G): if nx.is_connected(G): return nx.average_shortest_path_length(G) largest = max(nx.connected_components(G), key=len) sub = G.subgraph(largest).copy() return nx.average_shortest_path_length(sub), len(sub)逻辑说明：G.subgraph(largest)返回一个视图对象，不复制新图；加.copy()后得到独立图对象，后续计算不会突然丢失节点。
4.3 坑三：节点规模稍大就内存暴涨、运行卡死
现象：n 设为 5000 时，脚本跑了很久没结束，看进程管理器发现内存占用快满，甚至直接无响应。
原因：ER 随机图算法底层要处理所有节点对的候选边，复杂度是 O(n^2)。如果代码里又调用了nx.to_numpy_array，生成一个 5000×5000 的矩阵，仅矩阵本身就有 2500 万元素，占内存约 200MB；若用 Python 默认的 float64，内存需求更高。再加上中间变量，机器很容易被拖垮。
解决：按规模分级处理。n 小于 1000 时用 dense 邻接矩阵没问题；n 较大时避免构造矩阵，只保留边列表，并用nx.to_scipy_sparse_array输出稀疏矩阵。计算指标时优先用基于采样的近似算法，例如用nx.average_clustering(G, trials=1000)做随机抽样估计。生成算法本身也可以换成更省内存的边列表逐条生成方式，但实践中直接用稀疏矩阵转换更简单。
import networkx as nx from scipy.sparse import csr_matrix n = 5000 p = 0.01 G = nx.gnp_random_graph(n, p, seed=1) row = [u for u, v in G.edges()] col = [v for u, v in G.edges()] data = [1] * len(row) sparse_adj = csr_matrix((data, (row, col)), shape=(n, n))逻辑说明：手工从边表构造 CSR 稀疏矩阵，只存储存在的边，空间复杂度正比于边数，而不是节点数的平方。这一步在处理真实网络边表时尤其有用，因为很多数据集本身就是边表格式，不需要经过 NetworkX 中转。
4.4 坑四：把随机图里的波动当成真实网络结构，引发结论误判
现象：在 random graph 上跑社区发现，输出了两个“社区”，论文里就写“观察到了明显的社区结构”，后来别人用相同的参数复现，发现每次跑出来的社区划分都不一样。
原因：随机图本身存在统计波动，任何聚类算法都会找到某些区域边密度稍高，将其识别为社区。没有多次独立重复实验，就无法区分这是真实结构还是随机涨落。
解决：生成同一规模的随机图 100 次，每次跑同一个社区发现或结构检测算法，记录模块度或者社区数量的分布。若真实数据得到的指标明显高于随机图分布的 95 分位数，才下结论。简单写法是先用 random graph 建立经验分布，再对比真实网络数值。
import networkx as nx import numpy as np n = 300 p = 0.05 real_modularity = 0.58 # 假定的真实网络模块度 random_modularity_list = [] for seed in range(100): G = nx.gnp_random_graph(n, p, seed=seed) communities = nx.community.greedy_modularity_communities(G) random_modularity_list.append( nx.community.modularity(G, communities) ) threshold = np.percentile(random_modularity_list, 95) print("随机图模块度95分位数:", threshold) print("真实网络是否超过阈值:", real_modularity > threshold)逻辑说明：community.greedy_modularity_communities是快速贪心社区发现，运行速度较快，适合批量重复实验。np.percentile计算 95 分位数作为显著性门槛，这是复杂度较低但足够说服评委的统计检验方式。
5. 美赛现场可复用的 random graph 对照实验脚本骨架
5.1 批量生成随机图并汇总指标：一张表讲完所有对照组
美赛论文最缺的不是算法复杂程度，而是结论的可验证性。我习惯用一段脚本批量生成多张随机图，把每个模型的指标汇总成 DataFrame，直接贴进论文附录。
import networkx as nx import pandas as pd def net_stats(n, p, seed): G = nx.gnp_random_graph(n, p, seed=seed) degree_seq = [d for _, d in G.degree()] avg_deg = sum(degree_seq) / n clustering = nx.average_clustering(G) if nx.is_connected(G): path = nx.average_shortest_path_length(G) else: largest = max(nx.connected_components(G), key=len) path = nx.average_shortest_path_length(G.subgraph(largest)) return avg_deg, clustering, path rows = [] for seed in range(10, 50): avg_deg, clustering, path = net_stats(n=200, p=0.05, seed=seed) rows.append((seed, avg_deg, clustering, path)) df = pd.DataFrame(rows, columns=["seed", "avg_degree", "clustering", "avg_path"])逻辑说明：通过多个种子生成同一参数下的不同随机图样本，由此得到指标的波动范围，而不是单一数值。avg_path在子图上计算时可能略小于全连通图，因此整理表格时建议单独加一列标注连通节点数占比，论文里可以解释为“随机图存在孤立节点，路径长度基于最大连通分量”。
5.2 对 p 做参数扫描：观察随机网络结构的相变区间
除了对照，random graph 还能用来回答“随机性到什么程度会产生明显结构变化”这类问题。对 p 从 0.005 到 0.2 依次扫描，记录平均聚类系数和平均路径长度变化，往往能看到清晰拐点。这个可视化可以作为论文里支撑参数选择的证据。
import networkx as nx import matplotlib.pyplot as plt p_values = [0.005, 0.01, 0.02, 0.05, 0.1, 0.15, 0.2] clustering_list = [] path_list = [] for p in p_values: G = nx.gnp_random_graph(200, p, seed=42) clustering_list.append(nx.average_clustering(G)) if nx.is_connected(G): path_list.append(nx.average_shortest_path_length(G)) else: path_list.append(float("nan")) plt.plot(p_values, clustering_list, marker="o", label="avg clustering") plt.xlabel("p") plt.ylabel("metrics") plt.legend() plt.savefig("random_graph_parameter_scan.png", dpi=150)逻辑说明：当 p 很低时路径长度为 nan 或者很大，聚类系数接近 0；p 超过某个阈值后网络突然连通，路径长度迅速下降并趋平。这个转变区间就是随机图由“碎片化”到“连通紧密”的相变点，实际建模中可以把真实网络的平均度放到该区间里对比，判断它处于随机模型哪个阶段。
这也是我每次比赛前会反复跑的习惯性检查——把随机种子换掉，把参数重新扫一遍，看看结论是否稳定。很多所谓的网络规律，其实就是随机波动在特定参数区间里恰好表现得很有规律而已。希望这篇 random graph 参考方案能帮你在赛场上少踩几个坑，把时间花在真正值得分析的差异上。
本文还有配套的精品资源，点击获取
