Ch.04 社区检测：翻译 + 学习笔记

第 04 章精校翻译：社区检测

第 4 章　网络中的社区检测（Community Detection in Networks）

我们在引言中已经看到，许多网络的节点集可以基于节点属性或节点行为划分为若干群体。例如，空手道俱乐部网络（karate-club network）的成员分裂为两个群体（Zachary, 1977），而政治博客网络（political blog network）中的博客被标注为自由派或保守派。社区检测（community detection）——又称社区恢复（community recovery）或图聚类（graph clustering）——就是基于节点之间的相互作用来推断潜在的社区结构。

社区检测是一个微妙的问题，因为严格地说，社区这一概念是界定不清的。事实上，尽管社区结构在真实网络中相当普遍，却难以恰当地定义什么是社区。尽管如此，我们可以给出以下线索。

• 基于节点相似性的定义。 我们可以把彼此行为相似的节点群体定义为社区。例如，可以把社交网络的节点分为影响者（influencers，发布大量内容并被众多用户关注的人）和跟随者（followers，主要与影响者互动的外围节点）。为了评估两个节点的相似性，可以使用节点相似性度量（如 Personalized PageRank 或基于首中时间的中心性指标，见第 3 章）。
• 局部定义。 直观上，我们可以把社区定义为一组彼此之间大量互动的节点。在这种情况下，社区是组内连接稠密、而与网络其余部分连接稀疏的节点群体。
• 全局定义。 我们还可以用一个称为模块度（modularity）的量来评估把图划分为互不重叠社区的质量。这个量把社区内部的边数与某个零模型（null model）下内部边数的期望值进行比较。

除了上述"如何恰当地定义社区"的问题之外，我们还将看到，社区检测在计算上往往很困难，因此需要依赖近似算法。

已知真值社区（ground-truth communities）的真实网络常被用来比较和评估各种社区检测算法。下面我们给出此类网络的一份不完整清单。我们在图 4.1 中画出了其中若干网络，并在表 4.1 中汇总了这些网络的一些统计量。也请参阅引言部分，那里对这些以及另外一些网络有更详细的描述。

• Mark Newman 的个人网页上提供了一批标准网络：http://www-personal.umich.edu/~mejn/netdata/，其中包括广受欢迎的 Zachary 空手道俱乐部（Zachary, 1977）、一个海豚互动网络（Lusseau et al., 2003）以及政治博客数据集（Adamic and Glance, 2005）。
• Linqs 网页 https://linqs.soe.ucsc.edu/data 托管了若干数据集，包括 Cora、Citeseer、Pubmed 和 WebKB（Lu and Getoor, 2003）。
• netset 网页 https://netset.telecom-paris.fr/ 托管了若干数据集，包括维基百科条目之间链接构成的图。
• 最后，Stanford Large Network Dataset Collection（https://snap.stanford.edu/data/）托管了大量更大规模的网络。

使用合成网络来评估社区检测算法的有效性也很常见。一个被广泛使用的带社区结构的随机图模型是随机分块模型（Stochastic Block Model，SBM）及其度校正变体（见 2.3 节）。

本章结构如下。我们首先在 4.1 节介绍若干基于割的方法，以及它们以谱聚类（spectral clustering）形式出现的松弛。4.2 节介绍基于模块度的方法，特别是用于模块度最大化的非常高效的 Louvain 算法。4.3 节介绍社区检测的贝叶斯框架。此外，在每一节中，我们都通过数值实验验证所提出的方法，并讨论每种方法的局限性。最后，我们在 4.4 节以对社区检测问题的理论分析结束本章。

4.1　基于割的方法（Cut-based Methods）

在本节中，我们研究把图分成 $K \geq 2$ 个组的问题，要求组内的边密度高于两个不同组之间的边密度。

4.1.1　图二分（Graph Bisection）

我们考虑一个节点为 $\{1, \ldots, n\}$ 的图，其邻接矩阵（adjacency matrix）为 $A = (a_{ij})_{1 \leq i, j \leq n}$。图是无向的但可以带权，因此 $a_{ij} = a_{ji} \geq 0$。节点 $i \in V$ 的度（degree） $d_i$ 定义为 $\sum_{j=1}^{n} a_{ij}$。

我们的目标是把节点集 $V$ 划分为两个子集 $V_1, V_2$，使得 $V_1 \cap V_2 = \emptyset$（互不重叠的社区）且 $V_1 \cup V_2 = \{1, \ldots, n\}$。注意 $V_2 = V_1^c$，其中 $V_1^c$ 表示 $\{1, \ldots, n\} \setminus V_1$，即 $V_1$ 的补集。

乍一看，我们可能想求解

$$ \widehat{V}_1 = \underset{V_1 \subset [n]}{\arg\min}\; \operatorname{Cut}(A, V_1) . \tag{4.1} $$

但是，这个最小化问题的平凡解是 $\widehat{V}_1 = V$ 和 $\widehat{V}_1 = \emptyset$，它们对应于把每个节点都分到一个簇里、而让第二个簇为空！此外，即使我们强制要求 $V_1 \neq V$ 且 $V_1 \neq \emptyset$，也很可能得到几乎所有节点都在一个簇中、而另一个簇只有寥寥几个节点的解。

因此，可以要求预测出的集合 $V_1$ 与 $V_1^c$ 大小大致相同。为此，可以对不平衡的解施加惩罚。首先，让我们通过把最小化问题限制在满足 $|V_1| = \frac{n}{2}$ 的集合 $V_1$ 上，强制 $V_1$ 与 $V_1^c$ 的大小完全相等。这个新的最小化问题

$$ \underset{V_1 \subset [n]:\; |V_1| = \frac{n}{2}}{\arg\min}\; \operatorname{Cut}(A, V_1) \tag{4.2} $$

称为图二分问题（graph bisection problem）。当然，实践中两个簇的大小往往不同。这将在下一节介绍，届时还会推广到 $K$ 个簇（$K \geq 2$）的情形。

但是，即使在这个简单的两簇情形下，另一个问题也出现了：最小化问题 (4.2) 是 NP-hard 的（Wagner and Wagner, 1993; Garey et al., 1974）。因此，我们不得不依赖近似方法。下面，我们提出一种基于拉普拉斯矩阵（Laplacian）的松弛方法。一种基于邻接矩阵的类似方法和一种基于半定规划（semidefinite programming）的不同方法将在 4.1.3 节介绍。

第一种松弛方法：拉普拉斯谱聚类（First relaxation method: Laplacian spectral clustering）

因此，最小化问题 (4.2) 等价于

$$ \hat{z} = \underset{\substack{z \in \{-1; 1\}^n \\ \|z\|_2^2 = n \\ z \perp 1_n}}{\arg\min}\; z^T L z , \tag{4.3} $$

其中对应的两个簇就是 $\widehat{V}_1 = \{i \in [n] : \hat{z}_i = 1\}$ 与 $\widehat{V}_1^c = \{i \in [n] : \hat{z}_i = -1\}$。(4.3) 的一种可能的连续松弛（continuous relaxation）是

$$ \hat{x} = \underset{\substack{x \in \mathbb{R}^n \\ \|x\|_2^2 = n \\ x \perp 1_n}}{\arg\min}\; x^T L x . $$

所谓松弛，是指我们从 $z \in \{-1; 1\}^n$ 转向实值向量 $x \in \mathbb{R}^n$。这使我们可以用标准的微积分方法求解 $\arg\min$ 问题（参见引理 4.1）。一旦算出 $\hat{x}$，就可以按 $\hat{x}_i$ 的符号进行聚类。这就导出了标准的谱聚类方法（算法 4）。尽管如此，一般而言并不能保证松弛问题 (4.3) 的解等于原问题 (4.2) 的真实解。更细致的讨论见 4.4 节。

4.1.2　一般情形：多于两个簇（General Case: More Than Two Clusters）

在本节中，我们把上一节的方法推广到 $K \geq 2$ 个大小可能不同的簇的一般情形。

