Louvain 社区发现
概述
Louvain 算法通过优化模块度来检测社区——模块度即社区内部边所占比例减去边随机分布时的期望比例。这是一种贪心、层次化的算法，在稀疏图上以 O(n log n) 运行，可产出多个分辨率下的社区层级。
适用场景
触发条件：
发现社交、组织或交互网络中的自然分组
按行为相似度对用户/客户进行分群
分析复杂网络的模块化结构
不适用场景：
需要重叠社区时（应使用 DEMON 或 BigCLAM）
社区已预定义、只需对节点分类时（应使用标签传播）
算法
铁律：模块度存在分辨率极限 Louvain 优化的是模块度，而模块度存在已知的分辨率极限（Fortunato & Barthélemy, 2007）：它无法检测小于 √(2E) 的社区，其中 E 为总边数。在大型网络中，小而真实的社区可能被合并。为获得更好结果，应使用多分辨率方法或 Leiden 算法（改进版 Louvain）。
阶段 1：输入校验
从交互数据构建无向加权图。边权表示交互强度（频率、时长、数量）。 门槛：图已加载，无孤立节点（或已决定如何处理孤立节点）。
阶段 2：核心算法
阶段 1——局部移动：
将每个节点分配到各自的社区
对每个节点，计算移动到各邻居社区所带来的模块度增益
将节点移动到具有最大正增益的社区
重复，直到不再有可获益的移动
阶段 2——聚合： 5. 构建新图，其中节点 = 社区，边 = 社区间边之和 6. 在聚合图上重复阶段 1 7. 持续直到模块度不再提升
阶段 3：验证
检查：模块度 Q > 0（非平凡划分），社区规模合理（不是一个大社区加许多单点），抽样人工检查社区。 门槛：模块度为正，社区规模呈类幂律分布。
阶段 4：输出
返回社区分配及模块度分数。
输出格式
{ "communities": [{"id": 0, "size": 45, "top_members": ["Alice", "Bob"], "internal_density": 0.35}], "summary": {"num_communities": 12, "modularity": 0.65, "largest": 120, "smallest": 5}, "metadata": {"algorithm": "louvain", "nodes": 500, "edges": 2000} }
示例
示例输入/输出
输入：200 名员工的邮件网络，按邮件频率加权 预期：社区大致对应部门/团队，模块度约 0.5-0.7。
边界情况
输入 | 预期 | 原因
完全图 | 一个社区或随机划分 | 无模块化结构
非连通分量 | 每个分量 = 一个社区 | 自然分离
加权与不加权 | 社区不同 | 权重改变模块度计算
注意事项
非确定性：节点处理顺序会影响结果。应多次运行并选择模块度最高的划分，或使用 Leiden 算法（更稳定）。
分辨率参数：标准 Louvain 在模块度中使用 γ=1。改变 γ 可揭示不同尺度的社区。γ>1 找到更小的社区；γ<1 找到更大的社区。
Leiden 优于 Louvain：Louvain 可能产生连接不良的社区（移除一个节点即导致社区断开）。Leiden 算法修复了这一保证。
时间稳定性：在动态网络中，即使网络变化很小，不同快照间的社区分配也可能剧烈变化。应使用时间平滑。
解释：社区发现能找到结构，但解释节点为何聚类需要领域知识。不要过度解读自动检测出的社区。
参考资料
关于 Leiden 算法（改进版 Louvain），见 references/leiden.md
关于多分辨率社区发现，见 references/multi-resolution.md