开放科学（资源服务）标志码（OSID）：

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]提出将对称约束和结构约束融合到高维数据表示的低秩属性中，同时捕获高维数据的全局对称结构和子空间的加权局部线性结构，以提高聚类性能。

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

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

如图 1所示，本文研究的多层网络是M个单层网络的集合，表示为$ {G}_{i}(V, {E}_{i}) $，$ i=1{\rm{ }}, 2, \cdots , M $。每层网络中的节点数相同$ (n=|V\left|\right) $，但是连通模式和链路分布不同$ ({m}_{i}=|{E}_{i}\left|{\rm{ }}\right) $。该多层网络可以用一组邻接矩阵来进行表示，即$ \boldsymbol{A}=\{{A}^{1}, {A}^{2}, \cdots , {A}^{M}\} $，其中，$ {A}^{i}\in {\mathbb{R}}^{n\times n} $表示第$ i $层的邻接矩阵。多层网络中社团检测的目的是推断出最适合所有给定层共享的潜在社团分配。考虑每层包含的信息具有互补性，通过整合来自所有层的信息查找共享社团的过程也称为网络集成（融合）^[18]。

1.1 节点相似性度量

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

$ \boldsymbol{P}=\left[\begin{array}{cccccc}0& 1& 1& {\rm{\infty }}& {\rm{\infty }}& {\rm{\infty }}\\ 1& 0& 1& {\rm{\infty }}& {\rm{\infty }}& {\rm{\infty }}\\ 1& 1& 0& {\rm{\infty }}& {\rm{\infty }}& {\rm{\infty }}\\ {\rm{\infty }}& {\rm{\infty }}& {\rm{\infty }}& 0& 1& 1\\ {\rm{\infty }}& {\rm{\infty }}& {\rm{\infty }}& 1& 0& 1\\ {\rm{\infty }}& {\rm{\infty }}& {\rm{\infty }}& 1& 1& 0\end{array}\right] $

(1)

令$ {\boldsymbol{p}}_{i} $为$ {v}_{i} $与所有$ {v}_{j}\in G $的测地距离的集合，所有这些向量的集合为矩阵$ \boldsymbol{P}\in {\mathbb{R}}^{n\times n} $，$ \boldsymbol{P}=[\boldsymbol{p}{}_{1}, \boldsymbol{p}{}_{2}, \cdots , $ $ \boldsymbol{p}{}_{n}] $。$ P(i, j) $是$ {v}_{i} $与$ {v}_{j} $之间的距离，并且$ P $的所有对角线项均为零$ \left(P\right(i, i)=0) $，即网络没有任何自环。进一步地，使用高斯核函数将测地距离向量$ {\boldsymbol{p}}_{i} $转换为相似性向量，如式（2）所示：

$ \boldsymbol{S}={\rm{e}}{\rm{x}}{\rm{p}}\left(-\frac{\boldsymbol{P}\circ \boldsymbol{P}}{2{\sigma }_{{\rm{s}}}^{2}}\right) $

(2)

其中：$ {\sigma }_{{\rm{s}}} $控制衰减率；$ \circ $表示点乘运算符。如果无法从节点$ {v}_{j} $到达节点$ {v}_{i} $，则$ P\left(i, j\right)={\rm{\infty }} $，$ S\left(i, j\right)=0 $。

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

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

$\mathop {{\rm{min}}}\limits_{{\boldsymbol{Z}}, {\boldsymbol{E}}} \sum\limits_{m = 1}^M {\left\| {{{\boldsymbol{S}}^m} - {{\boldsymbol{S}}^m}{{\boldsymbol{Z}}^m} - {{\boldsymbol{E}}^m}} \right\|_{\rm{F}}^2} + \lambda {\left\| {{{\boldsymbol{E}}^m}} \right\|_{{\rm{2}}, {\rm{1}}}} + \gamma {\left\| {\boldsymbol{Z}} \right\|_{{\rm{2}}, {\rm{1}}}} $

(3)

其中：$ {‖\cdot ‖}_{{\rm{F}}} $和$ {‖\cdot ‖}_{{\rm{2, 1}}} $分别表示矩阵的Frobenius范数和$ {l}_{{\rm{2, 1}}} $范数；$ \lambda $和$ \gamma $是平衡参数；$ \boldsymbol{Z}=\left[{\boldsymbol{Z}}^{1}, {\boldsymbol{Z}}^{2}, \cdots , {\boldsymbol{Z}}^{M}\right]\in {\mathbb{R}}^{Mn\times n} $是跨层联合稀疏表示系数矩阵；$ {‖\boldsymbol{Z}‖}_{{\rm{2, 1}}} $约束使每个节点可以在不同层共享相同的子空间；$ {\boldsymbol{E}}^{m}\in {\mathbb{R}}^{n\times n} $表示第m层的噪声矩阵。

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