设 $V_1, \dots, V_K$ 是把 $V$ 分成 $K$ 个互不重叠的簇的划分，即 $V_1 \cup \ldots \cup V_K = V$ 且当 $k \neq \ell$ 时 $V_k \cap V_\ell = \emptyset$。在上一节中，我们强调了在割最小化问题中惩罚簇大小不平衡的划分的重要性。为了度量簇 $V_k$ 的大小，我们定义以下两个度量：

$$ |V_k| = \sum_{i=1}^{n} \mathbf{1}(i \in V_k) \qquad \text{和} \qquad \operatorname{vol}(V_k) = \sum_{i \in V_k} d_i . $$

量 $|V_k|$ 对应于属于集合 $V_k$ 的节点数，而 $\operatorname{vol}(V_k)$ 是集合 $V_k$ 的体积（volume），即属于 $V_k$ 的节点的度之和。我们将不直接最小化割，而是最小化以下两个量之一：

$$ \operatorname{RatioCut}(A, V_1, \ldots, V_K) = \sum_{k=1}^{K} \frac{\operatorname{Cut}(A, V_k)}{|V_k|} , \tag{4.4} $$

$$ \operatorname{NCut}(A, V_1, \ldots, V_K) = \sum_{k=1}^{K} \frac{\operatorname{Cut}(A, V_k)}{\operatorname{vol}(V_k)} . \tag{4.5} $$

Ratio-Cut（相应地，归一化割 Normalized-Cut 或 NCut）对应于按集合 $V_k$ 的大小（相应地，体积）施加惩罚的割：小集合承受大惩罚。因此，我们可以期望最小化 Ratio-Cut 或 Normalized-Cut 的解给出大小均衡的簇。

与前面一样，对所有可能的划分 $(V_1, \dots, V_K)$ 最小化这些量是 NP-hard 的，我们转而求解该问题的一个松弛版本。让我们定义矩阵 $H = (h_{ik}) \in \mathbb{R}^{n \times K}$：

