基于稀疏子空间聚类的多层网络社团检测

孙登第，凌 媛，丁转莲，罗 斌

（1.安徽大学 计算机科学与技术学院，合肥 230601；2.安徽大学 互联网学院，合肥 230039）

0 概述

社团检测的目的是对复杂网络中的节点进行划分，使同类节点属于相同的社团。通过社团检测可以更好地理解复杂网络的拓扑结构和功能特性，因此其对网络分析与数据挖掘至关重要，目前被广泛应用于机器学习［1］、计算机视觉［2］、图像处理［3-4］等领域中。

近年来，已出现较多针对社团检测问题的研究，如文献［5］提出一种基于网络拓扑与节点元数据的社团检测算法，文献［6］进行了局部优先的动态网络重叠社团及其演变模式检测，文献［7］基于网络社团检测实现了电信客户细分，文献［8］提出了带偏置信号传播随机游走的社团检测算法，但这些工作主要集中于单层网络，即网络节点之间只存在一种关系的情况。然而在现实环境中，网络可能同时具备多种连接类型，例如：在通信网络中，存在用户之间不同的通信方式，如电话、微信、微博等；在贸易网络中，国家之间会有不同商品的贸易往来，如食品、衣服等。如果不考虑连接的多种形式而将这些网络简化为单一类型的交互，将无法捕获系统、丰富而全面的内部结构。为了涵盖这些关系的多类型特性，利用相同的节点集合分层描述不同连接，以形成多层网络（也称为多重网络或复合网络），并对其进行社团检测显然具有更强的科学意义。因此，此项技术引起了广泛关注［9-11］。

多层网络具有维度高、结构复杂、层间差异大的特点，许多算法无法有效地检测其社团结构。随着稀疏学习研究的不断深入，各种子空间表示方法不断涌现。2009 年，ELHAMIFAR 等［12］提出了稀疏子空间聚类模型，该模型的解具有块对角结构，同一个块的数据属于同一子空间。然而，该方法单独考虑每个数据的稀疏表示，缺乏对数据集全局结构的描述。2010年，LIU等［13］提出了基于低秩表示的子空间聚类方法（LRR），以捕获数据集的全局结构。2018 年，FANG 等［14］通过将高斯场与调和函数合并到LRR 框架中，提出一种非负低秩表示方法，其在一个优化步骤中同时完成了相似度矩阵构建和子空间聚类。同年，WANG 等［15］提出一种局部与结构正则化的低秩表示方法（LSLRR），同时考虑了数据的局部几何结构和全局块对角线结构，改进了经典LRR 方法。2020 年，陶洋等［16］提出将对称约束和结构约束融合到高维数据表示的低秩属性中，同时捕获高维数据的全局对称结构和子空间的加权局部线性结构，以提高聚类性能。

子空间表示方法能够准确描述数据分布，并通过子空间聚类自适应地将数据划分到不同的子空间中，在网络嵌入与聚类中体现出重要的应用价值。但现有的子空间聚类模型大多只适用于单层网络，亟需将其推广到多层网络，深入挖掘层间的互补信息，实现多层融合与协同聚类。本文针对多层网络的社团检测问题，提出一种多层网络稀疏子空间聚类方法。引入结构化的稀疏约束l2，1范数，并在迭代过程中更新不同层的权重，以描述各层网络对社团检测的重要程度。在此基础上，设计交替方向乘子方法ADMM［17］，联合优化层权重、节点稀疏表示和图结构的鲁棒性。

1 基于稀疏子空间聚类的社团检测模型

如图1 所示，本文研究的多层网络是M个单层网络的集合，表示为Gi(V，Ei)，i=1，2，…，M。每层网络中的节点数相同(n=|V|)，但是连通模式和链路分布不同(mi=|Ei|)。该多层网络可以用一组邻接矩阵来进行表示，即A={A1，A2，…，AM}，其中，Ai∊ℝn×n表示第i层的邻接矩阵。多层网络中社团检测的目的是推断出最适合所有给定层共享的潜在社团分配。考虑每层包含的信息具有互补性，通过整合来自所有层的信息查找共享社团的过程也称为网络集成（融合）［18］。