$ \begin{array}{l}\underset{\boldsymbol{Z}, \boldsymbol{E}, \boldsymbol{r}}{{\rm{m}}{\rm{i}}{\rm{n}}}\sum\limits _{m=1}^{{\rm M}}\left(\frac{{\left({r}^{m}\right)}^{2}}{2}{‖{\boldsymbol{S}}^{m}-{\boldsymbol{S}}^{m}{\boldsymbol{Z}}^{m}-{\boldsymbol{E}}^{m}‖}_{{\rm{F}}}^{2}+\lambda {‖{\boldsymbol{E}}^{m}‖}_{{\rm{2, 1}}}\right)+\\ \gamma {‖\boldsymbol{Z}‖}_{{\rm{2, 1}}}+\varGamma {‖1-\boldsymbol{r}‖}_{{\rm{F}}}^{2}\end{array} $

(4)

其中：$ \boldsymbol{r}=[{r}^{1}, {r}^{2}, \cdots , {r}^M{]}^{{\rm{{\rm T}}}} $是层权向量，$ {r}^{m} $表示第$ m $层的权重；$ \varGamma {‖1-\boldsymbol{r}‖}_{{\rm{F}}}^{2} $表示$ {r}^{m} $的正则化，当允许它们单独指定时，它可以避免$ {r}^{m} $的退化解，$ \varGamma $是一个自适应参数，在第1次迭代之后确定。

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

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

$ \begin{array}{l}\underset{\boldsymbol{G}}{{\rm{m}}{\rm{i}}{\rm{n}}}\delta \sum\limits _{i, j=1}^{n}{‖{\boldsymbol{Z}}_{i}-{\boldsymbol{Z}}_{j}‖}_{{\rm{F}}}^{2}{\boldsymbol{G}}_{ij}+\frac{\omega }{2}{‖\boldsymbol{G}‖}_{{\rm{F}}}^{2}{\rm{ }}{\rm{ }}\\ {\rm{s}}.{\rm{t}}.{\rm{ }}{\rm{ }}{\boldsymbol{G}}^{{\rm{T}}}1=1, \boldsymbol{G}\ge 0\end{array} $

(5)

在式（5）中：$ \delta $和$ \omega $是平衡参数；$ \boldsymbol{1}$表示单位矢量；$ \boldsymbol{G}\in {\mathbb{R}}^{n\times n} $为期望的亲和度矩阵，即要学习的协同亲和图；$ {G}_{ij} $为第$ i $和第$ j $节点来自同一社团的概率，通过计算跨层联合表示$ {\boldsymbol{Z}}_{i} $和$ {\boldsymbol{Z}}_{j} $之间的距离来衡量；约束$ {\boldsymbol{G}}^{{\rm{{\rm T}}}}\boldsymbol{1}=\boldsymbol{1} $和$ \boldsymbol{G}\ge \boldsymbol{0} $用于保证$ {G}_{i} $概率性质；$ \frac{\omega }{2}{‖\boldsymbol{G}‖}_{{\rm{F}}}^{2} $用于避免过拟合。

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

$ \begin{array}{l}\underset{\boldsymbol{Z}, \boldsymbol{E}, \boldsymbol{G}, \boldsymbol{r}}{{\rm{m}}{\rm{i}}{\rm{n}}}\sum\limits _{m=1}^{M}\left(\frac{{\left({r}^{m}\right)}^{2}}{2}{‖{\boldsymbol{S}}^{m}-{\boldsymbol{S}}^{m}{\boldsymbol{Z}}^{m}-{\boldsymbol{E}}^{m}‖}_{{\rm{F}}}^{2}+\lambda {‖{\boldsymbol{E}}^{m}‖}_{{\rm{2, 1}}}\right)+\\ \gamma {‖\boldsymbol{Z}‖}_{{\rm{2, 1}}}+\varGamma {‖\boldsymbol{1}-\boldsymbol{r}‖}_{{\rm{F}}}^{2}+\delta \sum\limits _{i, j=1}^{n}{‖{\boldsymbol{Z}}_{i}-{\boldsymbol{Z}}_{j}‖}_{F}^{2}{G}_{ij}+\frac{\omega }{2}{‖\boldsymbol{G}‖}_{{\rm{F}}}^{2}\\ {\rm{s}}.{\rm{t}}.{\rm{ }}{\rm{ }}{\boldsymbol{G}}^{{\rm{T}}}\boldsymbol{1}=\boldsymbol{1}, \boldsymbol{G}\ge \boldsymbol{0}\end{array} $

