大规模网络数据分析与空间自回归模型｜第3章 网络聚类分析(3)
在应用谱聚类分析方法实现网络社区检测的过程中，针对不同类型的网络，通常需要对传统的谱聚类分析方法进行改进。接下来主要介绍几种常见的网络类型以及谱聚类分析方法的推广。
3.3.1 针对稀疏网络的谱聚类算法改进
稀疏网络指的是网络中的节点与节点之间连接稀疏，因此邻接矩阵中的非零元素很少，通常可以用网络节点的平均度来刻画网络的稀疏程度。记网络节点个数为，假设网络的期望最小度至少是，Lei等（2015）在理论上证明了基于传统的谱聚类算法的聚类误差收敛性。然而当网络节点的平均度小于时，Amini等（2013）发现传统谱聚类算法表现不理想。其主要原因有两点：第一，在稀疏网络中存在大量的孤立节点，由于没有连接信息，谱分析方法很难将这些节点正确划分。第二，稀疏矩阵的特征向量往往是局部化的，对于稀疏网络的拉普拉斯矩阵，其较大特征值对应的特征向量往往聚集在度较大的节点所对应的位置，不能用作网络社区划分，因此传统的谱聚类效果通常不好。
在大数据时代的背景下，大多数大规模网络都是稀疏的。以淘宝用户与用户的消费网络为例，若两个用户在同一个商家消费过，则用户之间有连接，否则无连接，考虑到大部分用户所交易的店家数相对淘宝所有店家数而言是非常少的，这是一个稀疏的网络。因此需要将谱聚类分析方法进行改进，从而推广到稀疏网络。Amini等（2013）在传统谱聚类分析方法的基础上，提出了带扰动的谱聚类算法，该算法的核心思想是人为地给所有的节点对添加“弱连接”。具体来说，通过在邻接矩阵的所有元素上增加扰动参数，可以得到正则化邻接矩阵定义如下：
3.3.2 针对度异质性网络的谱聚类算法改进
度异质性网络是指在同一个社区内不同节点的度具有明显的差异性的网络。例如，美国政治博客网络，对于同一个政治群体中的人而言，不同的人具有的影响力不同，并且每个人社交能力的差异导致各自的好友数目也具有较大差异，这就体现出了该网络的度异质性。常见的度异质性网络模型为度修正的随机分块模型（Karrer和Newman，2011）。Jin等（2015）指出传统谱分析方法在度异质性网络中的聚类效果不理想，其原因是对于度异质性网络，其拉普拉斯矩阵对应的特征向量不具有网络社区结构信息。针对度异质性网络，Jin等（2015）改进了传统的谱聚类分析方法，提出了基于特征向量比率的谱聚类算法，利用特征向量间的逐项比消除度异质性影响。具体来说，对于具有个不同社区的度异质性网络，基于特征向量比率的谱聚类算法步骤可以分为以下三步。
(1)计算邻接矩阵的特征分解，取出前个最大特征值对应的特征量；
(2)计算坐标比率向量，其中,令；
(3)对矩阵的行向量进行均值聚类分析。
基于特征向量比率的谱聚类算法可以避免估计度异质性参数，在实际应用中将更加有效。
3.3.3 针对具有混合属性节点的网络的谱聚类算法改进
具有混合属性节点的网络是指该网络中的节点没有严格的属性，这些节点不限于只属于某一个簇，而可以属于多个簇（Airoldi等, 2008）。例如，科研工作者的合作网络，根据科研领域可以将科研工作者进行划分，其中由于部分科研工作者兴趣广泛，他们可能属于多个科研领域。现有的大多数谱聚类算法都是硬分区方法，它们严格地将每个对象划分为一个类，而具有混合属性节点的网络更适合于软划分（Mirkin和Nascimento, 2012）。经典集理论常常不能完全解决歧义的分类问题，Zadeh等（1996）提出的模糊集理论则为这种软划分提供了有力的工具。将模糊集理论应用于谱聚类并研究出有效的模糊谱聚类算法，能够对具有混合属性节点网络的聚类提供很大的帮助，可参考Sun等（2011）的相关研究。
3.3.4 针对多层网络的谱聚类算法改进
多层网络是一种表示数据之间关系的有用工具，把研究对象看作节点，网络层表示的是这些对象间的多种关系，如图1所示（Kivelä 等, 2014）。以推特用户的交互网络为例，推特用户的社区属性表示为用户间的交互，而这种交互是多样的，可以基于政治观点、原国籍、足球俱乐部等，不同的角度下推特用户之间的交互关系就可以表示为多层网络。针对多层网络，Paul等（2020）把谱分析方法推广到多维空间，通过组合多层网络多层信息的方式来划分网络社区。对于给定的层网络, 其邻接矩阵可用三维的邻接张量表示，其中对于，表示第层中各个节点之间的连接关系。Tang等（2009），Paul等（2020）提出基于邻接矩阵分解方法分析多层网络问题，该方法利用张量分解对邻接矩阵进行分解，得到各个层的共同因子矩阵，然后对因子矩阵的行进行均值聚类分析。关于谱聚类分析方法在多层网络中的应用还可参见Nickel等（2011）和Lei等（2020）的相关研究。
参考文献
Abbe, E. (2017), “Community detection and stochastic block models: recent developments,” The Journal of Machine Learning Research, 18, 6446–6531.
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.
Amini, A. A., Chen, A., Bickel, P. J., Levina, E.,et al. (2013), “Pseudo-likelihood methods for community detection in large sparse networks,” The Annals of Statistics, 41, 2097–2122.
Jin, J.et al. (2015), “Fast community detection by SCORE,” The Annals of Statistics, 43, 57–89.
Joseph, A., Yu, B.,et al. (2016), “Impact of regularization on spectral clustering,” The Annals of Statistics, 44, 1765–1791.
Karrer, B. and Newman, M. E. (2011), “Stochastic blockmodels and community structure in networks,” Physical Review E, 83, 016107.
Kivelä, M., Arenas, A., Barthelemy, M., Gleeson, J. P., Moreno, Y., and Porter, M. A. (2014), “Multilayer networks,” Journal of Complex Networks, 2, 203–271.
Lei, J., Chen, K., and Lynch, B. (2020), “Consistent community detection in multi-layer network data,” Biometrika, 107, 61–73.
Lei, J., & Rinaldo, A. (2015). Consistency of spectral clustering in stochastic block models. The Annals of Statistics, 43(1), 215-237.
Mirkin, B. and Nascimento, S. (2012), “Additive spectral method for fuzzy cluster analysis of similarity data including community structure and affinity matrices,” Information Sciences, 183, 16–34.
Nickel, M., Tresp, V., and Kriegel, H.-P. (2011), “A three-way model for collective learning on multi-relational data.” in International Conference on Machine Learning, vol. 11, pp. 809–816.
Paul, S., Chen, Y.,et al. (2020), “Spectral and matrix factorization methods for consistent community detection in multi-layer networks,” The Annals of Statistics, 48, 230–250.
Qin, T. and Rohe, K. (2013), “Regularized spectral clustering under the degree-corrected stochastic blockmodel,” Advances in Neural Information Processing Systems, 26, 3120–3128.
Rohe, K., Chatterjee, S., Yu, B.,et al. (2011), “Spectral clustering and the high-dimensional stochastic blockmodel,” The Annals of Statistics, 39, 1878–1915.
Sun, P. G., Gao, L., and Han, S. S. (2011), “Identification of overlapping and non-overlapping community structure by fuzzy clustering in complex networks,” Information Sciences, 181, 1060–1071.
Tang, W., Lu, Z., and Dhillon, I. S. (2009), “Clustering with multiple graphs,” in 2009 Ninth IEEE International Conference on Data Mining, IEEE, pp. 1016–1021.
Zadeh, L. A., Klir, G. J., and Yuan, B. (1996), Fuzzy sets, fuzzy logic, and fuzzy systems: selected papers, vol. 6, World Scientific.
作者简介
黄丹阳，中国人民大学统计学院副教授，博士生导师，应用统计科学研究中心研究员，中国人民大学杰出青年学者，北京大数据协会理事会副秘书长，常务理事，全国工业统计学教学研究会青年统计学家协会理事。主持国家自然科学基金面上项目，青年项目，北京市社会科学基金青年项目等多项省部级及以上课题，曾获北京市优秀人才培养资助。长期从事复杂网络建模、超高维数据分析、分布式计算等方向的理论研究工作，注重统计理论研究在小微企业数字化发展中的实际应用。在Journal of Econometrics, Journal of the American Statistical Association, Journal of Business & Economic Statistics,以及《统计研究》等国内外期刊发表论文近30篇。
书籍简介
本书的主要内容包括网络数据的基本定义及基本特征，大规模网络数据的常见分析方法（链路预测，网络聚类）及应用，以及空间自回归模型在网络数据分析中的定义，模型拓展以及应用等等。本书关注大规模网络数据分析中的模型方法。除模型方法本身的理论拓展之外，在估计方法等方面会涉及大规模数据中的快速计算方法。由于网络分析本身的范围非常广泛，故本书涉及到的仅局限于作者及团队研究工作中使用到的一部分。在书的最后，为了启发读者思路，本书对于部分已有网络研究进行了梳理。本书的读者对象为统计学学者，对网络数据分析感兴趣，并且具备一定统计学基础的研究生，高年级本科生等。
扫描以下二维码购买本书：