本书主要关注基于谱分解的网络聚类算法。在介绍方法之前，先简单介绍随机分块模型的基本定义。

3.2.1 随机分块模型的基本定义

回顾前面讨论的网络社区划分质量的度量指标，其基本思想是将实际网络与其对应的随机网络进行比较，从而度量出其社区划分的效果。因此，在讨论谱聚类网络社区检测方法之前，首先介绍一种随机网络的生成模型。从应用的角度出发，随机网络的价值起到一种参照系的作用；从理论的角度出发，随机网络生成模型方便在总体框架下分析网络社区检测算法的理论性质。

随机分块模型（stochatic block model, SBM）是具有区块结构的随机网络生成模型。区块结构是指将网络中的节点划分为子集合（也称为块）。随机分块模型假设节点之间是否有连接是相互独立的，其概率取决于节点所属的块，并且区块内部节点之间的连接概率大于区块间节点连接概率。随机分块模型在统计学、机器学习和网络科学中有着重要的作用，它可以作为用于网络社区发现的有效基准模型（Holland等, 1983; Anderson等, 1992），并且已广泛应用于对社交网络（Zachary 1977）、客户消费网络（Koen和Kagan 1960）、世界贸易网络（Wasserman等 1994）等的研究中。

最早的随机分块模型出现在Holland等（1983）对于社交网络的分析中，它假设网络节点与节点之间的连接是服从伯努利分布的随机变量，并且网络节点之间的连接是相互独立的，其中区块内各节点的连接概率相同。事实上，区块内节点连接的概率可以和节点的自身特征相关。本书参考Rohe等（2011）研究中的定义，给出随机分块模型的相关符号以及具体定义。

假设随机分块模型生成的随机网络包含 个子块。回顾前面的定义， 表示网络节点 所属的子块标签，其中 , 。则网络社区可表示为 ， 。假设网络中节点之间的连接是服从伯努利分布的随机变量，记连接概率矩阵 ，则 , 。无向网络随机分块模型定义如下。

定义3.4 随机分块模型对应的随机概率矩阵 可表示为

其中， 为隶属矩阵(membership matrix)，该矩阵每一行有且仅有一个非零元素 ， ； 表示区块矩阵(block matrix)，其包含的元素 表示区块 中节点与区块 中节点的连接概率，且满足 ， 。

以上定义的直观解释是，基于随机分块模型生成的随机网络，其区块特征可以由网络节点连接的稀疏程度体现。具体来说，随机分块网络中，两节点之间的连接概率与其他节点之间是否有连接独立，只与两节点所属的区块有关，且属于同一个区块的两个节点连接概率不小于不同区块之间的节点连接概率。如图1所示， 、 表示两个区块， 和 分别表示区块 和 内部节点的连接概率， 表示区块 与 节点之间的连接概率并且满足 。

展开全文

图 1: 具有两个区块结构的随机分块模型连接概率图

现有大量关于简单随机分块模型的扩展模型，本书示例性地介绍以下三种。

(1)带标签的随机分块模型。网络节点之间存在多种交互的场景，在现实世界中许多网络具有节点交互多样性的特征，如蛋白质化学反应可能是放热的或吸热的，电子邮件交流内容可能是冷淡、正式或熟悉的，社交媒体网站上用户之间的关系通常反映出正面（友好）和负面（对抗）互动的混合。简单的随机分块模型无法体现这种节点交互的多样性，而带标签的随机分块模型通过对节点之间的连接设定标签，基于标签可以根据节点之间的不同交互类型来刻画节点间的相似度（Yun和Proutiere, 2016）。

(2)度修正的随机分块模型。在现实世界的网络中同一社区内的节点是具有各自特征的，如图2的空手道俱乐部网络以及图3的美国政治博客网络都展现出了同一社区内不同节点的度是存在差异的（Karrer和Newman, 2011）。而简单的随机分块模型假定同一区块内所有节点具有相同的特征，不够灵活，且有时无法生成与大多数经验网络数据中发现的结构相似的网络，因此，用简单的随机分块模型拟合复杂的真实网络结构可能会丢失很多节点重要特征。度修正的随机分块模型允许同一区块内不同节点的度不一致（Karrer和Newman, 2011），为每个节点设置度参数，使得节点间的连接概率与节点的度相匹配，从而能更好地产生和现实世界网络更相似的网络。

图 2: 基于度修正的随机分块模型的空手道俱乐部社区划分 (Karrer 和 Newman, 2011)

注：节点的灰度表示成员的社区属性

图 3: 基于度修正的随机分块模型的美国政治博客网络社区划分 (Karrer 和 Newman, 2011)

注：节点的灰度表示博客的社区属性

