基于卷积网络的社区检测算法研究综述

摘要：社区检测是将网络中特征相同的成员聚合在一起，社区内成员关系紧密，社区之间成员关系稀疏。社区检测在数据挖掘中具有重要意义。近年来由于大数据和深度学习的高速发展，使得深度学习在社区检测模型中有了显著发展。卷积神经网络在社区检测领域的应用调查对社区检测模型具有重要意义，通过对卷积网络和图卷积网络社区检测方法的归纳总结，总结现有方法的优缺点。最后，通过这个快速增长的深度学习领域提出亟待解决的问题。

关键词：社区检测；数据挖掘；神经网络；图卷积网络；重叠社区；拓扑不完全网络

中图分类号：TP311      文献标识码：A

文章编号：1009-3044（2024）24-0097-04

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

0 引言

自从2002年以来，Girvan和Newman[1]打开了图划分的新方向。在过去十年里，计算机科学的研究者通过利用静态和动态网络，小型和大型网络的网络拓扑结构和语义信息广泛的研究社区检测算法。

社区检测是一个越来越具有现实意义的研究领域。俗话说“物以类聚，人以群分”。基于六度分离理论，世界上任何人都能够通过6个熟悉的人知道其他人。这个俗语和六度分离理论都暗示了社交网络的惊人联系。“物以类聚，人以群分”强调了人们倾向于与具有相似兴趣、背景或特征的人聚集在一起的趋势。而六度分离理论则指出了人与人之间的连接并不像我们想象的那么遥远，即使我们可能认识的人数很少，通过社交网络中的连接，我们仍然可以与世界上任何一个人建立联系。这两者共同揭示了社会网络的奇妙和复杂性，以及人际关系的密切联系。比如，社会网络中典型的购物网站，社区检测挖掘商家与用户、商品与商品、用户与用户、品牌与商家之间的关系，以此来推广产品和提供个性化服务。 社区检测应用在代谢网络和蛋白质网络中揭示生物体内复杂的调控机制和生物学过程，有助于理解各种疾病的发生机制。因此，社区检测在数据挖掘和网络分析中非常重要。

许多传统社区检测技术，如光谱聚类和统计推断能够应用在小型网络和简单社区检测模型中。然而，包含丰富非线性信息的真实世界网络因为具有复杂的拓扑和高维特征，使得传统模型不太适用于实际应用。随着大数据的深度学习技术的蓬勃发展，越来越大的规模，高稀疏性，复杂结构，动态网络在现实世界中的场景被探索。传统社区检测方法解决不了的问题使用深度学习技术能够很好地解决，包括网络中非线性关系的处理；从高维网络数据到低维网络数据的转化；社区检测时更有效的保留网络结构的复杂性等。因此，社区检测的深度学习方法是一个新的趋势，包括卷积网络社区检测（Convolutional Neural Networks ，CNNs）、生成对抗网络（Generative Adversarial Networks，GAN）、深度非负矩阵因子（Deep Non-negative Matrix Factorization，DNMF）、深度嵌入（Deep Embeddings，DE）等。卷积网络作为深度学习的代表，在复杂网络的社区检测中占有很重要的位置。卷积网络包括卷积神经网络和图卷积网络（Graph Convolutional Networks ，GCNs）[2]。

卷积网络的一般框架是复杂结构关系高维数据到低维数据的学习，能够自动学习和提取非结构特征，从而在进行社区检测时提供更多有效的知识。除此之外，在提取特征进行社区进测时，卷积网络能够将节点、边、邻居节点或者多个网络结构的信息融合并进行更加有效的社区检测。

1 社区检测

