🔬 physics

Heuristic and exact modularity optimization with size-constrained communities

本文通过提出一种用于模块度优化的启发式方法，并将其与精确整数优化基线进行验证，解决了规模受限的社区检测问题，证明了这些方法为在用户指定规模范围内获取社区提供了一种 principled 的替代方案，以替代分辨率参数调节。

原作者： Filipi N. Silva, Samin Aref, Vincent Traag, Santo Fortunato

发布于 2026-05-26

📖 1 分钟阅读☕ 轻松阅读

原作者： Filipi N. Silva, Samin Aref, Vincent Traag, Santo Fortunato

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象你是一位城市规划师，正试图将一座庞大而繁忙的城市划分为不同的街区。你的目标是将彼此熟悉、经常往来的人们归入不同的“社区”。这正是计算机科学家所称的“社区发现”。

通常，算法会通过查看连接图谱来执行这一任务，并判断：“这些人联系非常紧密，所以他们一定属于同一个街区。”然而，这里存在一个问题：算法并不关心街区的“规模”。它最终可能会创建一个拥有 10,000 人的巨大且拥挤的城区，以及一堆只有两人的微小而孤独的村落。

在现实世界中，专家通常知道什么样的“理想”街区规模是合适的。营销团队知道，一个客户细分群体至少需要 100 人才能发挥作用。脑科学家知道，一个功能脑区的规模不应等同于整个大脑。但标准工具不允许你提出这样的要求：“确保每个街区的人数都在 50 到 200 人之间。”

本文介绍了一种解决该问题的新方法。以下是用通俗语言进行的拆解：

旧方法：靠“分辨率旋钮”进行猜测

以前，如果专家想要控制街区规模，他们不得不使用一个“分辨率旋钮”。

类比：想象你正在调收音机寻找特定电台。你不知道确切的频率，所以只能来回转动旋钮，听着声音是否变得更清晰。
问题：在网络科学中，转动这个旋钮会改变社区的“平均”规模，但它是一种笨拙的工具。你可能得到了正确的平均值，但仍可能得到一个巨大的街区加上一堆微小的街区。你无法控制“变异度”（即最大组与最小组之间的差异）。这就像试图通过随意调高或调低烤箱温度来烤出大小完全一致的饼干；你可能得到了正确的平均大小，但有些饼干会烤焦，有些则还是生面团。

新方法：“强制规模”规则

作者（Filipi Silva, Samin Aref, Vincent Traag 和 Santo Fortunato）提出了一种新方法，其作用就像俱乐部门口严格的保镖。

类比：与其猜测温度，不如告诉算法：“任何街区的人数不得少于 50 人，也不得多于 200 人。”
工作原理：他们创建了一种启发式（一种聪明且快速的捷径），在严格遵守这些规模规则的同时，尝试找到最佳的分组方案。
- 如果一个群体变得太小，算法会将人们推出去。
- 如果一个群体变得太大，它会将他们拆分。
- 这是通过在数学公式中添加“惩罚”来实现的。如果一个群体违反了规模规则，算法就会收到一个“皱眉”（惩罚分数），并试图修正它。

“黄金标准”验证

为了证明他们这种新的“聪明捷径”确实有效，他们还构建了一种精确方法。

类比：将精确方法想象成一位超级缓慢但超级聪明的数学家，他会检查划分城市的每一种可能方式，以找到“完美”的答案。这需要耗费大量的时间和计算能力，因此无法将其用于大城市。
结果：他们将快速的“聪明捷径”与缓慢的“完美数学家”进行了比较。他们发现，这种捷径极其可靠。它找到的解决方案与完美方案几乎完全相同，但速度快得多，使其能够应用于巨大的网络。

现实世界测试

该团队在两种类型的地图上进行了测试：

假想城市（合成基准）：他们构建了计算机生成的网络，并在其中预先知道了“正确”的街区。
- 结果：旧的“旋钮”方法往往无法找到正确的街区，尤其是在连接关系有些混乱时。而新的“强制规模”方法几乎每次都能找到正确的群体，即使旧方法感到困惑。
真实城市（真实网络）：
- 市场细分：在商业领域，他们展示了这如何帮助将客户分组为具有实用规模的群体，避免了出现一个巨大群体和许多无用微小群体的问题。
- 脑图谱：他们查看了人脑图谱。标准方法通常只是将大脑划分为两个大半球（左脑和右脑），这并没有太大帮助。通过根据神经科学家对脑区的认知设定规模限制，他们的方法发现了 6 个独特且有意义的功能集群，这些集群与专家知识相一致。

核心结论

这篇论文为科学家和专家提供了一种工具，使他们能够说：“我知道在我的领域中，合理的群体规模是什么样的，我希望计算机能尊重这一点。”

不再盲目地转动旋钮并寄希望于好运，你现在可以设定清晰的边界（例如，“群体人数必须在 43 到 187 人之间”）。新方法尊重这些边界，找到高质量的分组，并且速度快到足以应用于真实的、大规模的数据。它将社区发现从一场“猜测与检查”的游戏，转变为一种精确、有原则的过程。

技术摘要：带规模约束社区的启发式与精确模块度优化

问题陈述

社区检测是网络分析中的一项基本任务，但标准算法往往未能纳入关于社区规模的领域特定先验知识。在市场细分、神经科学（脑连接组）和基因组学（染色体相互作用）等应用中，专家通常掌握关于合理社区规模范围的知识。然而，现有的无约束方法经常产生规模差异极大的划分（例如，一个巨大的社区和许多微不足道的社区），或者无法与生物学或功能现实相一致。

