大规模网络数据分析与空间自回归模型｜第3章 网络聚类分析(2)_节点_网络_分块

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

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所示。具体地，对于给定的网络社区数以及网络邻接矩阵，首先计算该网络的正则化拉普拉斯矩阵，然后对其进行特征分解并取得其最小个特征值对应的特征向量组成的矩阵，把的每一行看作对应网络节点的嵌入向量，最后利用均值聚类方法对的行向量进行聚类，由此得到所有网络节点的划分。

图 4: 网络社区检测的谱聚类算法流程图

参考文献

Airoldi, E. M., Blei, D. M., Fienberg, S. E., and Xing, E. P. (2008), “Mixed membership stochastic blockmodels,” Journal of Machine Learning Research, 9, 1981–2014.

Anderson, C. J., Wasserman, S., and Faust, K. (1992), “Building stochastic blockmodels,” Social Networks, 14, 137–161.

Bach, F. R. and Jordan, M. I. (2009), “Spectral clustering for speech separation,” Automatic Speech and Speaker Recognition: Large Margin and Kernel Methods, 369, 221–253.

Chasanis, V. T., Likas, A. C., and Galatsanos, N. P. (2009), “Scene detection in videos using shot clustering and sequence alignment,” IEEE Transactions on Multimedia, 11, 89–100.

Donath, W. E. and Hoffman, A. J. (2003), “Lower bounds for the partitioning of graphs,” in Selected Papers Of Alan J Hoffman: With Commentary, World Scientific, pp. 437–442.

Fiedler, M. (1973), “Algebraic connectivity of graphs,” Czechoslovak Mathematical Journal, 23, 298–305.

Holland, P. W., Laskey, K. B., and Leinhardt, S. (1983), “Stochastic blockmodels: First steps,” Social Networks, 5, 109–137.

Karrer, B. and Newman, M. E. (2011), “Stochastic blockmodels and community structure in networks,” Physical Review E, 83, 016107.

Koen, R. Y. and Kagan, R. C. (1960), The China lobby in American politics, Macmillan New York.

Liu, H., Jiao, L., and Zhao, F. (2010), “Non-local spatial spectral clustering for image segmentation,” Neurocomputing, 74, 461–471.

Ng, A. Y., Jordan, M. I., and Weiss, Y. (2002), “On spectral clustering: Analysis and an algorithm,” in Advances in Neural Information Processing Systems, pp. 849–856.

Rohe, K., Chatterjee, S., Yu, B.,et al. (2011), “Spectral clustering and the high-dimensional stochastic blockmodel,” The Annals of Statistics, 39, 1878–1915.

Shi, J. and Malik, J. (2000), “Normalized cuts and image segmentation,” IEEE Transactions on pattern analysis and machine intelligence, 22, 888–905.

Spielman, D. A. and Teng, S. H. (1996), “Spectral partitioning works: Planar graphs and finite element meshes,” Linear Algebra & Its Applications, 421, 284–305.

Tung, F., Wong, A., and Clausi, D. A. (2010), “Enabling scalable spectral clustering for image segmentation,” Pattern Recognition, 43, 4069–4076.

Von Luxburg, U. (2007), “A tutorial on spectral clustering,” Statistics and Computing, 17, 395– 416.

Wang, L. and Dong, M. (2012), “Multi-level low-rank approximation-based spectral clustering for image segmentation,” Pattern Recognition Letters, 33, 2206–2215.

Wasserman, S., Faust, K.,et al. (1994), Social Network Analysis: Methods and Applications, vol. 8, Cambridge University Press.

Yun, S.-Y. and Proutiere, A. (2016), “Optimal cluster recovery in the labeled stochastic block model,” in Advances in Neural Information Processing Systems, pp. 965–973.

Zachary, W. W. (1977), “An information flow model for conflict and fission in small groups,” Journal of Anthropological Research, 33, 452–473.

Zeng, S., Sang, N., and Tong, X. (2011), “Hand-written numeral recognition based on spectrum clustering,” in MIPPR 2011: Pattern Recognition and Computer Vision, International Society for Optics and Photonics, vol. 8004, p. 80040X.

作者简介

黄丹阳，中国人民大学统计学院副教授，博士生导师，应用统计科学研究中心研究员，中国人民大学杰出青年学者，北京大数据协会理事会副秘书长，常务理事，全国工业统计学教学研究会青年统计学家协会理事。主持国家自然科学基金面上项目，青年项目，北京市社会科学基金青年项目等多项省部级及以上课题，曾获北京市优秀人才培养资助。长期从事复杂网络建模、超高维数据分析、分布式计算等方向的理论研究工作，注重统计理论研究在小微企业数字化发展中的实际应用。在Journal of Econometrics, Journal of the American Statistical Association, Journal of Business & Economic Statistics,以及《统计研究》等国内外期刊发表论文近30篇。

书籍简介

本书的主要内容包括网络数据的基本定义及基本特征，大规模网络数据的常见分析方法（链路预测，网络聚类）及应用，以及空间自回归模型在网络数据分析中的定义，模型拓展以及应用等等。本书关注大规模网络数据分析中的模型方法。除模型方法本身的理论拓展之外，在估计方法等方面会涉及大规模数据中的快速计算方法。由于网络分析本身的范围非常广泛，故本书涉及到的仅局限于作者及团队研究工作中使用到的一部分。在书的最后，为了启发读者思路，本书对于部分已有网络研究进行了梳理。本书的读者对象为统计学学者，对网络数据分析感兴趣，并且具备一定统计学基础的研究生，高年级本科生等。

往期推荐:

第1章 网络数据的定义及相关指标（1）

第1章 网络数据的定义及相关指标（2）

第1章 网络数据的定义及相关指标（3）

第2章 大规模网络中的链路预测（1）

第2章 大规模网络中的链路预测（2）

第2章 大规模网络中的链路预测（3）

第2章 大规模网络中的链路预测（4）

第2章 大规模网络中的链路预测（5）

第3章 网络聚类分析（1）