图1 多层网络示意图Fig.1 Schematic diagram of multi-layer network

1.1 节点相似性度量

与现有方法不同，本文提出的子空间聚类方法不直接作用在邻接矩阵上，而是通过计算每个节点相对于网络中所有其他节点的测地距离矢量来表示该节点。对于未加权的网络，测地距离是沿最短路径的2 个节点之间的链路数；对于加权图，测地距离是沿最短路径的链路的权重的总和。这样就可以将每个节点都嵌入到高维几何空间中。由于社团定义为具有更多组内链接和更少组间链接的节点组，因此同一社团中2 个节点之间的测地距离的期望值将小于2 个不同社团中2 个节点的测地距离的期望值。所以，在映射的几何空间中，每个社团将分布于一个独立的子空间中。尽管节点的嵌入维度与网络中的节点数相同，但由于数据聚类的低秩特性，实际维度却要小得多，具体取决于节点所在社团的大小。例如对于一个包含2 个社团的未加权无向网络，节点标记为｛1，2，3｝和｛4，5，6｝，每个社团内部的3 个节点两两相连。在此网络中，每个节点由测地距离矩阵P的1 列表示，如式（1）所示：

令pi为vi与所有vj∊G的测地距离的集合，所有这些向量的集合为矩阵P∊ℝn×n，P=[p1，p2，…，p n]。P(i，j)是vi与vj之间的距离，并且P的所有对角线项均为零(P(i，i)=0)，即网络没有任何自环。进一步地，使用高斯核函数将测地距离向量pi转换为相似性向量，如式（2）所示：

其中：σs控制衰减率；◦表示点乘运算符。如果无法从节点vj到达节点vi，则P(i，j)=∞，S(i，j)=0。

1.2 多层网络的联合稀疏表示

基于上述表示形式，本文提出如下的联合稀疏表示模型。受到稀疏聚类算法［12，19］的启发，相同社团的节点在相同的稀疏子空间中，因此，每个节点都可以由剩余节点的线性组合稀疏地表示，即Sm=Sm Zm，Zm是稀疏表示系数矩阵。由于网络中的数据会受到不同程度噪声的干扰，因此为提高模型的鲁棒性，本文引入噪声矩阵，融合所有层的联合稀疏表示如式（3）所示：

在现实世界中，通常不同层具有不同的信息量，因此，为每层分配一个自适应权重，从而使得本文方法能够自适应地整合不同层的节点数据。将这些层权加到式（3）中，自适应权重的多层网络联合稀疏表示模型如式（4）所示：

其中：r=[r1，r2，…，rΜ]Τ是层权向量，rm表示第m层的权重；Γ表示rm的正则化，当允许它们单独指定时，它可以避免rm的退化解，Γ是一个自适应参数，在第1 次迭代之后确定。

1.3 正则化的联合稀疏表示学习

现有多数方法使用表示系数矩阵来定义图的亲和性：W=(|Z|+|ZΤ|)/2。虽然这种亲和力在某种程度上是有效的，但它表示的含义已经不同于图原始的定义［20］。该方法获得的亲和性图矩阵会不可避免地存在一些元素是负数的情况，而矩阵中的元素对应图中边的权重，即节点间的关联，所以，当出现边权是负数时不能做出有意义的解释。本文通过式（5）所示约束，直接学习出一个统一的、更能描述多层网络中节点子空间一致性分布的协同亲和图G。

在式（5）中：δ和ω是平衡参数；1 表示单位矢量；G∊ℝn×n为期望的亲和度矩阵，即要学习的协同亲和图；Gij为第i和第j节点来自同一社团的概率，通过计算跨层联合表示Zi和Zj之间的距离来衡量；约束GΤ1=1 和G≥0 用于保证Gi概率性质；用于避免过拟合。

结合式（4）和式（5）可得到本文最终的模型，如式（6）所示。该模型框架如图2 所示。

图2 本文模型框架Fig.2 Framework of the proposed model

2 模型优化与求解