虽然多分辨率技术允许用户通过调整分辨率参数（ $\gamma$ ）间接影响平均社区规模，但这种方法无法控制单个社区的规模，也不能保证所有社区都落在用户定义的特定范围内。本文解决了**带规模约束的最大模块度（SMM）**问题：寻找一种网络划分，在最大化模块度的同时，确保每个社区规模 $n_c$ 满足 $n_{min} \le n_c \le n_{max}$ 。

方法论

作者提出了一种解决 SMM 问题的双重方法：一个精确优化基线和一个可扩展的启发式方法。

1. 精确优化基线（SMMk）

为了建立可靠性的真实基准，作者将问题表述为整数规划（IP）。

公式化：他们扩展了最大模块度 $k$ -划分（MMk）问题的标准整数规划公式。
约束：该模型包含线性约束以强制执行规模界限。具体而言，他们引入了约束，确保对于任何非空社区 $c$ ，节点数量 $\sum x_{ic} \ge n_{min}$ ，并且对于所有潜在社区， $\sum x_{ic} \le n_{max}$ 。
求解器：该模型使用 Gurobi 优化器求解，以获得中小规模图的全局最优（或近优）划分。这作为评估启发式方法的基线。

2. 启发式优化（约束 Leiden - CL）

在标准模块度启发式算法（如 Leiden 算法）中直接强制执行规模约束是有问题的，因为局部节点移动很容易违反规模界限（例如，将一个节点移动到一个新的单节点社区会违反 $n_{min} > 1$ ）。

惩罚方法：作者采用惩罚方法，而不是障碍法（障碍法会限制搜索空间）。他们通过优化修改后的目标函数，将约束问题转化为无约束问题：
$Q'(G, P) = Q(G, P) - \phi \Theta(P)$
其中 $\Theta(P)$ 是违反规模约束的社区的惩罚函数， $\phi$ 是惩罚权重。
惩罚函数：规模为 $n_c$ 的社区的惩罚 $\theta(n_c)$ 定义为：
$\theta(n_c) = \begin{cases} \sqrt{n_{min} - n_c} & \text{if } n_c < n_{min} \\ \sqrt{n_c - n_{max}} & \text{if } n_c > n_{max} \end{cases}$
选择平方根函数是因为它是次可加的，防止算法陷入局部最优，即在一个违反规模的大社区被分裂成两个较小的违反规模社区时，总惩罚反而更低的情况。
渐进调度：算法从 $\phi = 0$ （无约束）开始。如果生成的划分违反约束，则增加 $\phi$ （从 $10^{-4}$ 开始并加倍），并从之前的解重新初始化优化。这一过程持续进行，直到找到可行的划分。

主要结果

作者在合成和真实世界网络上评估了所提出的**约束 Leiden（CL）方法与无约束 Leiden（UL）以及约束整数规划（CIP）**基线的表现。

合成基准

植入划分模型：在具有已知真实社区的网络中，CL 和 CIP 在检索率（通过调整互信息 AMI 衡量）方面显著优于 UL，特别是在混合参数较低到中等时。UL 经常无法检索到植入的社区，因为它产生的划分规模超出了预期范围。
团簇环：在一个由 50 个大小为 5 的团簇顺序连接而成的图中，UL 仅在手动将分辨率参数调整到特定范围（ $[5, 40]$ ）时才能检索到正确的划分。相比之下，CL 在给定正确规模范围 $[2, 8]$ 的情况下，在默认分辨率（ $\gamma=1$ ）下准确检索到了植入的划分。
可靠性：启发式 CL 的检索率始终接近 CIP 精确基线，有时甚至相等，表明在这些情境下，启发式方法并未为了速度而牺牲准确性。

真实世界网络

脑连接组：应用于布达佩斯脑连接组网络时，UL 产生了一个包含四个社区的平凡划分（对应于大脑半球），这缺乏神经科学效用。
领域对齐：通过应用 CL，并使用源自专家知识的规模范围（基于 Brainnetome 和 Schaefer 图谱， $[43, 187]$ 个节点），该方法生成了 6 个社区。这一结果比无约束结果更好地与已知的大脑功能簇（例如 Yeo 等人定义的 7 个簇）相一致。
变异控制：作者证明，在 UL 中改变分辨率参数可以控制平均社区规模，但无法控制规模的变异（方差）。CL 提供了对均值和变异性的直接控制，确保所有社区都落在指定的界限内。

意义与主张

本文声称，所提出的方法提供了一种原则性方式，将领域专业知识纳入社区检测。

直接控制：与调整分辨率参数的“试错”做法不同，CL 允许用户明确定义社区的最小和最大规模，直接满足领域专家的需求。
可扩展性：虽然精确的 IP 方法（CIP）受计算复杂度限制仅适用于较小的图，但 CL 启发式方法具有可扩展性，可应用于大型网络，使其在实际应用中具有可行性。
实现：该方法已集成到 Python Leiden 算法包中，便于立即使用。

作者得出结论，尽管模块度存在已知局限性（如分辨率限制和缺乏清晰的统计基础），但通过其启发式方法强制执行规模约束的能力，能够产生更具信息量且与领域一致的划分。他们建议未来的工作可以探索将规模约束纳入其他框架，如随机块模型（SBMs），以便在统计推断上下文中利用这些约束。