社区检测 Louvain 算法简介

什么是 Louvain 算法？

Louvain 算法是一种基于模块度优化的启发式算法，用于在大型网络中高效地检测社区结构。它由 Vincent Blondel 等人于 2008 年提出，因其速度快、效果好而被广泛应用于社交网络分析、生物信息学等领域。

核心原理

1. 局部移动优化：初始时每个节点自成一个社区，然后尝试将节点移动到邻居所在的社区，以最大化模块度增益。
2. 图聚合：当无法再通过移动节点提高模块度时，将同一社区内的节点聚合为超节点，构建新的简化图。
3. 迭代重复：在新图上重复上述过程，直到模块度不再显著提升。

优势

• 时间复杂度低，适合处理大规模网络。
• 无需预先指定社区数量。
• 能发现层次化的社区结构。

使用方法

本实现基于 python-louvain 库，结合 networkx 构建图结构。运行 main.py 即可对默认数据集（空手道俱乐部网络）进行社区划分，并输出模块度及节点归属结果。

结果展示说明

输入描述

程序无需外部输入文件，内部直接加载 networkx 自带的“空手道俱乐部”（Karate Club）网络数据作为测试图。该图包含 34 个节点和 78 条边，代表一个大学空手道俱乐部成员之间的社交关系。

输出描述

运行 python main.py 后，控制台将输出以下内容：

1. 社区数量统计

   • 示例输出：检测到的社区数量：4
   • 含义：算法自动将网络划分为 4 个紧密连接的子群。

2. 模块度得分

   • 示例输出：模块度得分：0.4452
   • 含义：数值越接近 1 表示社区结构越明显，0.4452 表明该网络具有较好的社区划分效果。

3. 节点归属列表（前 10 个）

   • 示例输出：

   节点 0: 社区 0 节点 1: 社区 0 节点 2: 社区 0 节点 3: 社区 0 节点 4: 社区 1 节点 5: 社区 1 节点 6: 社区 1 节点 7: 社区 0 节点 8: 社区 2 节点 9: 社区 3

   • 含义：列出了前 10 个节点及其被分配到的社区 ID，相同 ID 的节点属于同一个社区。

结论

通过上述输出可知，Louvain 算法成功识别出网络中的潜在社群结构，且无需人工干预即可自动确定最优社区数目。