针对式（6）所示模型，本文设计了如下的优化求解算法。虽然式（6）具有较多变量，整体上非凸的，但是固定其他变量时，其每个变量的子问题都是凸的，并且具有闭合解。因此，本文使用交替方向乘子算法（ADMM）［17］将模型函数分离成具有闭合解的独立子问题。引入辅助变量Qm∊ℝn×n和Pm∊ℝn×n，使得式（6）是可分离的，得到式（7）所示形式：

其 中：P=[P1，P2，…，PM]；Q=[Q1，Q2，…，QM]。将式（7）中的约束条件进一步转化为式（8）所示的增广拉格朗日函数：

3 实验与结果分析

为验证本文方法的有效性，采用多种数据集设计实验。

3.1 数据集

在10 个现实世界的网络上测试本文方法，以证明其在广泛领域中的适用性。这些数据集的相关信息如下：

1）引文数据集，包括Citeseer、CoRA 数据集，分别有6 类3 312 份论文和7 类2 708 份论文。这2 个数据集都使用同样的方法构建为两层网络，其中引文层表示论文之间的引用关系，相似层表示论文之间的文本相似性。

2）推特数据集，包括Football、Olympics、Politics数据集。Football 数据由推特上活跃的248 个足球运动员数据组成，根据所属俱乐部划为20 个类，这些球员的社交网络被分为3 层，分别代表推特用户之间的3 种交互方式；Olympics数据涵盖了参与2012 年伦敦夏季奥运会的464 位运动员和组织数据，按28 个大项分类，本文使用与Football 数据集相同的方法来构造3 层；Politics 数据集为419 位来自英国的国会议员数据，依据政党划分为5 类，同样构建3 层。

3）手机数据集MPD，由3 层组成，代表麻省理工学院中87 个用户之间不同的联系，包括物理位置、蓝牙扫描和电话。

4）社交网络数据集SND，由律师事务所的71 个员工数据组成，3 层网络表示他们之间的3 种交互方式。

5）脑虫网络WBN，由代表神经元的279 个节点组成，通过5 种不同类型的链接相连，代表5 种不同类型的突触，本文使用神经元类型作为真实标签。

6）世界贸易网络WTN，包含214 个国家之间的贸易关系，分别使用地理区域和经济贸易类别作为标签，因此产生WTN（reg）和WTN（cat）2 种网络。

实验中使用的数据集的节点数目、层数目和真实类数目如表1 所示。

表1 多层网络数据集Table 1 Multi-layer network datasets

3.2 参数设置

由于式（8）中的参数较多，并且对于不同的数据集各参数都会相应变化，因此在实验中反复调整力求结果较优，不同数据集中的参数设置如表2 所示。为了便于调参，在实验中将λ和γ设置为相同的值，并且在所有的数据集中设置ξ=3。此外，通过实验验证参数的选取。

表2 各数据集中的参数设置Table 2 Parameter settings in each dataset

3.3 比较方法

选取单层网络和多层网络2 类方法进行比较。

1）单层网络方法。为了与已有的子空间聚类方法进行比较，选择最具有代表性的SSC［12］、LRR［13］、和SSCF［22］方法，但是子空间聚类方法目前仅应用于单层网络中，为了将它们应用于多层网络，首先将所有网络层合并为一个由以下邻接矩阵描述的单层网络：A=。此外，还与Ncut［23］方法进行比较，以验证本文方法的有效性。

2）多层网络方法。将本文方法与当前具有代表性的多层网络社团检测方法进行比较，分别是基于矩阵分解的CSNMF 方法［24］和LMF 方法［25］、基于信息融合的SNF 方法［26］、基于谱聚类的SC-ML 方法［27］，为了展现公平性，所有的实验以最佳结果进行对比。

3.4 评估指标

采用以下3种广泛使用的评估指标：纯度（Purity）［28］，规一化互信息（NMI）［29］，准确性（ACC）［30］。这3 个指标都提供了一种定量方法来比较计算的社团聚类Ω={φ1，φ2，…，φκ}和真实标签C={c1，c2，…，cκ}。

正确分类的节点数的百分比如式（9）所示：

其中：n是节点总数；|φk∩cj|表示φk与cj的交集的节点数。

