图机器学习（12）——社区检测

0. 前言

在处理网络数据时，常面临的一个核心问题是如何识别图中的聚类与社区结构。这一需求尤其常见于社交网络分析，因为社交网络天然具有社区特性。不过，底层算法同样适用于其他场景，为聚类与分割任务提供了新思路。例如，在文本挖掘中，这些方法可有效识别新兴话题，或将讨论同一事件/主题的文档归类。
社区检测任务的核心在于划分图结构，使得同一社区内的节点紧密连接，而不同社区的节点连接稀疏。现有策略主要分为两类：：

• 非重叠社区检测算法：节点与社区严格一一对应，因此社区之间没有重叠的节点
• 重叠社区检测算法，允许一个节点属于多个社区，更贴合社交网络的真实特性(如一个人可同时属于摄影圈、科技圈等)，或生物系统中单个蛋白质参与多个生化反应的情形

接下来，我们将介绍社区检测中最常用的技术。

1. 基于嵌入的社区检测

第一类方法是通过对节点嵌入应用经典浅层聚类技术实现社区划分，嵌入算法能将节点映射至向量空间，在这个空间中可以定义表示节点之间相似度的距离度量。嵌入算法在区分具有相似邻域和/或连接特性的节点方面非常有效。然后，可以使用标准的聚类技术，如基于距离的聚类 (K-means)、基于连接的聚类(层次聚类)、基于分布的聚类(高斯混合模型)和基于密度的聚类 (DBSCAN)。根据算法的不同，不同算法可能输出硬分配(单一社区归属)或软分配(概率化归属)。接下来，通过杠铃图示例演示其工作原理。

(1) 首先使用 networkx 工具函数生成基础杠铃图：

import networkx as nx
G = nx.barbell_graph(m1=10, m2=4)

(2) 然后，使用嵌入算法 (本节使用HOPE) 获取节点的降维稠密向量表示：

from gem.embedding.hope import HOPE
gf = HOPE(d=4, beta=0.01)
gf.learn_embedding(G)
embeddings = gf.get_embedding()

(3) 在节点嵌入生成的向量表示上运行聚类算法：

from sklearn.mixture import GaussianMixture
gm = GaussianMixture(n_components=3, random_state=0)
labels = gm.fit_predict(embeddings)

(4) 通过不同颜色高亮显示计算得到的社区结构：

colors = ["blue", "green", "red"]
nx.draw_spring(G, node_color=[colors[label] for label in labels])

如下所示，两个聚类簇及连接节点被正确划分为三个不同社区，准确反映了图的内部结构特征：

2. 谱方法与矩阵分解

另一种实现图划分的途径是通过处理表示图连接特性的邻接矩阵或拉普拉斯矩阵。例如，对拉普拉斯矩阵的特征向量应用标准聚类算法即可实现谱聚类。从某种意义上说，谱聚类也可视为基于嵌入的社区检测算法的特例——其嵌入技术正是通过选取拉普拉斯矩阵前k个特征向量获得的谱嵌入。通过采用不同的拉普拉斯矩阵定义或相似度矩阵，可衍生出该方法的多种变体。
Python 库 communities 提供了该方法的便捷实现，可直接处理从networkx图结构转换的邻接矩阵：

from communities.algorithms import spectral_clustering
adj = np.array(nx.adjacency_matrix(G).todense())
communities = spectral_clustering(adj, k=2)

此外，邻接矩阵(或拉普拉斯矩阵)还可以使用矩阵分解技术(如非负矩阵分解)进行分解，从而获得相似的社区划分效果：

from sklearn.decomposition import NMF
nmf = NMF(n_components=2)
score = nmf.fit_transform(adj)
communities = [set(np.where(score [:,ith]>0)[0]) for ith in range(2)]

本节中将社区归属阈值设为 0 (即默认包含所有关联节点)，但也可调整该值仅保留社区核心成员。需要注意的是，这些方法属于重叠社区检测算法，节点可能同时属于多个社区。

3. 概率模型

社区检测方法还可通过拟合概率图生成模型的参数来实现随机块模型 (Stochastic Block Model, SBM) 则专门针对此设计。该模型基于以下核心假设：节点可划分为 $K$ 个互斥社区，且社区间连接概率具有特定模式。对于包含 $n$ 个节点和 $K$ 个社区的网络，生成模型由以下参数定义：

• 成员矩阵：$M$，一个 $n\times K$ 的矩阵，表示给定节点属于某个社区k的概率
• 概率矩阵：$B$，一个 $K\times K$ 的矩阵，表示属于社区i的节点与属于社区j的节点之间存在边的概率