(6)

2 模型优化与求解

针对式（6）所示模型，本文设计了如下的优化求解算法。虽然式（6）具有较多变量，整体上非凸的，但是固定其他变量时，其每个变量的子问题都是凸的，并且具有闭合解。因此，本文使用交替方向乘子算法（ADMM）^[17]将模型函数分离成具有闭合解的独立子问题。引入辅助变量$ {\boldsymbol{Q}}^{m}\in {\mathbb{R}}^{n\times n} $和$ {\boldsymbol{P}}^{m}\in {\mathbb{R}}^{n\times n} $，使得式（6）是可分离的，得到式（7）所示形式：

$ \begin{array}{l}\underset{\boldsymbol{Z}, \boldsymbol{P}, \boldsymbol{Q}, \boldsymbol{E}, \boldsymbol{r}, \boldsymbol{G}}{{\rm{m}}{\rm{i}}{\rm{n}}}\sum\limits _{m=1}^{M}\left(\frac{{\left({r}^{m}\right)}^{2}}{2}{‖{\boldsymbol{S}}^{m}-{\boldsymbol{S}}^{m}{\boldsymbol{Z}}^{m}-{\boldsymbol{E}}^{m}‖}_{{\rm{F}}}^{2}+\lambda {‖{\boldsymbol{E}}^{m}‖}_{{\rm{2, 1}}}\right)+\\ \gamma {‖\boldsymbol{Q}‖}_{{\rm{2, 1}}}+\delta \sum\limits _{i, j=1}^{n}{‖{\boldsymbol{P}}_{i}-{\boldsymbol{P}}_{j}‖}_{F}^{2}{G}_{ij}+\varGamma {‖\boldsymbol{1}-\boldsymbol{r}‖}_{{\rm{F}}}^{2}+\frac{\omega }{2}{‖\boldsymbol{G}‖}_{{\rm{F}}}^{2}\\ {\rm{s}}.{\rm{t}}.{\rm{ }}{\rm{ }}{\boldsymbol{Z}}^{m}={\boldsymbol{P}}^{m}, {\boldsymbol{Z}}^{m}={\boldsymbol{Q}}^{m}, {\boldsymbol{G}}^{{\rm{T}}}\boldsymbol{1}=\boldsymbol{1}, \boldsymbol{G}\ge \boldsymbol{0}\end{array} $

(7)

其中：$ \boldsymbol{P}=[{\boldsymbol{P}}^{1}, {\boldsymbol{P}}^{2}, \cdots , {\boldsymbol{P}}^{M}] $；$ \boldsymbol{Q}=[{\boldsymbol{Q}}^{1}, {\boldsymbol{Q}}^{2}, \cdots , {\boldsymbol{Q}}^{M}] $。将式（7）中的约束条件进一步转化为式（8）所示的增广拉格朗日函数：

$ \begin{array}{l}{l}_{({\boldsymbol{G}}^{{\rm{T}}}\boldsymbol{1}=\boldsymbol{1}, \boldsymbol{G}\ge \boldsymbol{0})}(\boldsymbol{Z}, \boldsymbol{P}, \boldsymbol{Q}, \boldsymbol{E}, \boldsymbol{r}, \boldsymbol{G})=\\ \sum\limits _{m=1}^{M}\left(\frac{{\left({r}^{m}\right)}^{2}}{2}{‖{\boldsymbol{S}}^{m}-{\boldsymbol{S}}^{m}{\boldsymbol{Z}}^{m}-{\boldsymbol{E}}^{m}‖}_{{\rm{F}}}^{2}+\lambda {‖{\boldsymbol{E}}^{m}‖}_{{\rm{2, 1}}}\right)+\\ \gamma {‖\boldsymbol{Q}‖}_{{\rm{2, 1}}}+\delta \sum\limits _{i, j=1}^{n}{‖{\boldsymbol{P}}_{i}-{\boldsymbol{P}}_{j}‖}_{{\rm{F}}}^{2}{G}_{ij}+\varGamma {‖\boldsymbol{1}-\boldsymbol{r}‖}_{{\rm{F}}}^{2}+\\ \frac{\omega }{2}{‖\boldsymbol{G}‖}_{{\rm{F}}}^{2}+f(\boldsymbol{Z}, \boldsymbol{P}, \boldsymbol{Q}, {\boldsymbol{Y}}_{1}, {\boldsymbol{Y}}_{2}, \mu )\end{array} $

