Small-world 小世界网络分析算子集
算子类别：Small-world（图重连与参考图生成，用于小世界网络分析）
算法数量：1 个
适用阶段：小世界特性评估、网络随机化基准构建、重连对比分析
产品定位：为“这个网络是否具备小世界特性？与匹配度序列的随机网络相比有何差异？”提供基准参考图生成与随机重连算子。
一、算子集概述
Small-world 算子集聚焦于小世界网络分析中的参考图生成与图随机化重连，主要回答以下问题：
-
基准构建
- 如何生成一个与原始网络具有相同节点数和度序列，但连接模式完全随机的参考图？
- 用于计算小世界系数时的随机图基准。
-
随机重连
- 是否可以通过保持度序列不变的方式，对网络进行随机重连？
- 在重连过程中是否引入了多重边或自环？如何避免？
二、算子能力分类
| 能力类型 | 对应算子 | 功能描述 |
|---|---|---|
| 随机参考图生成 | random_reference | 通过保持度序列不变的边交换策略，生成一个随机化的参考图，用于小世界网络分析与零模型比较 |
三、通用输入输出约定
- 输入
G：NetworkX 无向图（通常要求连通且无自环、无重边） - 关键参数：
niter：边交换的迭代次数（默认为10 * E，保证充分混合）connectivity：是否要求输出图连通（默认True）
- 常见输出类型：NetworkX Graph（与输入图具有相同节点集和度序列的随机参考图）
四、算子详细说明
1. random_reference —— 生成随机参考图
功能说明
通过双边缘交换（double-edge swap）的方式对图进行随机重连，在严格保持每个节点的度不变的条件下，生成一个与原始网络结构无关的随机参考图。该参考图用于与原始网络比较聚类系数、平均最短路径长度等指标，从而判断网络是否具有小世界特性（高聚类、短路径）。
产品价值
- 为小世界网络判定提供统计基准（零模型）
- 支持网络的随机性假设检验
- 可用于计算小世界系数 σ 或 ω 的过程
- 保持度序列不变，使比较更具公平性
典型场景
- 社交网络小世界效应验证
- 脑网络功能连接小世界属性分析
- 蛋白质相互作用网络随机化对照
- 交通网络或电力网络的结构随机性评估
- 网络模体（motif）显著性检验时的随机网络生成
关键参数
niter：边交换迭代次数，整数。建议使用默认值以保证混合充分connectivity：布尔值。True时保证输出图仍然连通（默认行为）；当原始图连通时推荐使用
适用与特性
- 图类型：无向图（连通图更佳）
- 输出：与
G度序列完全相同的随机图 - 算法本质：保持度序列的马尔可夫链边交换
- 复杂度：
O(niter * d)，其中d为平均度，通常总复杂度与边数线性相关
注意事项
- 如果原始图过小或结构过于特殊，可能难以在保持连通的前提下充分随机化
- 该算子生成的是匹配度序列的配置模型中的一个样本，不处理权重或方向（有向/加权版本需其他工具）
- 迭代次数过少可能导致随机化不充分，建议使用默认值
五、推荐使用指南
1. 小世界特性分析
- 计算原始图的平均聚类系数
C和平均最短路径长度L - 调用
random_reference生成多个随机参考图，计算其平均聚类系数C_r和平均最短路径L_r - 若
C >> C_r且L ≈ L_r，则网络具有较强的同配小世界特性
2. 网络模体或功能显著性检验
- 生成大量
random_reference样本作为零分布，用于检验某些网络属性的统计显著性
六、可直接回答的典型问题
- “与给定度序列匹配的随机网络长什么样？”
- “如何生成一个和原始网络节点个数、每个节点的邻居数完全一样，但连接方式完全随机的对照网络？”
- “判断我的网络是否是小世界网络，需要用什么算子？”
- “生成随机基准图时，是否保证网络仍然连通？”
七、算子清单
| 序号 | 算子名称 | 中文说明 |
|---|---|---|
| 1 | random_reference | 生成与给定图具有相同节点集和度序列的随机参考图（保持连通） |