获取具有指定聚类系数与平均路径长度网络的重连策略

一、替代模拟退火（SA）的定向边重连方法 #

1. 仅调整全局聚类系数（近似固定平均路径长度） #

• 局部三角形增删操作：
  选择一个节点v，找到它的两个未相连邻居u和w，添加边(u,w)可直接提升全局聚类系数；反之，删除v的两个邻居间的边则降低聚类系数。这类操作仅影响局部节点的三角形数量，对全局平均路径长度的扰动极小，适合在固定路径长度的基础上微调聚类系数。
• 定向边交换变体：
  选取两对边(u,a)和(v,b)，其中u与v相邻、a与b不相邻，删除(u,a)和(v,b)并添加(u,v)和(a,b)。该操作不改变边密度，且仅影响局部结构，对全局平均路径的影响可忽略，可用于批量调整聚类系数。

2. 仅调整平均路径长度（近似固定全局聚类系数） #

• 长距离边的增删：
  借鉴小世界模型的核心逻辑，随机添加少量连接远距离节点的边，可显著缩短平均路径长度，同时几乎不破坏局部聚类结构；反之，删除这类长距离边则会增加路径长度。该操作适合在固定聚类系数的前提下快速调整路径长度。
• 跨模块边交换：
  选择分属不同局部模块的两对边(u,v)和(x,y)（u、v在同一模块，x、y在另一模块），交换为(u,x)和(v,y)。此操作能优化全局连通性、缩短路径长度，且对各模块内的三角形结构（即聚类系数）影响极小。

二、模拟退火（SA）的效率优化方案 #

若必须使用SA，可通过以下方式大幅降低平均路径长度的计算成本：

• 增量式路径更新：
  当执行边的添加/删除操作后，无需重新计算全图所有节点对的最短路径，仅需以操作涉及的两个节点为起点，重新执行BFS更新它们到其他节点的最短距离，再针对性更新受影响的节点对路径长度。此方法可将单次路径计算成本从O(n(n+m))降至O(n+m)。
• 采样近似估算：
  无需计算所有节点对的平均路径，随机采样10%-20%的节点对（如1000节点网络采样100对），用采样结果的平均路径近似全局值。该方法的计算量仅为全量计算的1/5-1/10，且近似精度足够支撑SA的迭代判断。
• SA参数调优：
  初始温度设置为与当前目标偏差匹配的合理值，避免过高温度导致无效迭代；设置动态降温速率，在迭代后期加快降温以收敛；同时限制单次迭代的边操作次数，减少不必要的计算开销。

内容的提问来源于stack exchange，提问作者Johannes Nauta