为了平衡社团聚类的质量与数量，使用NMI 指标，其定义如式（10）所示：

其中：I表示节点簇Ω与真实类C之间的互信息；H(Ω)和H(C)分别表示簇和类的熵。

给定一个包含n个顶点的数据集，对于每个样本网络，令ψi为通过应用不同方法获得的聚类标签，而ζi为该数据集提供的真实标签，被正确分配的节点的百分比如式（11）所示：

其 中：δ(x，y) 是delta 函数，即当x和y相等时，δ(x，y)=1，否则等于0；map(ψi)是将每个社团标签ψi映射到数据集中等效标签的映射函数。

3.5 计算复杂度和收敛性分析

利用O标记简要分析本文模型的计算复杂度。在算法1 中，当不考虑基本的矩阵运算，如矩阵相加、矩阵相乘时，最大的计算成本是矩阵的逆运算，对于大小为n×n的矩阵，逆运算的计算复杂度为O（n3），由于在Z 和P的更新过程中存在逆运算，因此算法1 的总计算复杂度约为Ο(2τn3)，其中，τ是迭代次数。

此外，本文采用ADMM 算法求解所提出的多层网络联合稀疏表示模型。由于目标函数较为复杂，因此基于梯度的方法不能保证找到最佳解。为验证所得优化路径，在多层网络上进行收敛性实验。对于每一个网络，在每次迭代后保存目标函数l的值，并将其绘制为波形图。SND、Football、Olympics 和WTN 网络上的实验结果如图3 所示，从波形图中可以发现，目标函数l快速收敛并趋于稳定。因此，实验结果验证了本文方法的收敛性。在其他网络中也具有类似的结果。

图3 收敛性对比Fig.3 Comparison of convergence

3.6 参数分析

本文方 法的参数σs、λ、δ、ω对实验结果的影响如图4 所示，为保持参数选取标准的一致性，选择NMI 作为主要评估指标。可以看出，结果与上文分析保持一致。此外还可以看出，对不同的数据库，参数曲线在每个参数最优值两侧较长的一段中均保持平稳，表明本文方法对参数具有一定的鲁棒性。

图4 不同参数对实验结果的影响Fig.4 Influence of different parameters on experimental results

3.7 社团检测实验结果

本文方法和其他8 种方法在Purity、NMI、ACC 3 种指标下的实验结果如表3～表5 所示，最优结果用黑体表示。可以看出，本文方法在大部分数据集中都能达到最优。值得注意的是，在推特数据集的3 个网络中（Football、Olympics、Politics），所有方法的结果都很理想，这是因为该数据集中网络层的社团内部连接较为紧密，社团结构较为清晰，有利于进行社团检测。本文方法无规律地略低于某些方法，这源于优化过程中的参数设置与迭代次数导致的精度误差。但是，在网络社团结构较差的Citeseer 和CoRA 中，本文方法明显优于其他所有比较方法，说明本文方法可以挖掘不同层的互补信息，得到更为准确的一致性联合稀疏表示。此外，从与单层的子空间分割算法（LRR、SSC、SSCF）的比较可以看出，本文方法中加入的距离正则项和自适应权重对子空间分割产生了积极的作用，大幅提高了聚类性能。

表3 不同方法检测精度比较（Purity）Table 3 Accuracy comparison of different methods（Purity）

表4 不同方法检测精度比较（NMI）Table 4 Accuracy comparison of different methods（NMI）

表5 不同方法检测精度比较（ACC）Table 5 Accuracy comparison of different methods（ACC）

4 结束语

为解决多层网络中的社团检测问题，本文提出一种基于子空间分割的多层网络联合稀疏表示方法。不同于传统的单层网络分割与平均叠加的思路，本文将距离正则项和非负约束条件共同集成到SSC 框架中，同时利用数据的全局和局部信息进行图学习，并且在模型中引入l2，1范数，促使学习到的协同亲和图具有更清晰的聚类结构。此外，整合互补层的信息并考虑不同层的重要性，设计基于ADMM 的迭代算法来优化模型。下一步将通过优化算法参数，扩大本文方法的适用性。