$$ \forall i \in [n],\; \forall k \in [K]:\quad h_{ik} = \left\{ \begin{array}{ll} \dfrac{1}{\sqrt{|V_k|}} , & \text{若 } v_i \in V_k , \\ 0 , & \text{其他} . \end{array} \right. \tag{4.6} $$

$H$ 是把 $K$ 个指示向量作为列的矩阵，其中每个集合 $V_k$ 的大小被用作归一化项。类似地，定义 $N = (n_{ik}) \in \mathbb{R}^{n \times K}$：

$$ \forall i \in [n],\; \forall k \in [K]:\quad n_{ik} = \left\{ \begin{array}{ll} \dfrac{1}{\sqrt{\operatorname{vol}(V_k)}} , & \text{若 } v_i \in V_k , \\ 0 , & \text{其他} . \end{array} \right. \tag{4.7} $$

这里我们用每个集合 $V_k$ 的体积作为归一化项。我们有以下引理。

因此，最小化 RatioCut 可以改写为：

$$ \underset{(V_1, \ldots, V_k)}{\arg\min}\; \operatorname{Tr}\left( H^T L H \right) , \tag{4.8} $$

其中 $L = D - A$，$H$ 由式 (4.6) 定义。类似地，最小化 NCut 可以改写为：

$$ \underset{(V_1, \ldots, V_k)}{\arg\min}\; \operatorname{Tr}\left( U^T \mathcal{L} U \right) , \tag{4.9} $$

其中 $\mathcal{L} = D^{-1/2} L D^{-1/2}$，$U := D^{1/2} N$，$N$ 由式 (4.7) 定义。

下一步是松弛最小化问题 (4.8) 和 (4.9)，只保留约束 $H^T H = I_K$ 与 $U^T U = I_K$。这些松弛问题的解由下一个命题给出（证明我们参考附录 A.3.3 中的命题 A.15）。

一旦松弛问题得解，我们手头剩下一个 $n \times K$ 矩阵，其各列对应于 $L$（或 $\mathcal{L}$）的前 $K$ 个特征向量。为了把这个实值矩阵重新转换为离散划分，一种标准做法是考虑 $K$ 的 $n$ 行（于是得到 $\mathbb{R}^K$ 中的 $n$ 个数据点），并对这 $n$ 个数据点应用 $k$-means 算法。更确切地说，$k$-means 由以下最小化问题构成

$$ (\widehat{Z}, \widehat{X}) = \underset{\substack{Z \in \mathcal{Z}_{n, K} \\ X \in \mathbb{R}^{K \times K}}}{\arg\min}\; \| Z X - V \|_F^2 \tag{4.10} $$

其中 $\mathcal{Z}_{n, K}$ 表示成员矩阵（membership matrices）的空间，即元素取自 $\{0, 1\}$、且每行 $i$ 只有一个非零元素的 $n \times K$ 矩阵。虽然求解最小化问题 (4.10) 是 NP-hard 的，但存在（见 Kumar et al., 2004）一种多项式时间的程序，可以找到

$$ \begin{array}{rll} & (\widehat{Z}, \widehat{X}) \in \mathcal{Z}_{n, K} \times \mathbb{R}^{K \times K} & \\ \text{s.t.} & \left\| \widehat{Z} \widehat{X} - V \right\|_F^2 \leq (1 + \epsilon) \displaystyle \min_{\substack{Z \in \mathcal{Z}_{n, K} \\ X \in \mathbb{R}^{K \times K}}} \| Z X - V \|_F^2 . & \end{array} \tag{4.11} $$

一旦找到 $\widehat{Z}$，我们就返回预测的簇：若 $\widehat{Z}_{ik} = 1$，则节点 $i$ 属于簇 $k$。我们把它总结在算法 5 中。

4.1.3　半定规划（Semidefinite Programming）

与上一节类似，我们也可以考虑在 $V$ 的所有簇 $V_k$ 大小都等于 $|V|/K$ 的划分 $(V_1, \dots, V_K)$ 上最小化

$$ \operatorname{Cut}(A, V_1, \ldots, V_K) = \sum_{k=1}^{K} \operatorname{Cut}(A, V_k) \tag{4.12} $$

的问题。与上一节的做法类似，我们可以证明，最小化 (4.12) 等价于最大化

$$ \operatorname{Tr}\left( X^T A X \right) \tag{4.13} $$

其中 $X = (x_{ik})$ 是一个 $n \times K$ 矩阵，满足

$$ x_{ik} = \left\{ \begin{array}{ll} 1 & \text{若 } v_i \in V_k , \\ 0 & \text{其他} . \end{array} \right. $$

查看学习笔记对“最小化 (4.12) 等价于最大化 (4.13)”这一步的推导补全

最大化表达式 (4.13) 导出另一种基于邻接矩阵的谱聚类方法：此时寻找的是 $A$ 的与 $K$ 个最大特征值对应的 $K$ 个特征向量。我们还可以提出一种不同的松弛方法。事实上，由关系式

$$ \operatorname{Tr}\left( X^T A X \right) = \operatorname{Tr}\left( A X X^T \right) , \tag{4.14} $$

可知最小化 (4.12) 等价于求解以下优化问题

$$ \begin{array}{rll} \displaystyle \underset{Y \in \{0,1\}^{n \times n}}{\arg\max} & \langle A, Y \rangle & \\ & Y \succeq 0 & \\ & \operatorname{rank}(Y) = K & \\ & Y_{ii} = 1 & \\ & Y 1_n = \frac{n}{K} 1_n & \end{array} \tag{4.15} $$

其中 $\langle A, Y \rangle = \operatorname{Tr}(A Y^T)$ 表示通常的矩阵内积。(4.15) 中的前四个约束强制 $Y$ 具有 $X X^T$ 的形式，而最后一个约束强制各簇大小相同。

优化问题 (4.15) 的一种可能的松弛是以下半定规划（semidefinite programming）

$$ \begin{array}{rll} \displaystyle \underset{Y \in \mathbb{R}^{n \times n}}{\arg\max} & \langle A, Y \rangle . & \\ & Y \succeq 0 & \\ & Y_{ii} \leq 1 & \\ & Y 1_n = \frac{n}{K} 1_n & \end{array} \tag{4.16} $$

4.1.4　讨论（Discussion）

谱聚类的复杂度（Complexity of spectral clustering）

谱方法需要计算特征向量，其最坏情形复杂度为 $O(n^3)$。然而，实践中当处理特征值分离良好的稀疏矩阵时，复杂度可以接近 $O(Kn)$，其中 $K$ 是所需特征向量的个数（见例如 Demmel et al., 2008）。

谱聚类在真实数据集上的性能（Performance of spectral clustering on real data sets）

我们首先在表 4.2 中展示谱聚类的性能，使用的是 scikit-learn Python 库中的实现¹。该实现使用归一化拉普拉斯矩阵（并且在实践中，人们观察到归一化拉普拉斯矩阵优于标准拉普拉斯矩阵）。

我们还在图 4.2 中展示了在 MNIST 数据集上选取两个数字时归一化谱聚类的性能。我们观察到，大多数数字对都被很好地预测，但数字对 (4, 9)、(5, 8) 和 (7, 9) 最难区分，精度分别为 0.53、0.70 和 0.72。这凸显了一个直观的事实：这些数字对中的数字长相相似。

谱方法与悬垂树（Spectral methods and dangling trees）

让我们分析谱聚类在政治博客数据集上的失败。图 4.3 展示了 $\mathcal{L}$ 的与第二小和第三小特征值对应的特征向量分量的取值。我们看到，第二个特征向量的分量集中在少数节点上。而且，这些节点对应于一棵悬垂树（dangling tree），并不对应有意义的社区结构（见图 4.3c）。相反，第三个特征向量的分量对应于正确的社区结构。事实上，用这个特征向量做聚类可以达到 95% 的精度。

图 4.3 表明，对这个数据集而言，适合聚类的特征向量是第三个，而第二个特征向量集中在低度节点附近，形成一棵悬垂树。² 由于这种行为会导致图被划分为一个包含几乎所有节点的大社区和一个只有几个节点的小社区，在实践中很容易识别。为了解决这个问题，一个简单的办法是看更高阶的特征向量。但是，如何确定正确的特征向量呢？事实上，这可能并不总是一件容易的事。首先，正确的特征向量可能处在更低的位置，比如说第 5 或第 7 位，而在带噪声的特征向量中定位它可能并非易事。此外，这一推理难以推广到多于 2 个簇的情形。

正则化技术（regularization technique）旨在解决这个问题。它是对 $\mathcal{L}_\tau := I - D_\tau^{-1/2} A_\tau D_\tau^{-1/2}$ 做谱聚类，其中 $A_\tau := A + \frac{\tau}{n} 1_n 1_n^T$，$D_\tau$ 是相应变换后的度矩阵。矩阵 $A_\tau$ 是初始邻接矩阵 $A$ 的一个扰动版本：我们在所有节点对之间都加上了一条权重为 $\frac{\tau}{n}$ 的边。这倾向于把悬垂树拉回到图的其余部分，从而恢复特征向量中的秩序（Zhang and Rohe, 2018）。此外，Le et al., 2017 证明了伯努利随机图的正则化拉普拉斯矩阵 $\mathcal{L}_\tau$ 比归一化拉普拉斯矩阵 $\mathcal{L}$ 在其期望附近集中得更好（我们在 4.4.4 节进一步展开这一点，特别见定理 4.9）。扰动参数 $\tau$ 通常取 $\tau = 1$ 或 $\tau = \bar{d}$，其中 $\bar{d}$ 是图的平均度。我们在表 4.3 中比较了标准谱聚类与正则化版本的性能。

谱方法与几何数据（Spectral methods and geometric data）

在许多情形中，节点可以带有几何属性（例如在度量空间中的位置）。如 Avrachenkov et al., 2021a 所示，这种几何结构会妨碍基于割的聚类方法。事实上，在这种情况下，Fiedler 向量可能对应于一种几何构型，因而不携带关于潜在社区标记的任何信息。为了避免这一陷阱，Avrachenkov et al., 2021a 提出通过考察更高阶的特征向量来恢复正确的社区成员归属。图 4.4 凸显了这种情形。第二和第四个特征向量给出的是基于节点位置的构型，而恢复节点标签用第 10 个特征向量做得更好。理想特征向量的确切位次则依赖于模型参数，详细分析见 Avrachenkov et al., 2021a。

让我们再展示：在含有几何成分的真实数据集上，更高阶的特征向量也能带来更好的聚类。我们从 MNIST 中选取 1000 张代表数字 4 和 9 的图片，用高斯权重构建一个 $k$ 近邻（$k = 8$）相似图。数字 4 和 9 是最难区分的数字对。我们在图 4.5 中画出谱聚类所得精度随特征向量阶数的变化。我们强调一个事实：与政治博客数据集不同，这并不是悬垂树造成的假象。我们在图 4.6 中画出用该图归一化拉普拉斯矩阵的第二小和第三小特征值对应的特征向量所预测的簇，并与真实的簇比较。我们注意到，预测出的簇大小均衡。我们还注意到，真实标签的 NCut 为 3.8，而用第二个（相应地，第三个）特征向量所做预测对应标签的 NCut 为 2.7（相应地，3.7）。因此，对这个图而言，正确的标签并不对应于最小的归一化割。

4.2　基于模块度的方法（Modularity-based Methods）

在本节中，我们将首先定义一个质量函数，称为模块度（modularity）（最早由 Newman and Girvan, 2004 引入），它旨在把我们的簇分配下的连接密度与图由随机零模型生成时所得到的密度进行比较。通过在所有划分的空间上优化模块度，我们识别出内部连接比随机情形下预期更稠密的节点群体。由于模块度最大化是 NP-hard 的，我们介绍两种常用的近似方法。

4.2.1　定义（Definition）

注 4.1 关于模块度的若干说明

以下几点说明是必要的：

• 我们让社区标记 $z$ 在 $[n]$ 中取值，因此潜在地可以有 $n$ 个社区（于是每个节点都可以单独自成一个社区）。此外，有些社区可以为空。

• 图 4.7 展示了一个玩具图上若干划分的模块度。特别地，我们观察到，在这个玩具图中，“明显的”社区结构对应于最大的模块度（图 4.7(a)），而偏离这一划分会得到较小的模块度（图 4.7(b)）。此外：
  • 若 $z = 1_n$（即划分 $z$ 把所有节点分在同一个组中），则 $\mathcal{M}(z) = 0$（图 4.7(c)）；
  • 若划分 $z$ 把每个节点都单独分在自己的社区中（即 $z = (1, 2, \cdots, n)$），则 $\mathcal{M}(z) \leq 0$（图 4.7(d)）。
  这两个简单的事实对任何图都成立，并且容易建立。
• 因子 $1 / (2|E|)$ 是归一化因子。特别地，证明对任何图和任何节点标记向量 $z$ 都有 $-1 \leq \mathcal{M}(z) \leq 1$ 是直接的（straightforward）³。

查看学习笔记对“$-1 \leq \mathcal{M}(z) \leq 1$ 是直接的”及脚注 3 中 $-\tfrac{1}{2}$ 下界的证明补全

• $P_{ij}$ 是当图由配置模型（configuration model）生成时节点 $i$ 与 $j$ 之间边数的期望。事实上，节点 $i$ 有 $d_i$ 条向外伸出的边，而其中一条边连到节点 $j$ 的概率是 $d_j / (2|E|)$，其中 $|E|$ 是网络中的总边数。在 4.4.1 节中，我们将通过把模块度与一个 SBM 的 MAP 估计量相联系，进一步论证这一选择。
• 在实践中，模块度的好取值通常位于 0.3 与 0.7 之间。若干带真值社区的网络的模块度取值见表 4.4。
• 不幸的是，优化模块度是 NP-complete 的（Brandes et al., 2007）。

模块度的高效计算（Efficient computation of modularity）

以下引理给出了计算模块度和更新模块度的公式，它们对下一节介绍的算法很有用。对社区标记 $z \in [n]^n$，我们把从社区 $k$ 指向社区 $\ell$ 的边所占的比例定义为

$$ e_{k\ell}(z) = \frac{1}{2|E|} \sum_{i, j} A_{ij} \mathbf{1}(z_i = k) \mathbf{1}(z_j = \ell) , $$

并把社区 $k$ 的质量（mass）$m_k$ 定义为社区 $k$ 中节点的度之和除以所有节点度之和：

$$ m_k(z) = \frac{1}{2|E|} \sum_{i=1}^{n} d_i\, \mathbf{1}\left( z_i = k \right) . $$

4.2.2　贪心算法（Greedy Algorithm）

第一个模块度最大化算法由 Newman, 2004 提出，此处重录（算法 6）：只要合并能增大划分的模块度，就迭代地把成对的社区合并起来。一些扩展已被提出（例如见 Clauset et al., 2004），但它们都已被 Louvain 算法超越（4.2.3 小节）。

4.2.3　Louvain 算法（Louvain Algorithm）

算法 7 给出的是 Blondel et al., 2008 发明的 Louvain 算法。该方法之所以叫 Louvain，是因为原论文的作者们当时在比利时的 Louvain 大学工作。

4.2.4　讨论（Discussion）

与谱方法不同，基于模块度的方法不需要预先知道块数。此外，实践中观察到的速度差异使贪心方法（算法 6）失去了竞争力。再者，人们还在经验上观察到 Louvain 返回的划分具有高模块度。表 4.4 给出了 Louvain 方法在真实数据集上的性能。特别地，我们看到 Louvain 倾向于预测出较多的社区个数，但模块度高于真值划分。

我们在图 4.8 和图 4.9 中分别画出 Louvain 在空手道俱乐部数据集和政治博客数据集上预测的社区。与真值比较，我们观察到 Louvain 把真值社区分裂成了更小的社区。这得到的构型具有比真值更大的模块度（见表 4.4），而把 Louvain 预测的小社区合并成更大的社区，几乎可以完美地恢复真值。

4.3　贝叶斯社区检测（Bayesian Community Detection）

4.3.1　过拟合问题？（An Over-fitting Issue?）

对任何模块度最大化算法的结果都应当谨慎解读。事实上，在没有任何社区结构的随机图模型上也能找到高模块度的划分。图 4.10 展示了 Louvain 算法在 Erdős–Rényi、配置模型和优先连接（preferential attachment）随机图上的输出（包括预测划分的模块度和预测的簇数）。所得到的模块度很高，尤其是在 Erdős–Rényi 与优先连接随机图上，尽管这些图按构造并没有社区结构！此外，在配置模型——本应是模块度的零模型——上也能找到高模块度的划分。我们强调，这是模块度最大化的内在问题，而不是 Louvain 算法的副作用。

基于割的方法同样容易过拟合。图 4.11 表明，在 Erdős–Rényi 随机图上使用归一化谱聚类，所得划分的割占全部边数的 15% 到 30%（取决于所选的簇数）。换句话说，谱聚类在纯随机之中也找到了社区！

4.3.2　有理论依据的方法（Principled Approach）

为了避免过拟合问题、并在网络中找到统计上显著的社区，我们现在探索一种贝叶斯方法。贝叶斯社区检测旨在通过最大化后验分布（posterior distribution）$\mathbb{P}(z \,|\, A)$，确定是哪一个社区标记 $z \in [n]^n$ 生成了网络 $A$。贝叶斯公式给出

$$ \mathbb{P}(z \,|\, A) = \frac{\mathbb{P}(A \,|\, z)\, \mathbb{P}(z)}{\mathbb{P}(A)} . $$

分母中的量 $\mathbb{P}(A)$ 是证据（evidence），即观测数据的概率，它不依赖于 $z$。

量 $\mathbb{P}(A \mid z)$ 是边际似然（marginal likelihood）。我们将假设网络是按照同质 DC-SBM 的 Poisson 版本生成的（见 2.3.2 节）。因此，$\mathbb{P}(A \mid z)$ 等于

$$ \int \mathbb{P}(A \,|\, z, \omega, \theta)\, \mathbb{P}(\omega \,|\, z)\, \mathbb{P}(\theta \,|\, z)\, d\omega\, d\theta . \tag{4.18} $$

特别地，$\mathbb{P}(A \,|\, z, \omega, \theta)$ 等于⁴（见命题 2.8）

$$ \prod_{1 \leq k \leq K} \omega_{kk}^{m_{kk}}\, \mathrm{e}^{-\frac{n_k^2}{2} \omega_{kk}} \prod_{1 \leq k < \ell \leq K} \omega_{k\ell}^{m_{k\ell}}\, \mathrm{e}^{-n_k n_\ell \omega_{k\ell}} \prod_{i} \theta_i^{d_i} , $$

其中 $m_{k\ell} = \sum_{i < j} A_{ij} \mathbf{1}(z_i = k) \mathbf{1}(z_j = \ell)$。我们为 $\theta$ 选取一个均匀先验，它对所有 $k$ 施加归一化条件 $\sum_i \theta_i \mathbf{1}(z_i = k) = n_k$。因此

$$ \mathbb{P}(\theta \,|\, z) = \prod_{k} (n_k - 1)!\; \delta\left( \sum_{i} \theta_i \mathbf{1}(z_i = k) - n_k \right) . $$

最后，我们回忆：对取值于 $[0, \infty)$、均值被约束为 $\bar{x}$ 的连续随机变量 $X$，最大熵分布是密度为 $f(x) = \mathrm{e}^{-x/\bar{x}} / \bar{x}$ 的指数分布。于是，我们为 $\omega_{k\ell}$ 选取指数先验，使得

$$ \mathbb{P}(\omega_{k\ell} \,|\, z) = \frac{\mathrm{e}^{-\omega_{k\ell} / \bar{\omega}}}{\bar{\omega}} , $$

其中 $\bar{\omega} = 2|E|/n^2$ 对应于网络中的平均连边概率。计算式 (4.18) 中关于 $\omega$ 的积分，得到

$$ \int \prod_{k} \frac{m_{kk}!}{\bar{\omega} \left( \frac{1}{\bar{\omega}} + \frac{n_k^2}{2} \right)^{m_{kk} + 1}} \prod_{k < \ell} \frac{m_{k\ell}!}{\bar{\omega} \left( \frac{1}{\bar{\omega}} + n_k n_\ell \right)^{m_{k\ell} + 1}} \prod_{i} \theta_i^{d_i}\, \mathbb{P}(\theta \,|\, z)\, d\theta , $$

其中我们用到了 $\int_0^\infty \mathrm{e}^{-ax} x^b\, dx = \frac{b!}{a^{b+1}}$（$a, b > 0$）。

为了完成最后关于 $\theta$ 的积分，我们注意到对所有 $k$，

$$ \prod_{i \in \mathcal{C}_k} \int \theta_i^{d_i}\, \delta\left( \sum_{i \in \mathcal{C}_k} \theta_i - n_k \right) d\theta_i = \frac{\prod_{i \in \mathcal{C}_k} d_i!}{\left( \sum_{i \in \mathcal{C}_k} d_i + 1 \right)!} $$

其中 $\mathcal{C}_k = \{i : z_i = k\}$。因此 $\mathbb{P}(A \mid z)$ 等于

$$ \begin{gathered} \prod_{k} \frac{m_{kk}!}{\left( 1 + \bar{\omega} \frac{n_k^2}{2} \right)^{m_{kk} + 1}} \prod_{k < \ell} \frac{m_{k\ell}!}{\left( 1 + \bar{\omega} n_k n_\ell \right)^{m_{k\ell} + 1}} \\ \prod_{k} n_k^{v_k + 1}\, \frac{(n_k - 1)!}{(n_k + v_k - 1)!}\, \frac{\bar{\omega}^{|E|} \prod_{i} d_i!}{\prod_{i < j} A_{ij}!} \end{gathered} $$

其中 $v_k = \sum_i d_i \mathbf{1}(z_i = k)$ 是块 $k$ 中节点的度之和。

现在我们来研究先验分布 $\mathbb{P}(z)$。特别地，先验的选择不应对（非空）组的个数、也不应对各组中的节点数作任何先验假设（允许大小不同的组）。令

$$ \mathbb{P}(z) = \mathbb{P}\left( z \mid \{n_k\} \right) \mathbb{P}\left( \{n_k\} \mid K \right) \mathbb{P}(K) $$

其中 $K$ 表示 $z$ 中非空组的个数，$n_k$ 表示社区 $k$ 中的节点数。我们首先有 $\mathbb{P}(K) = \frac{1}{n}$（先验对块数不作偏好）。然后，回忆 $\binom{n-1}{K-1}$ 计数的是把 $n$ 个非零计数分进 $K$ 个非空格子中的方式数，因此 $K$ 个块的大小为 $n_1, \ldots, n_K$ 的概率是 $\mathbb{P}(\{n_k\} \,|\, K) = \frac{1}{\binom{n-1}{K-1}}$。最后，给定随机抽取的块大小 $\{n_k\}$，划分以均匀概率 $\mathbb{P}(z \mid \{n_k\}) = \frac{\prod_r n_r!}{n!} \frac{1}{n}$ 抽取。因此，

$$ \mathbb{P}(z) = \frac{\prod_k n_k!}{n!} \cdot \frac{1}{\binom{n-1}{K-1}} \cdot \frac{1}{n} . $$

使用边际似然与先验的表达式，导出在所有可能的社区标记 $z \in [n]^n$ 上最大化

$$ \frac{1}{\binom{n-1}{K-1}} \prod_{k} \frac{m_{kk}!}{\left( 1 + \bar{\omega} \frac{n_k^2}{2} \right)^{m_{kk} + 1}}\, \frac{n_k^{v_k} (n_k!)^2}{(n_k + v_k - 1)!} \prod_{k < \ell} \frac{m_{k\ell}!}{\left( 1 + \bar{\omega} n_k n_\ell \right)^{m_{k\ell} + 1}} $$

4.3.3　马尔可夫链蒙特卡罗算法（Markov Chain Monte Carlo Algorithm）

虽然上述基于似然的最大化问题是困难的，但我们可以采用马尔可夫链蒙特卡罗（Markov Chain Monte Carlo，MCMC）重要性采样方法来寻找一个好的近似解（Robert and Casella, 2013）。我们从某个初始标记 $z^{(0)}$ 出发。在每一步，我们提出对标记 $z^{(t)}$ 的一个修改 $z'$。这个修改以概率 $\min\left\{1,\, \frac{\mathbb{P}(z' \,|\, A)}{\mathbb{P}(z \,|\, A)} \frac{\mathbb{P}(z \,|\, z')}{\mathbb{P}(z' \,|\, z)}\right\}$ 被接受。若移动被接受，则 $z^{(t+1)} = z'$，否则 $z^{(t+1)} = z^{(t)}$。这个接受概率称为 Metropolis–Hastings 准则（Metropolis-Hastings criterion），它保证了细致平衡（detailed balance）（Metropolis et al., 1953; Hastings, 1970a）。利用前面的计算，计算 $\frac{\mathbb{P}(z' \,|\, A)}{\mathbb{P}(z \,|\, A)}$ 的时间复杂度为 $O(d_i)$（特别地，我们不需要计算证据 $\mathbb{P}(A)$，因为它会约掉）。