(8)

其中：$ f\left(\boldsymbol{Z}, \boldsymbol{P}, \boldsymbol{Q}, {\boldsymbol{Y}}_{1}, {\boldsymbol{Y}}_{2}, \mu \right)=-\frac{1}{2\mu }\sum\limits _{m=1}^{{\rm M}}\left({‖{Y}_{1}^{m}‖}_{{\rm{F}}}^{2}+{‖{Y}_{2}^{m}‖}_{{\rm{F}}}^{2}\right)+ $$ \frac{\mu }{2}{‖{\boldsymbol{Z}}^{m}-{\boldsymbol{P}}^{m}+\frac{{Y}_{1}^{m}}{\mu }‖}_{{\rm{F}}}^{2}+\frac{\mu }{2}{‖{\boldsymbol{Z}}^{m}-{\boldsymbol{Q}}^{m}+\frac{{Y}_{2}^{m}}{\mu }‖}_{{\rm{F}}}^{2}, \mu >0 $是惩罚系数；$ {Y}_{1}^{m} $和$ {Y}_{2}^{m} $是拉格朗日乘子。本文使用ADMM对该模型进行优化求解，即通过固定其他变量来更新其中一个变量的方式最小化$ l $。最终，得到各变量的迭代公式如下：

$ \begin{array}{l}{\boldsymbol{Z}}^{m, k+1}={\left({\left({\boldsymbol{S}}^{m}\right)}^{{\rm{{\rm T}}}}{\boldsymbol{S}}^{m}+2\mu I/{\left({r}^{m, k}\right)}^{2}\right)}^{-1}\\ \left({\left({\boldsymbol{S}}^{m}\right)}^{{\rm{{\rm T}}}}\left({\boldsymbol{S}}^{m}-{\boldsymbol{E}}^{m, k}\right)+\frac{\mu \left({P}^{m, k}+{Q}^{m, k}\right)-{Y}_{1}^{m, k}-{Y}_{2}^{m, k}}{{\left({r}^{m, k}\right)}^{2}}\right)\end{array} $

$ {\boldsymbol{P}}^{k+1}=\left(\mu {\boldsymbol{Z}}^{k+1}+{Y}_{1}^{k}\right){\left(4\delta {\boldsymbol{L}}_{{G}^{k}}+{\mu }_{k}I\right)}^{-1} $

$ {\boldsymbol{Q}}^{k+1}={\varTheta }_{\frac{\gamma }{{\mu }_{k}}}\left({\boldsymbol{Z}}^{k+1}+{Y}_{2}^{k}/{\mu }_{k}\right) $

$ {\boldsymbol{E}}^{m, k+1}={\varTheta }_{\frac{\lambda }{({r}^{m, k}{)}^{2}}}\left({\boldsymbol{S}}^{m}-{\boldsymbol{S}}^{m}{\boldsymbol{Z}}^{m, k+1}\right) $

$ {r}^{m, k+1}=\frac{2\varGamma }{{‖{\boldsymbol{S}}^{m}-{\boldsymbol{S}}^{m}{\boldsymbol{Z}}^{m, k+1}-{\boldsymbol{E}}^{m, k+1}‖}_{{\rm{F}}}^{2}+2\varGamma } $

$ {G}_{i}^{k+1}=\frac{1+\sum\limits _{j=1}^{\xi }{\widehat{u}}_{ij}}{\xi }(1-{u}_{i}{)}_{+} $

