一、经典社区发现算法原理与流程
1. Louvain 算法（基于模块度优化）
- 原理： 通过迭代优化模块度（Modularity）指标，逐步合并节点形成社区。模块度衡量社区内部连接密度与随机网络的差异，公式为： $Q = \frac{1}{2m} \sum_{i,j} \left[ A_{ij} - \frac{k_i k_j}{2m} \right] \delta(c_i, c_j)$ 其中，$A_{ij}$ 为邻接矩阵，$k_i$ 为节点度数，$c_i$ 为节点所属社区，$m$ 为总边数。
- 流程：
- 初始化：每个节点自成一个社区。
- 局部优化：遍历每个节点，尝试将其加入邻居社区，选择使模块度增量最大的社区（或保留原社区）。
- 构建粗粒度网络：将每个社区视为超节点，边权重为原社区间连接数。
- 重复迭代：对粗粒度网络重复步骤 2-3，直至模块度不再提升。
- 特点：高效（适合大规模网络），层次化社区结构，结果依赖初始节点顺序。
2. Girvan-Newman（GN）算法（分裂法）
- 原理： 基于边介数（Edge Betweenness）逐步分裂网络。边介数表示通过该边的最短路径数量，介数越高的边越可能位于社区间。
- 流程：
- 计算所有边的介数。
- 删除介数最高的边。
- 重复步骤 1-2，直到网络分裂为孤立节点，记录每次分裂的社区数目与模块度，选择模块度峰值对应的社区划分。
- 特点：适用于小网络，计算复杂度高（O(n^3)），需手动确定最佳社区数。
3. 谱聚类（Spectral Clustering）
- 原理： 通过图的拉普拉斯矩阵（Laplacian Matrix）的特征向量将节点嵌入低维空间，再用聚类算法（如 K-means）划分社区。
- 流程：
- 构建邻接矩阵 $A$，计算度矩阵 $D$（对角矩阵，对角线为节点度数）。
- 计算归一化拉普拉斯矩阵 $L = I - D^{-1/2} A D^{-1/2}$。
- 提取 $L$ 的前 $k$ 个最小特征值对应的特征向量，组成特征矩阵。
- 对特征矩阵的行进行 K-means 聚类，得到社区划分。
- 特点：理论性强，适合社区结构清晰的网络，需预先指定社区数 $k$。
4. Infomap 算法（基于信息论）
- 原理： 将网络视为随机游走过程，通过压缩编码路径信息来发现社区。目标是最小化描述游走路径的编码长度，公式为： $C = H_M + H_C$ 其中，$H_M$ 为社区间转移的熵，$H_C$ 为社区内节点的熵。
- 流程：
- 初始化每个节点为独立社区。
- 随机选择一个节点，尝试将其移动到邻居社区，计算编码长度变化，保留最优移动。
- 重复步骤 2 直至收敛，合并具有相同父节点的社区。
- 特点：抗噪声能力强，可检测嵌套社区，结果具有概率解释性。
5. Leiden 算法（Louvain 改进版）
- 原理： 在 Louvain 基础上引入'分辨率限制'（Resolution Limit），解决 Louvain 在小社区上的分辨率问题，并优化局部移动策略以提高效率。
- 流程： 与 Louvain 类似，但在局部优化阶段采用更严格的社区合并条件，并支持自定义分辨率参数 $\gamma$（$\gamma > 1$ 倾向于小社区，$\gamma < 1$ 倾向于大社区）。
- 特点：速度更快，社区划分更准确，适合不同规模网络。