定义1：网络 给定一个基本网络[G（V，E）]，且[V={V1，V2，...，Vn}]是节点集合，[E=eijni，j=1]代表节点之间的边集。[N（vi）={u∈V|（vi，u）∈E}]定义为[vi]的邻居节点，[A=[aij]]定义为[n×n]维邻接矩阵。如果[eij=E]则[aij=1]，否则[aij=0]。如果[aij≠aji]，[G]是一个有向网络，否则[G]是一个无向网络。如果[aij]由[wij∈W]加权，则[G=（V，E，W）]是权重网络，否则就是非权重网络。如果[aij]的值是+1和-1，[G]是信号网络。如果节点[vi∈V]归属于[xi∈X∈ℝn×d]，[G=（V，E，X）]是属性网络，否则就是无属性网络。

定义2：社区 给定一组社区[C={C1，C2，…，CK}]，每个社区[Ck]是图[G]的一个分区，它保持区域结构和聚类性质[3]。也就是说，社区[Ck]中的成员都具有相同的属性和结构。社区聚集到社区[Ck]的节点[vi]应当满足条件：社区内部节点的度要超过外部节点的度。假设[Ck⋂Ck'=∅]，[（∀k，k'）]，[C]表示离散社区，否则就表示重叠社区。

定义3：社区检测输入 深度学习模型将网络拓扑结构和网络属性作为输入。节点和边形成的拓扑能够在矩阵中加以表示，比如邻接矩阵[A]，信号邻接矩阵[A（+，-）]，以及类似模块矩阵[B]的测量矩阵。网络属性表示网络实体额外的信息，例如节点属性[X]。

社区检测输出 社区检测输出方法的目标是输出一组离散或者重叠社区。比如，学生俱乐部只允许一个学生加入其中的一个俱乐部，这是离散社区的典型代表。参与社交网络中多个圈子的用户，这是重叠社区的典型代表。部分重叠社区的检测方法可以检测离散社区。

2 基于卷积神经网络的社区检测算法

CNNs是一类针对图像数据等网格状拓扑数据提出的特殊的前馈深度神经网络（Deep Neural Network，DNN），其卷积层减少计算成本和池化操作来确保CNN特征表示中的稳健性。现有的社区检测方法实现了具有严格数据输入限制的CNN模型，见图1。

传统的社区检测是深度学习模型中的无监督学习任务，现实中网络可能边缺失，这种拓扑结构不完整的网络，进行社区检测时会降低其准确度。为此，Xin等[4]提出了第一个针对不完全拓扑网络结构的有监督CNN社区检测模型。通过设计一个结构化深度卷积神经网络模型，以便能够更好地检测网络拓扑结构不完整网络的社区。通过添线性或者星型预处理方法来调整网络结构，该深度卷积神经网络有两个卷积层和一个全连接层组成。然后在每个特征图上应用最大池化运算，最后第二卷积层的最大池化操作之后的特征图都连接到全连接层，逐步将不完整拓扑结构网络的特征补充完整。最后一个连接层[f]为每个节点[vi]更新社区：

[oki=σ（bfk+Wfkh（2）i）]                  （1）

其中[σ]表示激活函数，[Wfk]和[bfk]第[k]个神经元的权重和偏差，[h（2）i]是前两个卷积层输出节点表示向量。该模型的损失函数为：

[L=12i∥oi-yi∥22=12ik（oki-yii）2]  （2）

这里[yi]表示节点[vi]的标记向量，[yki∈{0，1}]表示[vi]是否属于第[k]个社区。该模型社区检测中，用10%的标记节点实现了约80%的准确率，表明使用线性和星型预处理方法能够有效提高社区检测的准确率。

大规模社交网络具有高稀疏性，Sperli[5]设计了一个可以处理大维度和高稀疏性的卷积神经网络，全连接层由[k]个输出神经元组成，每个神经元对应一个特定的社区。每个特征图中的每条条目都连接到全连接层上的所有[k]个神经元，表示为：

[okn=relu（bf+WfkqC1C2n）]                    （3）