(3)混合成员随机分块模型。现实世界中的对象是多维度的，社交网络中的对象与不同对象互动时，可能会根据不同的社交场景发挥不同的作用。例如，在大学网络中存在老师和学生的互动关系，同一个老师可能与一些学生存在教学关系，与一些学生存在好友关系，与一些学生存在合作关系等。简单的随机分块模型假定研究对象都只能属于某一个簇，也就是说限定研究对象只有一种角色。为了适应网络中具有不同类型的节点和连接的情况，Airoldi等（2008）提出混合成员随机分块模型，此模型允许社区重叠，网络节点不限于只属于某一个簇，而可以属于多个簇。混合成员随机分块模型的各节点在不同的场景下所属的类可以不同，因此可用来刻画节点的多种特征。

3.2.2 网络数据中的谱聚类分析方法

最近几十年来，谱聚类是应用最广泛的聚类算法之一（Ng等, 2002; Rohe等, 2011）。谱聚类分析方法将图分割问题近似转化为线性代数求解问题，其优点在于计算简便，且对数据类型没有限制，故应用范围较广。具体而言，给定数据集 ，其中 ( )表示样本 的特征，可定义相似矩阵 ，其中 衡量了节点对的相似程度，通常选择高斯相似函数，即 ，其中 为尺度参数。谱聚类算法中最重要的工具是拉普拉斯矩阵 ，其中 为对角矩阵，其对角线元素 ， ，可表示为对应节点的影响力。由于理论分析的需要，应用更加广泛的通常是正则化拉普拉斯矩阵，其定义为

谱聚类思想的核心是基于拉普拉斯矩阵的特征分解将数据集 投影到低维空间，然后在低维空间进行聚类分析。

具体地，取正则化拉普拉斯矩阵 的最小 个特征值对应的特征向量 ，设 ，那么矩阵 的行向量 ( )可以看作数据集 在低维空间的投影向量。因此，对数据集 的聚类问题可以转化为对 的聚类分析。接下来将从图分割的角度解释谱聚类算法的可行性。

聚类的目的是根据各节点的相似性将不同簇中的点分开。给定图邻接矩阵 ，最简单直接的图分割方法是求解最小分割问题。首先定义 ，表示两个区块 和 之间的连接数，并且令 表示集合 的补集。那么最小分割问题可定义如下。

定义3.5 （最小分割准则）对于给定的子集数 ，定义分割损失函数

若存在一组划分 使得分割损失函数取到最小值，那么称 满足最小分割准则。

其中 表示按照 进行图划分需要分割的连接数。该定义基于保证区块内连接最多的原则，由于网络中所有连接的总数是固定的，那么划分需要分割的连接数越少，留在区块内部的连接就越多。这样不仅能保证网络连接的完整性，还能保证区块内与区块间节点间连接密度的差异性。Shi和Malik（2000）在此基础上提出了最小正则化分割（normalized cut）准则。

定义3.6 （最小正则化分割准则）对于给定的子集数，定义正则化分割损失函数

其中，表示社区所有节点度的总和。若存在一组划分使得正则化分割函数取到最小值，那么称满足最小正则化分割。

其中表示与社区有关的连接数，那么可表示社区的连接分割比例。因此表示按照进行分割的图连接分割率。相比最小分割准则，最小正则化分割准则在理论分析中应用更加广泛。

现在将通过最小正则化准则分析谱聚类分析方法的合理性。首先定义簇示性向量，其中

其 他

然后令矩阵 ，则 ， ，并且 。因此最小正则化分割问题可以转化为

注意到 矩阵里的每一个指示向量都是 维的，向量中每个元素的取值为 或者 ， 。若放宽该条件仅约束 ，那么将 代入式(3.13)可得

即

这是标准的迹最小化问题，其解矩阵 可通过求解 的 个最小特征值对应的特征向量得到。这说明正则化谱聚类算法的原理就是最小正则化分割的近似解。

这里主要介绍谱聚类在网络社区检测中的应用。对于给定的无向图 ，其邻接矩阵 中的元素满足 , 因此邻接矩阵 可以作为网络节点对的相似矩阵，其中矩阵元素 为伯努利随机变量。那么对应的正则化拉普拉斯矩阵可定义为

其中， 为度矩阵。借鉴 Ng等（2002）的工作，利用谱聚类分析方法实现网络社区检测的详细过程见算法1，并且该算法流程如图4所示。具体地，对于给定的网络社区数以及网络邻接矩阵，首先计算该网络的正则化拉普拉斯矩阵，然后对其进行特征分解并取得其最小个特征值对应的特征向量组成的矩阵，把的每一行看作对应网络节点的嵌入向量，最后利用均值聚类方法对的行向量进行聚类，由此得到所有网络节点的划分。