其中：$ {\boldsymbol{L}}_{{G}^{k}} $是$ {G}^{k} $的拉普拉斯矩阵，$ {\boldsymbol{L}}_{{G}^{k}}={\boldsymbol{D}}_{{G}^{k}}-{\boldsymbol{G}}^{k} $，度矩阵为$ {\boldsymbol{D}}_{{G}^{k}}=\sum\limits _{j=1}^{n}{G}_{ij} $；$ {\varTheta }_{\frac{\gamma }{{\mu }_{k}}}\left({\boldsymbol{Z}}^{k+1}+{Y}_{2}^{k}/{\mu }_{k}\right) $表示$ {l}_{{\rm{2, 1}}} $范数具有参数$ \gamma /{\mu }_{k} $在$ \left({Z}^{k+1}+{Y}_{2}^{k}/{\mu }_{k}\right) $上的最小化操作算子；运算符$ {\left(X\right)}_{+} $表示将$ X $中的负元素变为0，同时保留其余元素；$ {\boldsymbol{u}}_{i}\in {\mathbb{R}}^{n\times 1} $是向量，它的第$ j $个元素是$ {u}_{i, j}=\delta {‖{\boldsymbol{P}}_{i}-{\boldsymbol{P}}_{j}‖}_{F}^{2}/\omega $；$ {\widehat{\boldsymbol{u}}}_{i} $表示将列$ {\boldsymbol{u}}_{i} $中的元素按照升序排列。由于式（8）中每个子问题都是凸的，因此算法满足均衡条件^[21]。具体的优化过程如算法1所示。

算法1  式（8）所示模型优化过程

输入  多层网络的邻接矩阵$ \boldsymbol{A}=\{{\boldsymbol{A}}^{1}, {\boldsymbol{A}}^{2}, \cdots , {\boldsymbol{A}}^N\} $，$ {\boldsymbol{A}}^{i}\in $ $ {\mathbb{R}}^{n\times n} $；参数$ \delta $、$ \gamma $、$ \lambda $、$ \omega $，$ \boldsymbol{r}=\left[\frac{1}{M}, \frac{1}{M}, \cdots , \frac{1}{M}\right] $

输出  $ {\boldsymbol{Z}}^{m}, \boldsymbol{P}, \boldsymbol{Q}, {\boldsymbol{E}}^{m}, \boldsymbol{G} $，r

初始化  $ {Z}^{m, 0}={Y}_{1}^{m, 0}={Y}_{2}^{m, 0}={P}^{0}={Q}^{0}={E}^{m, 0}={G}^{0}=0 $

$ {\mu }_{0}={10}^{‒3}, {\mu }_{{\rm{m}}{\rm{a}}{\rm{x}}}={10}^{10}, \rho =1.5, \tau ={10}^{‒4}, \varGamma =1, $

$ {\rm{m}}{\rm{a}}{\rm{x}}{\rm{I}}{\rm{t}}{\rm{e}}{\rm{r}}=100, k=0 $

For i=1∶n do

$ {{\rm{P}}}^{{\rm{i}}}\Leftarrow {\rm{F}}{\rm{i}}{\rm{n}}{\rm{d}} $-$ {\rm{G}}{\rm{e}}{\rm{o}}{\rm{d}}{\rm{e}}{\rm{s}}{\rm{i}}{\rm{c}} $-$ {\rm{D}}{\rm{i}}{\rm{s}}{\rm{t}}{\rm{a}}{\rm{n}}{\rm{c}}{\rm{e}}{\rm{s}}\left({{\rm{A}}}^{{\rm{i}}}\right) $；

$ {{\rm{S}}}^{{\rm{i}}}={\rm{e}}{\rm{x}}{\rm{p}}\left(-\frac{{{\rm{P}}}^{{\rm{i}}}\circ {{\rm{P}}}^{{\rm{i}}}}{2{{\rm{ \mathsf{ σ} }}}_{{\rm{s}}}^{2}}\right)\text{;} $

end for

While不收敛do

$ {\rm{j}} $=$ 1; $

更新$ {{\rm{Z}}}^{{\rm{m}}, {\rm{k}}+1}{\rm{、}}{{\rm{P}}}^{{\rm{k}}+1}{\rm{、}}{{\rm{Q}}}^{{\rm{k}}+1}{\rm{、}}{{\rm{E}}}^{{\rm{m}}, {\rm{k}}+1}{\rm{、}}{{\rm{r}}}^{{\rm{m}}, {\rm{k}}+1}{\rm{、}}{{\rm{G}}}^{{\rm{k}}+1} $；

If $ {\rm{j}}== $1 then $ {\rm{\Gamma }} $=$ {\rm{m}}{\rm{a}}{\rm{x}}\{{{\rm{\Gamma }}}^{1}, {{\rm{\Gamma }}}^{2}, \cdots , {{\rm{\Gamma }}}^{{\rm{{\rm M}}}}\} $；