其中[okn]是第[k]层神经元的值，表示节点[n]属于第[k]个社区的概率，[bf]，[Wfk]和[qC1C2n]分别是统计偏差、权重矩阵和第二卷积层输出。同样为了处理维数和稀疏性问题，Santo等人[6]引入了SparseConv2D算子修改CNN的输入层，用来更有效的在稀疏矩阵上执行卷积。虽然神经卷积网络在社区检测上取得了一定的效果，但是根据现有的模型，都无法处理社区的重叠密集情况，其中一个节点可能属于多个社区。GCN在处理图数据具有很强的优势，其最近的发展表明其有能力在图形的数据中建模和捕捉复杂关系。因此，越来越多的社区检测方法开始关注GCN。

3 基于图卷积网络的社区检测算法

GCN是基于CNNs图结构数据提出的，并在频谱滤波器的一阶近似上执行。GCNs的分层传播规则是：

[H（l+1）=σ（D-12AD-12H（l）W（l））]            （4）

其中[l]层的潜在表示保存在矩阵[H（l）（X（0）=H）]中，通过激活函数[σ（⋅）]和特定层训练权重矩阵[W（l）]中；[A=A+In]和[In]表示单位矩阵；[Dij=jaij]且[aij∈A]。

GCNs进行社区检测是在深度图卷积层上全局提取复杂特征并聚合节点邻居信息。有两类基于GCNs的社区检测算法[7]：有监督/半监督算法以及无监督算法。GCNs使用传统深度学习算子来进行社区检测，比如用于统计推断的SBMs，用于频谱分析的拉普拉斯矩阵和用于信念传播的概率图模型 [8] 。比如线形图神经网络（Line Graph Nerual Network，LGNN）是一个有监督的社区检测模型，改进了SBNs并减少了计算开销，将非回溯算子与信念传播的消息传递规则相结合，学习网络中的节点表示特征 。激活函数softmax识别条件概率：节点[vi]属于社区[Ck（oi，k=p（yi=ck|Θ，G））]，并且最小化社区标签所有可能的组合交叉熵损失[SC]：

[L（Θ）=minπ∈SC-ilogoi，π（yi）]                  （5）

GCN本身并不是为了进行社区检测，因此模型并不能准确进行社区分类。为了弥补这个差距，一种半监督的社区GCN检测模型MRFasGCN通过使用马尔科夫随机场进行社区检测，同时能够将社区检测结果进行优化。为了实现无监督的社区检测，一个基于GCN框架的网络表示学习SGCN模型设计了局部标签采样模型[9]并确定社区检测的结构中心，利用图卷积网络进行局部特征提取，通过将标签采样模型和GCN集成到一个无监督框架中，SGCN在训练每个没有先验标签节点的社区成员身份时融合拓扑和属性来进行社区检测。基于图神经网络的重叠社区检测[10]（Neural Overlapping Community Detection，NOCD）模型，是一个无监督端到端的深度学习模型，将GCN模型和伯努利-泊松（Bernoulli-Poisson，BP）概率相结合，使用ReLU激活函数应用在输出层，BP模型的负对数似然对从属矩阵使用最小化参数进行优化，GNN为相邻节点输出相似的社区隶属向量。邻域聚合算法将图卷积公式化为对称拉普拉斯平滑运算，聚合节点与邻居的特征信息。但是这种算法在神经网络深度增加时会导致过度平滑的问题。因此Hu等人[11]设计了图卷积梯形网络（Graph Convolutional Ladder-shape Networks，GCLN），这是一种新的图神经网络结构，使用上下文特征通道构建具有收缩和扩张路径的对称结构，该梯形架构允许网络直接将上下文信息从浅层传输、融合到更深层，克服过度平滑，扩展神经网络的规模。分层传播等式如下：

[H（l+1）=s（D-12AD-12H（l）W（l））]                  （6）

独立性提升图纠缠网络[12]（Independence Promoted Graph Disentangled Network，IPGDN）将现实网络中纠缠的潜在因素独立表示出来，同时增强节点表示之前的独立性，以降低检测邻域的难度。邻域路由中的Hilbert-Schmidt独立准则（HSIC）正则化支持IPGDN。