最简单的移动提议是均匀随机地选取一个节点，并在 $K + 1$ 个选择（$K$ 个现有的组，加上把 $i$ 分到一个空组的可能性）中选取它的新社区归属 $z_i'$。这种直接的做法效率低下，因为马尔可夫链的混合时间可能非常长。一种更好的做法（Peixoto, 2014a, 2019）是按照

$$ \mathbb{P}(z_i' = \ell \,|\, z) = \sum_{k} \mathbb{P}(k \,|\, i)\, \frac{e_{k\ell} + \epsilon}{e_k + \epsilon (K + 1)} $$

选取新的组归属 $z_i'$，其中 $\mathbb{P}(k \mid i) = \sum_j \frac{A_{ij} \mathbf{1}(z_j = k)}{d_i}$ 是 $i$ 的邻居中属于组 $k$ 的比例，$\epsilon > 0$ 是保证遍历性的参数。我们可以这样解读这个概率：首先均匀随机地选取一个节点 $i$，并采样 $i$ 的一个邻居 $j$，其社区标签为 $z_j^{(t)} = k$。然后，

• (i) 以概率 $\frac{\epsilon}{e_k + \epsilon(K+1)}$，在 $K + 1$ 种可能中随机选取一个社区标签 $\ell$（它可以是一个空组）；
• (ii) 否则，以概率 $\frac{e_{k\ell}}{e_k + \epsilon(K+1)}$ 采样一个组标签 $\ell$。

只要我们记录每个组关联的边，这一过程就可以在 $O(d_i)$ 的时间复杂度内完成，其代价是 $O(|E|)$ 的存储复杂度。

4.3.4　数值结果（Numerical Results）

本节介绍的 MCMC 算法在 graph-tool 库（Peixoto, 2014b）中实现，见 http://graph-tool.skewed.de。

我们首先分析贝叶斯聚类在合成网络上的性能。我们生成 DC-SBM 图。

贝叶斯框架的 MCMC 程序给出的是后验分布，而不仅仅是找到它的最大值。特别地，我们可以得到网络中各节点组归属的边际概率，以及组数的边际概率。特别地，我们在图 4.12 中画出了在空手道俱乐部网络上得到的结果。特别地，我们在图 4.12(a) 中观察到：网络具有一个或两个社区的概率很大，而社区数更多的构型可能性小得多。回忆真值对应的是总教练与俱乐部主席之间争执之后的情形，我们可以把单社区情形上的大后验解释为争执之前的网络——当时并不存在社区。当贝叶斯聚类预测出两个社区时，我们观察到不同的构型。有些预测确实与争执后观察到的两个社区对齐（见图 4.12(b)），而另一些构型则倾向于把度大的节点——“影响者”——聚到一起，把度小的节点——“跟随者”——聚成第二个社区（见图 4.12(c)）。

最后，我们在图 4.13 中展示：把贝叶斯聚类应用于没有社区结构的随机图模型时，它在绝大多数情形下只预测出一个社区——过拟合问题不复存在了。

4.4　理论分析（Theoretical Analysis）

4.4.1　模块度与最大后验估计量（Modularity and Maximum A Posteriori Estimator）

在本节中，我们考虑从同质度校正分块模型中采样的随机图 $G$ 的邻接矩阵 $A$，其中边服从 Poisson 分布（见 2.3.2 节）。更确切地说，$A_{ii} = 0$，且对 $i \neq j$，

$$ A_{ij} = A_{ji} \sim \left\{ \begin{array}{ll} \mathcal{P}(\theta_i \theta_j \omega_{\mathrm{in}}) , & \text{若 } z_i^0 = z_j^0 , \\ \mathcal{P}(\theta_i \theta_j \omega_{\mathrm{out}}) , & \text{其他} , \end{array} \right. \tag{4.19} $$

其中 $\mathcal{P}(\omega)$ 表示参数为 $\omega$ 的 Poisson 随机变量，$d_i$ 是节点 $i$ 的度。与 DC-SBM 类似，我们假设对所有 $k \in [K]$ 都有 $\sum_i \theta_i \mathbf{1}(z_i^0 = k) = 1$。命题 4.4 表明，对这样的分块模型，由下式定义的最大后验（Maximum A Posteriori，MAP）估计量

$$ \hat{z}^{\mathrm{MAP}} = \underset{z \in [K]^n}{\operatorname{arg\,max}}\; \mathbb{P}(z \,|\, A) \tag{4.20} $$

对应于最大化一个与模块度相似的量。

回忆模块度由式 (4.17) 定义为

$$ \mathcal{M}(z) = \frac{1}{2|E|} \sum_{i, j} \left( A_{ij} - P_{ij} \right) \mathbf{1}(z_i = z_j) , $$

其中 $P_{ij}$ 是零模型下 $i$ 与 $j$ 之间连边的概率，而所选的零模型是配置模型。命题 4.4 给出了类似的东西。事实上，我们可以写出

$$ \hat{z}^{\mathrm{MAP}} = \underset{z}{\arg\max}\; \sum_{i, j} \left( A_{ij} - \gamma\, P_{ij} \right) \mathbf{1}(z_i = z_j) , $$

其中 $\gamma = \dfrac{\omega_{\mathrm{in}} - \omega_{\mathrm{out}}}{\log \frac{\omega_{\mathrm{in}}}{\omega_{\mathrm{out}}}}\, \dfrac{K}{\omega_{\mathrm{in}} + (K-1)\,\omega_{\mathrm{out}}}$，而 $P_{ij} = \theta_i \theta_j\, \dfrac{\omega_{\mathrm{in}} + (K-1)\,\omega_{\mathrm{out}}}{K}$ 对应于零模型下（见定义 (4.19)）观测到 $i$ 与 $j$ 之间连边的期望概率。此外，节点 $i$ 的期望度等于 $\bar{d}_i = \sum_{j=1}^{n} \theta_i \theta_j \lambda_{ij} = \theta_i\, \dfrac{\omega_{\mathrm{in}} + (K-1)\,\omega_{\mathrm{out}}}{K}$，而期望边数等于 $\bar{m} = \frac{1}{2}\, \dfrac{\omega_{\mathrm{in}} + (K-1)\,\omega_{\mathrm{out}}}{K}$。因此 $P_{ij} = \dfrac{\bar{d}_i \bar{d}_j}{2\bar{m}}$，于是我们恢复了

$$ \hat{z}^{\mathrm{MAP}} = \underset{z \in [K]^n}{\arg\max}\; \sum_{i, j} \left( A_{ij} - \gamma\, \frac{\bar{d}_i \bar{d}_j}{2\bar{m}} \right) \mathbf{1}\left( z_i = z_j \right) . $$

$\arg\max$ 内部的量与 (4.17) 中定义的模块度相似，只是多了一个参数 $\gamma$。可以如下定义正则化模块度（regularised modularity）（Reichardt and Bornholdt, 2006; Arenas et al., 2008）：

$$ \mathcal{M}_\gamma(z) = \sum_{i, j} \left( A_{ij} - \gamma P_{ij} \right) , \tag{4.21} $$

其中 $P_{ij}$ 通常取为 $\frac{d_i d_j}{2m}$。

因此，MAP 估计量等价于广义模块度的最大化，其中 $P_{ij} = \frac{\bar{d}_i \bar{d}_j}{2\bar{m}}$，$\gamma$ 如前所定义。不幸的是，这一等价关系的实用价值相当有限，因为参数 $\omega_{\mathrm{in}}, \omega_{\mathrm{out}}$（因而 $\gamma$）通常是未知的，尽管人们已提出多种估计它们的策略（更多内容见 Newman, 2016）。

4.4.2　归一化谱聚类作为模块度最大化的连续松弛（Normalized Spectral Clustering as a Continuous Relaxation of Modularity Maximisation）

本小节的目标是把模块度最大化的一个特定松弛与归一化谱聚类联系起来。为简化推导，我们只考虑两个簇的情形。回忆广义模块度的最大化由下式给出

$$ \hat{z} = \underset{z \in \{-1, 1\}^n}{\arg\max}\; \sum_{i, j} \left( A_{ij} - \gamma \frac{d_i d_j}{2|E|} \right) \mathbf{1}(z_i = z_j) . $$

注意到 $\mathbf{1}(z_i = z_j) = \frac{1}{2} \left( z_i z_j + 1 \right)$，我们可以把它改写为

$$ \hat{z} = \underset{z \in \{-1, 1\}^n}{\arg\max}\; \sum_{i, j} B_{ij} z_i z_j , $$

其中 $B$ 是元素为 $B_{ij} = A_{ij} - \gamma \frac{d_i d_j}{2|E|}$ 的矩阵。正如对基于割的方法所做的那样（4.1 节），我们可以通过把 $z \in \{-1, 1\}^n$ 的离散性松弛为实值向量 $x \in \mathbb{R}^n$ 来简化问题（Newman, 2013）。然而，需要加上一个约束，以防止 $x_i$ 变得任意大，即防止项 $\left( A_{ij} - \gamma \frac{d_i d_j}{2|E|} \right) x_i x_j$ 以平凡的方式变大。一个直接的约束是通过施加 $\sum_i x_i^2 = n$ 把 $x$ 固定在超球面上。特别地，这把各分量限制在 $-\sqrt{n} \leq x_i \leq \sqrt{n}$，同时把 $x$ 的 $\ell^2$-范数固定为 $n$。更一般地，可以通过令 $\sum_i \kappa_i x_i^2 = \sum_i \kappa_i$（$\kappa = (\kappa_1, \ldots, \kappa_n)$ 为分量非负的向量）把 $x$ 固定在一个超椭球面上。特别地，取 $\kappa_i = d_i$ 导出以下问题

$$ \hat{x} = \underset{\substack{x \in \mathbb{R}^n \\ x^T D x = 2|E|}}{\arg\max}\; x^T B x , $$

其中我们用到了 $x^T B x = \sum_{i, j} B_{ij} x_i x_j$。

与上述问题相关的拉格朗日函数是

$$ x^T B x - \lambda \left( x^T D x - 2|E| \right) , $$

令其关于 $x$ 的导数为零，得到

$$ B x = \lambda D x . \tag{4.22} $$

因此 $x$ 是与特征值 $\lambda$ 对应的广义特征向量方程的一个解。为了知道应考虑哪个 $\lambda$ 值，我们注意到：对广义特征向量 $x$，有 $x^T B x = \lambda x^T D x = \lambda \cdot 2|E|$，因此模块度 $x^T B x$ 在广义特征问题 (4.22) 的最大特征值 $\lambda$ 处取到最高值。

由于 $B 1_n = (1 - \gamma) D 1_n$，$\lambda = 1 - \gamma$ 是 (4.22) 的一个可接受的解。因此，如果最大特征值是 $1 - \gamma$，那么最好的划分对应于完全不切分网络。我们排除这种情形，因此假设 $\lambda > 1 - \gamma$。注意到 $B x = A x - \gamma D 1_n \frac{d^T x}{2|E|}$，其中 $d = (d_1, \ldots, d_n)$，我们把问题 (4.22) 改写为

$$ A x = D \left( \lambda x + \gamma\, 1_n \frac{d^T x}{2|E|} \right) . $$

左乘 $1^T$ 给出 $d^T x = (\lambda + \gamma)\, d^T x = 0$（我们用到了 $1^T A = 1^T D = d^T$ 以及 $d^T 1 = 2|E|$）。由于 $\lambda > 1 - \gamma$，这反过来蕴含 $d^T x = 0$，于是问题 (4.22) 化简为

$$ A x = \lambda D x . $$

我们注意到常数向量 $x = 1_n$ 是一个解，并且根据 Perron–Frobenius 定理，由于它的所有元素都为正，它与最大特征值对应。尽管如此，我们排除这个解，因为它不满足 $d^T x = 0$，于是我们考虑第二大特征值 $\lambda$。用 $y = D^{1/2} x$ 作变量代换，导出标准特征值问题

$$ D^{-1/2} A D^{-1/2} y = \lambda y , $$

或者等价地，

$$ \mathcal{L} y = (1 - \lambda)\, y $$

其中用到归一化拉普拉斯矩阵 $\mathcal{L} = I_n - D^{-1/2} A D^{-1/2}$。因此，$y$ 是归一化拉普拉斯矩阵的一个特征向量。与归一化谱聚类的联系由以下观察完成：$\lambda$ 应是第二大特征值，因此 $1 - \lambda$ 应是 $\mathcal{L}$ 的第二小特征值。

4.4.3　SBM 中一致恢复的信息论结果（Information-theoretic Results for Consistent Recovery in SBMs）

本节介绍关于 SBM 中恢复一致性的信息论结果。

非二值 SBM（Non-binary SBMs）

让我们首先把 SBM 推广到具有非二值相互作用的网络。我们用 $\mathcal{S}$ 表示相互作用的空间，用 $f_{\mathrm{in}}$ 与 $f_{\mathrm{out}}$ 表示相互作用密度（关于某个测度 $\mu$）。这些参数在观测空间

$$ \mathcal{A} = \left\{ A = (a_{ij}) \in \mathcal{S}^{n \times n} \; \text{使得对所有 } i, j \text{ 都有 } a_{ij} = a_{ji},\; a_{ii} = 0 \right\} $$

上指定了一个概率测度，其关于参考测度 $\mu$ 的 $\frac{n(n-1)}{2}$ 重乘积测度的概率密度函数为

$$ \mathbb{P}(A \,|\, z) = \prod_{1 \leq i < j \leq n} f_{z_i z_j}\left( a_{ij} \right) \tag{4.23} $$

换句话说，对按 (4.23) 分布的观测 $A$，各元素 $a_{ij}$（$1 \leq i < j \leq n$）相互独立，并且当 $z_i = z_j$ 时 $a_{ij}$ 按 $f_{\mathrm{in}}$ 分布，否则按 $f_{\mathrm{out}}$ 分布。特别地，当 $\mathcal{S} = \{0, 1\}$ 且 $f_{\mathrm{in}}, f_{\mathrm{out}}$ 为伯努利分布时，我们回到 2.3.1 节定义的二值同质 SBM。当 $\mathcal{S} = \mathbb{Z}$ 且 $f_{\mathrm{in}}, f_{\mathrm{out}}$ 为 Poisson 分布时，我们回到 Poisson SBM（见式 (2.7)）。

表示块成员结构的节点标记 $z$ 是待估计的未知参数。我们把节点标记看作一个随机变量，它在参数空间 $\mathcal{Z} = \{z \in [K]^n\}$ 上服从均匀分布 $\pi(z) = K^{-n}$。在这种情形下，节点标记与观测数据的联合分布由 $\mathcal{Z} \times \mathcal{X}$ 上关于 $\mathrm{card}_{\mathcal{Z}} \times \mu$ 的概率密度

$$ \mathbb{P}(z, A) = \pi(z)\, \mathbb{P}(A \,|\, z) \tag{4.24} $$

刻画，其中 $\mathrm{card}_{\mathcal{Z}}$ 是 $\mathcal{Z}$ 上的计数测度。

渐近恢复的层级（Regime of asymptotic recovery）

我们回忆，两个序列 $y, z \in [K]^n$ 之间的汉明距离（Hamming distance）定义为对应符号不同的位置个数，即

$$ d_{\mathrm{Ham}}(y, z) = \sum_{i=1}^{n} \mathbf{1}(y_i \neq z_i) . $$

对节点标记 $z \in [K]^n$ 的一个估计量 $\hat{z}$，我们如下定义绝对分类误差（absolute classification error）：

$$ d_{\mathrm{Ham}}^{*}\left( \hat{z}, z \right) = \min_{\tau \in \mathcal{S}_K} \sum_{i=1}^{n} \mathbf{1}\left( \tau \circ \left( \hat{z}_i \right) \neq z_i \right) . \tag{4.25} $$

这对应于估计量 $\hat{z}$ 在相差一个全局置换⁵ $\tau \in \mathcal{S}_K$ 的意义下误分类的节点数。

在分析一个估计量的平均性能时，我们可以把 $\hat{z} : A \in \mathcal{A} \mapsto \hat{z}(A) \in [K]^n$ 看作定义在观测集 $\mathcal{A}$ 上、取值于 $[K]^n$ 的随机变量。于是，$\mathbb{E}_z\, d_{\mathrm{Ham}}^{*}(\hat{z}, z)$ 等于给定真实节点标记 $z$ 时的期望聚类误差，而

$$ \mathbb{E}\, d_{\mathrm{Ham}}^{*}(\hat{z}) = \sum_{z \in [K]^n} \pi(z)\, \mathbb{E}_z\, d_{\mathrm{Ham}}^{*}\left( \hat{z}, z \right) $$

是关于参数空间上节点标记分布 $\pi$ 的平均聚类误差。

我们说估计量 $\hat{z}$ 渐近地达到精确恢复（exact recovery），或等价地说 $\hat{z}$ 是 $z$ 的强一致估计量（strongly consistent estimator），如果

$$ \mathbb{E}\, d_{\mathrm{Ham}}^{*}\left( \hat{z} \right) \to 0 \quad \text{当} \quad n \to \infty . \tag{4.26} $$

条件 (4.26) 意味着渐近地每个节点都被正确分类。这一要求常常过于苛刻。更合理的设定是只有占比趋于零的节点被误分类（即至多有 $o(n)$ 个节点被误分类）。我们说估计量 $\hat{z}$ 渐近地达到几乎精确恢复（almost exact recovery）（或称 $\hat{z}$ 是一致估计量（consistent estimator）），如果

$$ n^{-1}\, \mathbb{E}\, d_{\mathrm{Ham}}^{*}\left( \hat{z} \right) \to 0 \quad \text{当} \quad n \to \infty . $$

一致恢复的信息论条件（Information-theoretic conditions for consistent recovery）

在下文中，我们假设 $\mathcal{S}$ 上的一个 $\sigma$-有限参考测度 $\mu$ 一经取定不再更改，并把 $\frac{df}{d\mu}, \frac{dg}{d\mu}$ 简写为 $f, g$，同时在积分号中省略 $d\mu$，于是 $D_{1/2}(f, g) = -2 \log \int \sqrt{fg}$。当 $\mathcal{S}$ 可数时，$\mu$ 总取为计数测度，此时我们写作 $D_{1/2}(f, g) = -2 \log \sum_{x \in \mathcal{S}} \sqrt{f(x) g(x)}$。

定理 4.6 表明，Rényi 散度支配着非二值 SBM 中（强）一致恢复的可能性与不可能性。事实上，当相互作用分布 $f_{\mathrm{in}}$ 与 $f_{\mathrm{out}}$ 过于相似（即它们的 Rényi 散度小于 $n^{-1}$）时，网络提供的信息不足以一致地恢复社区。

定理 4.6 在 Avrachenkov et al., 2022 中证明。关于 SBM 一致性阈值的文献很多，二值 SBM（$\mathcal{S} = \{0, 1\}$）可参阅 Zhang et al., 2016，加权（$\mathcal{S} = \mathbb{R}$）或边带标签（$\mathcal{S} = \{0, 1, \cdots, L\}$）的 SBM 可参阅 Jog and Loh, 2015; Xu et al., 2020。

在二值 SBM 上的应用（Application to binary SBMs）

让我们看看如何把定理 4.6 应用于稀疏二值 SBM，此时 $f_{\mathrm{in}} = \mathrm{Ber}(p_{\mathrm{in}})$、$f_{\mathrm{out}} = \mathrm{Ber}(p_{\mathrm{out}})$，且 $p_{\mathrm{in}}, p_{\mathrm{out}} \ll 1$。Taylor 展开给出

$$ \begin{aligned} D_{1/2}(f_{\mathrm{in}}, f_{\mathrm{out}}) &= -2 \log \left( \sqrt{(1 - p_{\mathrm{in}})(1 - p_{\mathrm{out}})} + \sqrt{p_{\mathrm{in}} p_{\mathrm{out}}} \right) \\ &= -2 \log \left( 1 - \frac{p_{\mathrm{in}} + p_{\mathrm{out}}}{2} + \sqrt{p_{\mathrm{in}} p_{\mathrm{out}}} + O(p_{\mathrm{in}} p_{\mathrm{out}}) \right) \\ &= -2 \log \left( 1 - \frac{\left( \sqrt{p_{\mathrm{in}}} - \sqrt{p_{\mathrm{out}}} \right)^2}{2} + O(p_{\mathrm{in}} p_{\mathrm{out}}) \right) \\ &= \left( \sqrt{p_{\mathrm{in}}} - \sqrt{p_{\mathrm{out}}} \right)^2 + O(p_{\mathrm{in}} p_{\mathrm{out}}) . \end{aligned} \tag{4.27} $$

这可以应用于以下两个特例。

查看学习笔记对脚注 6“孤立节点无法优于随机猜测”论证的形式化

非二值 SBM 的其他特例（Other Particular Cases of Non-binary SBMs）

4.4.4　SBM 中谱方法的一致性（Consistency of Spectral Methods in SBM）

在本节中，我们将证明谱聚类在 SBM 中是一致的。为简单起见，我们考虑使用图的邻接矩阵的谱聚类，但如果使用归一化拉普拉斯矩阵，类似的证明同样成立。

启发式：平均场模型（Heuristic: mean-field model）

我们首先考虑 SBM 的平均场模型（mean-field model），即把所有随机量都替换为其期望的模型。特别地，平均场图变成由 SBM 图的期望邻接矩阵构成的加权图。因此，如果 $(z, G)$ 抽取自 $\mathrm{SBM}(n, \pi, Q)$，那么相应平均场的邻接矩阵是

$$ \mathbb{E} A = Z Q Z^T , $$

其中 $Q \in [0, 1]^{K \times K}$ 是速率矩阵（回忆元素 $Q_{k\ell}$ 表示社区 $k$ 中一个节点与社区 $\ell$ 中一个节点之间出现边的概率），$Z \in \{0, 1\}^{n \times K}$ 是由下式定义的成员矩阵（membership matrix）

$$ Z_{ik} = \left\{ \begin{array}{ll} 1 , & \text{若 } z_i = k , \\ 0 , & \text{其他} . \end{array} \right. $$

以下引理刻画了 $\mathbb{E} A$ 的特征结构。

特别地，引理 4.7 保证了社区信息被编码在 $\mathbb{E} A$ 的特征结构中。事实上，$\mathbb{E} A$ 的与非零特征值对应的 $K$ 个特征向量由 $U$ 的各列给出，而 $U$ 可以写成 $ZX$。$k$-means 步骤（见式 (4.10)）随后旨在从 $U$ 中恢复 $Z$（以及 $X$）。

SBM 中谱聚类的一致性（Consistency of spectral clustering in SBM）

我们已经确立：如果观测到的是平均场图，那么通过考察平均场邻接矩阵 $\mathbb{E} A$ 的前 $K$ 个主特征向量，恢复社区是可能的。下面的定理表明，在一些自然的条件下，通过考察随机图邻接矩阵 $A$ 的前 $K$ 个主特征向量，一致恢复是可能的。我们回忆，绝对分类误差 $d_{\mathrm{Ham}}^{*}(\hat{z}, z)$ 在 (4.25) 中定义，一个估计量是一致的，如果 $\frac{d_{\mathrm{Ham}}^{*}(\hat{z}, z)}{n} = o(1)$。

定理 4.8 证明的直觉如下。

• 证明邻接矩阵 $A$ 的前 $K$ 个主特征向量与期望邻接矩阵 $\mathbb{E} A$ 的前 $K$ 个主特征向量相差不大。这分两步完成。
• 首先用随机矩阵理论的一个结果证明 $A$ 集中在 $\mathbb{E} A$ 附近。这就是定理 4.9。
• 然后用这个集中性证明特征向量也是集中的。这通常用 Davis–Kahan 定理完成。我们在引理 4.10 中给出它的一个变体。
• 最后通过界定 $k$-means 步骤产生的误差收尾。

定理 4.9 的证明很复杂，超出本书的范围。我们只指出：当 $d_n$ 很小时，正则化项 $\tau 1_n 1_n^T$ 是保证邻接矩阵集中所必需的。事实上，令 $p_{ij} = p$，考虑一个 Erdős–Rényi 图。如果 $d_n \ll \log n$，那么某些节点的度会远大于期望度 $d_n = np$。这意味着邻接矩阵某些行的 $\ell^2$ 范数远大于 $d_n$，这反过来蕴含 $\|A - \mathbb{E}A\| \gg \sqrt{d_n}$。

引理 4.10 是 Davis–Kahan “$\sin\theta$” 定理的一个版本，它界定了由两个矩阵的主特征向量张成的两个子空间之间的距离。进一步的解释我们参考 Yu et al., 2015 的定理 2。

定理 4.8 证明所需的最后一个要素是对 $k$-means 步骤产生的误差的界。下一个引理给出这样一个界。

引理 4.11 上界了 $k$-means 步骤产生的误差。该界涉及 $\bar{V}$（以 $\mathbb{E}A$ 的特征向量为列的矩阵；由平均场研究引理 4.7 可知它能写成 $ZX$，并从中可以恢复社区结构 $Z$）与矩阵 $V$（以 $A$ 的特征向量为列的矩阵）之间的 Frobenius 距离。

进一步阅读（Further Notes）

谱聚类在 Von Luxburg, 2007 的综述中有很好的讲解。关于 Louvain 算法的更多细节，我们推荐读者参阅 Blondel et al., 2008; Good et al., 2010。Jamonnak et al., 2015 介绍了 Louvain 算法（以及更一般的社区检测方法）在 Reddit 内容推荐上的一个精彩应用。Traag et al., 2019 发现了 Louvain 算法的其他缺陷（例如产生内部连通性很差的社区），他们同时也提出了 Louvain 算法的一个改进版本（称为 Leiden 算法（Leiden algorithm））。我们还提到分辨率极限（resolution limit）问题（Fortunato and Barthelemy, 2007），这是模块度最大化方法共有的问题。最后我们指出：尽管模块度方法很流行——得益于快速算法的存在，以及把模块度最大化与最大似然方法联系起来的启发式考虑——但仍需小心，因为模块度最大化与似然最大化并不严格等价（Zhang and Peixoto, 2020），而且模块度算法容易过拟合。

SBM 中谱方法的一致性由 Lei and Rinaldo, 2015 研究，并在 Abbe et al., 2020 中得到进一步发展。关于谱方法各种应用的近期综述，我们推荐 Chen et al., 2021。谱方法并不是在 SBM 上唯一一致的方法。例如，SDP 方法的一致性也已被证明（Hajek et al., 2016a,b; Guédon and Vershynin, 2016; Amini et al., 2018; Fei and Chen, 2019）。此外，其他分块模型（如几何分块模型）中的社区检测最近也得到了研究（Galhotra et al., 2018; Sankararaman and Baccelli, 2018; Avrachenkov et al., 2021a）。

还存在许多其他的社区检测方法，例如：信念传播（belief propagation）（Moore, 2017; Decelle et al., 2011）、博弈论方法（Avrachenkov et al., 2018a; Moscato et al., 2019）、基于映射方程（map equation）的方法（Rosvall and Bergstrom, 2008; Rosvall et al., 2009），以及基于其他矩阵的谱方法，如非回溯矩阵（non-backtracking matrix）（Krzakala et al., 2013）或 Bethe–Hessian（Saade et al., 2014）。关于社区检测问题的更多见解，我们也推荐 Fortunato, 2010 的综述。

最后，本文未覆盖的一个重要问题是社区个数的估计。关于这个主题，我们推荐读者参阅 Le and Levina, 2015; Bickel and Sarkar, 2016; Lei, 2016; Saldana et al., 2017; Hu et al., 2020。