Where $ {{\rm{\Gamma }}}^{{\rm{m}}} $= $ {‖{{\rm{S}}}^{{\rm{m}}}-{{\rm{S}}}^{{\rm{m}}}{{\rm{Z}}}^{{\rm{m}}, {\rm{k}}+1}-{{\rm{E}}}^{{\rm{m}}, {\rm{k}}+1}‖}_{{\rm{F}}}^{2}, {\rm{m}}\in [1, {\rm{{\rm M}}}]; $

End if

更新拉格朗日乘子：

$ {{\rm{Y}}}_{1}^{{\rm{m}}, {\rm{k}}+1}={{\rm{Y}}}_{1}^{{\rm{m}}, {\rm{k}}}+{{\rm{ \mathsf{ μ} }}}_{{\rm{k}}}({{\rm{Z}}}^{{\rm{m}}, {\rm{k}}+1}-{{\rm{P}}}^{{\rm{m}}, {\rm{k}}+1}); $

$ {{\rm{Y}}}_{2}^{{\rm{m}}, {\rm{k}}+1}={{\rm{Y}}}_{2}^{{\rm{m}}, {\rm{k}}}+{{\rm{ \mathsf{ μ} }}}_{{\rm{k}}}({{\rm{Z}}}^{{\rm{m}}, {\rm{k}}+1}-{{\rm{Q}}}^{{\rm{m}}, {\rm{k}}+1}); $

更新$ {{\rm{ \mathsf{ μ} }}}_{{\rm{k}}+1}:{{\rm{ \mathsf{ μ} }}}_{{\rm{k}}+1}={\rm{m}}{\rm{i}}{\rm{n}}({{\rm{ \mathsf{ μ} }}}_{{\rm{m}}{\rm{a}}{\rm{x}}}-{\rm{ }}{\rm{ \mathsf{ ρ} }}{{\rm{ \mathsf{ μ} }}}_{{\rm{k}}}); $

更新$ {\rm{k}}:{\rm{k}}={\rm{k}}+1; $

更新迭代次数$ {\rm{j}}:{\rm{j}}={\rm{j}}+1; $

检查收敛条件：Z、P、Q、E、G、r在连续2次迭代的差值小于$ {\rm{ \mathsf{ τ} }} $，或者迭代次数大于maxIter；

End while

对G进行谱聚类，得到最终的聚类结果；

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所示。

3.2 参数设置

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

3.3 比较方法

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

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

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

3.4 评估指标

采用以下3种广泛使用的评估指标：纯度（Purity）^[28]，规一化互信息（NMI）^[29]，准确性（ACC）^[30]。这3个指标都提供了一种定量方法来比较计算的社团聚类$ \varOmega =\{{\varphi }_{1}, {\varphi }_{2}, \cdots , {\varphi }_{\kappa }\} $和真实标签$ C=\{{c}_{1}, {c}_{2}, \cdots , {c}_{\kappa }\} $。

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

$ {P}_{{\rm{P}}{\rm{u}}{\rm{r}}{\rm{i}}{\rm{t}}{\rm{y}}}(\varOmega , C)=\frac{1}{n}\sum\limits _{k}\underset{j}{{\rm{m}}{\rm{a}}{\rm{x}}}\left|{\varphi }_{k}\bigcap {c}_{j}\right| $

(9)

其中：$ n $是节点总数；$ \left|{\varphi }_{k}\bigcap {c}_{j}\right| $表示$ {\varphi }_{k} $与$ {c}_{j} $的交集的节点数。

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

$ {N}_{{\rm{N}}{\rm{M}}{\rm{I}}}(\varOmega , C)=\frac{I(\varOmega , C)}{\frac{\left|H\left(\varOmega \right)+H\left(C\right)\right|}{2}} $

(10)

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

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

$ {A}_{{\rm{A}}{\rm{C}}{\rm{C}}}=\frac{\sum\limits _{i=1}^{n}\delta ({\zeta }_{i}, {\rm{m}}{\rm{a}}{\rm{p}}({\psi }_{i}\left)\right)}{n} $

(11)

其中：$ \delta (x, y) $是delta函数，即当x和y相等时，$ \delta (x, y)=1 $，否则等于0；$ {\rm{m}}{\rm{a}}{\rm{p}}\left({\psi }_{i}\right) $是将每个社团标签$ {\psi }_{i} $映射到数据集中等效标签的映射函数。

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

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

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

3.6 参数分析

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

3.7 社团检测实验结果

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

4 结束语

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