邻接矩阵通过以下公式生成：
$$a_{ij}=\{\begin{array}{ll}Bernoulli(B_{g_i,g_j)})& i<j\\ 0& i=0\\ a_{ji}& i>j\end{array}$$
其中社区标签 $g_i$ 和 $g_j$ 通过多项式分布 $M_i$ 和 $M_j$ 采样获得。
SBM 的关键在于逆向求解——通过最大似然估计从观测矩阵 $A$ 反推成员矩阵 $M$，从而将社区检测转化为后验概率估计问题。将该方法与随机化谱聚类结合，能够实现超大规模图的社区检测。值得注意的是，当概率矩阵B退化为常数矩阵(即 $B_{ij}\equiv p$ )时，SBM 等价于经典的 Erdős-Rényi 随机图模型。这类模型的优势在于能同时揭示社区间关联关系，例如：

• 识别具有强连接倾向的社区对
• 发现作为"桥梁"的中介社区
• 量化社区间的连接密度差异

4. 成本函数最小化

另一种检测图中社区结构的方法是通过优化特定成本函数来实现。该函数能够表征图结构特征，并对跨社区边施加惩罚(相较于社区内部边)。这种方法的核心在于构建社区质量的量化指标(如模块度)，然后通过优化节点与社区的关联关系，使整体划分质量达到最优。
在二元关联社区结构的背景下，节点的社区归属可用二分变量 $S_i$ 表示(取值为 -1 或 1，分别对应两个不同的社区)。在此设定下，我们可以定义以下量化指标，该指标能有效反映连接不同社区节点的成本：
$$\sum _{i,j\in E}{A}_{ij}(1-S_i{S}_j)$$
其中，当两个相连的节点 ($A_{ij}>0$) 属于不同社区 ($S_i{S}_j=-1$) 时，该边会产生正向贡献值；而当两个节点不相连 ($A_{ij}=0$) 或同属一个社区 ($S_i{S}_j=1$) 时，贡献值则为零。因此，该问题的核心在于寻找最优的社区分配方案( $S_i$ 和 $S_j$ 取值)以使上述函数最小化。不过，这种方法仅适用于二元社区检测，应用范围较为有限。
这类方法中另一个非常流行的算法是 Louvain 算法，该算法旨在最大化以下定义的模块度 (modularity)：
$$Q=\frac{1}{2m}\sum _{i,j\in E}(A_{ij}-\frac{k_i{k}_j}{2m})\delta (c_i,c_j)$$
其中，$m$ 表示图中边的总数，$k_i$ 和 $k_j$ 分别表示第 $i$ 个和第 $j$ 个节点的度，$\delta (c_i,c_j)$ 为 Kronecker delta 函数，当 $c_i=c_j$ 时取 1，否则取 0。模块度本质上衡量的是：与保持相同边数和度分布的随机重连网络相比，当前社区划分结构的优越程度。该指标通过比较实际边数与随机预期边数的差异，来评估社区划分的质量——当社区内部连接显著高于随机预期时，模块度趋近于 1；若划分结果与随机网络无异，则模块度接近 0。
为高效实现模块度最大化，Louvain 方法通过迭代进行以下步骤：

1. 模块化度优化：遍历所有节点，针对每个节点计算其加入相邻节点所属社区时可能带来的模块度变化值 $\Delta Q$。完成所有 $\Delta Q$ 值计算后，将该节点调整至能带来最大模块度增量的社区。若节点移至任何相邻社区均无法提升模块度，则保持其原有归属。此优化过程持续至网络结构不再变化为止。
2. 节点聚合：构建新网络，将同一社区的所有节点合并为超节点，社区间的连接边权重取原网络对应社区间所有边权重之和。社区内部的边转化为带权自环，其权重为该社区内部所有边权重总和。

communities库中提供了 Louvain 算法的实现：

from communities.algorithms import louvain_method
communities = louvain_method(adj)

另一种模块度最大化方法是 Girvan-Newman 算法，其原理是通过迭代移除具有最高介数中心性的边(这类边通常连接不同节点簇)，以创建连通分量社区：

from communities.algorithms import girvan_newman
communities = girvan_newman(adj, n=2)

需要注意的是，该算法需计算所有边的介数中心性以确定待移除边。对于大型图结构，此类计算可能产生极高开销。事实上 Girvan-Newman 算法的时间复杂度为 $O(n{m}^2)$ (其中 $m$ 为边数，$n$ 为节点数)，因此不适用于大规模数据集处理。