社区检测方法综述：从统计建模到深度学习

摘要

社区检测是网络分析的一项基本任务，旨在将网络划分为多个子结构，以帮助揭示其潜在功能。 社区检测已被广泛研究并广泛应用于许多现实世界的网络问题。 社区检测的经典方法通常利用概率图模型并采用各种先验知识来推断社区结构。 随着网络方法试图解决的问题和要分析的网络数据变得越来越复杂，新的方法也被提出和开发，特别是那些利用深度学习并将网络数据转换为低维表示的方法。 尽管最近取得了所有进展，但仍然缺乏对社区检测的理论和方法基础的深刻理解，这对于网络分析领域的未来发展至关重要。 在本文中，我们开发并提出了网络社区发现方法的统一架构，以表征社区检测领域的最新技术。 具体来说，我们对现有的社区检测方法进行了全面的回顾，并引入了一种新的分类法，将现有的方法分为两类，即概率图模型和深度学习。 然后我们详细讨论这两个类别中每种方法背后的主要思想。 此外，为了促进社区检测的未来发展，我们发布了来自多个问题领域的多个基准数据集，并重点介绍了它们在各种网络分析任务中的应用。 最后，我们讨论了该领域的挑战，并对未来研究的可能方向提出了建议。

1 简介

网络科学是利用计算机科学、数学和物理学的理论和技术对网络形式的复杂系统进行研究。 特别是，网络结构[1]（参见图1中的示例）已经在子图、网络模块和社区的概念下得到了广泛的研究。 网络结构识别或社区检测是将网络中的节点划分为组，组内节点连接密集，不同组内节点连接稀疏。 挖掘网络结构也是揭示和理解复杂网络系统的组织原理和运行功能的关键。 例如，社区检测已应用于建议[2, 3]、异常检测[4, 5]、恐怖组织识别[6]，仅举几例。

图1： 显示社区结构的说明性示例（Zacharys 空手道俱乐部网络[7])。 该网络的节点分为两组，大多数连接属于组内，只有少数连接属于组间。

人们还致力于网络结构特性的分析，例如小世界效应（即节点之间的平均距离较短[8])和无标度特性（即节点度的分布遵循幂律分布[9])。

已经提出了许多社区检测算法，其中大多数仅利用网络拓扑信息。 它们包括层次聚类[10][11]，模块化优化[12][13] [14]、谱聚类[15] [16]和统计推断[17] [18]. 除了网络拓扑之外，还开发了新的方法来利用节点语义或节点属性来提高生成社区的质量，同时为结果提供解释。 其中包括启发式优化（多目标）[19][20]、矩阵分解[21] [22] 和贝叶斯模型 [23]。 随着越来越复杂的网络问题的解决，来自多个来源的复杂网络数据（例如网络拓扑和节点语义）必须有效地集成。 因此，这些传统方法很难对非常高维度和不同属性的数据进行有效的数据融合。 最近采用深度学习技术来处理高维网络数据并学习网络结构的低维表示。 示例包括基于自动编码器 [24] [25] 和生成对抗方法 [26] [27] 的方法。

社区检测的一个重要且有效的想法是学习给定网络的网络结构的充分表示。 我们将这种方法称为基于学习的社区检测。 这些方法包括基于模型的生成模型。 最流行和最具代表性的例子是随机块模型（SBM）[28]，它通过将网络的生成过程形式化为一系列严格的概率分布来检测社区。 为了提高 SBM [29][30] 的性能，引入了多项扩展和改进。 另一种基于模型的学习方法采用马尔可夫随机场（MRF）（一种无向图模型）来利用网络中的邻域结构[31]。 基于学习的方法的最新发展利用了深度学习的低维表示能力。 例如，卷积神经网络（CNN）[32]利用卷积和池化操作来降低网络数据的维度，从而有效地发现网络中的社区。 图卷积网络（GCN）[33]继承了CNN的优点，直接对网络结构化数据进行操作，也被探索用于推导社区表示[34]。

尽管人们一直在努力开发有效的社区发现方法[35, 36]，但人们仍然缺乏对社区发现的理论和方法基础的理解，特别是基于学习的社区发现。 为了弥补这一差距，在本文中，我们将对现有代表性方法进行综合调查。 我们特别关注两种通用方法，一种基于概率建模，另一种基于深度学习。 我们首先详细描述每一行工作，并对方法进行彻底的审查和比较。 然后我们考虑社区检测在不同领域的几种应用。 最后，我们讨论了网络分析领域的一些关键挑战以及未来有价值的研究方向。

我们调查的主要目标之一是为现有方法提供新的视角，以帮助更好地理解社区检测的基本问题和支持技术。 我们的调查与已发表的调查在三个方面有所不同。 首先，我们通过关注学习（社区建模和社区检测的核心问题）来总结现有方法，而现有评论[37][38]一般讨论按时间顺序排列的方法现有方法的发展。 其次，我们提出了社区检测方法发展的最新趋势，即从统计建模到深度学习，而其他方法主要关注个体技术，例如进化计算[39]、统计推理[40]或深度学习[41]。 第三，我们提出了一个统一的系统架构来表征现有方法，这为基于统计建模和深度学习的方法提供了新颖且综合的视角，这远远超出了一些现有的调查[42] [43]。 最后但并非最不重要的一点是，在深度学习时代，随着网络数据变得越来越复杂，各种想法和技术被提出，迫切需要进行调查以全面揭示现有社区检测方法之间的内在关系。

为了向对网络科学和网络数据分析感兴趣的研究人员和从业者提供一般指导，我们在这项工作中做出了独特的贡献，总结如下。

• 我们提出了基于学习的社区检测最全面和广泛​​的概述，并将其分为两类：概率图模型和深度学习。 据我们所知，这是首次从学习的角度进行社区发现的尝试。 它为理解社区检测背后的直觉提供了坚实的基础，并且可以用作设计和利用不同社区检测方法的指南。

• 我们对基于学习的社区检测方法进行了全面的理论分析，讨论了它们的异同，确定了尚未解决的关键挑战，并指出了未来发展的五个方向。

• 我们收集了基于学习的社区检测的丰富资源，包括最先进的基准数据集和应用程序。

本调查文件的其余部分组织如下。 第 2 节给出了现有社区检测方法的基本知识和分类。 第 3 节介绍了社区检测统计建模研究进展的技术概述。 第四节概述了基于深度学习的社区检测的研究。 第五节讨论社区检测的应用。 我们在第 6 节中提出了有前景的未来研究方向，并在第 7 节中进行了总结。

2 预备知识和分类

我们首先介绍术语和符号，然后提出我们将在本文中讨论的社区检测方法的分类。

2.1 定义、术语和符号

图2： 社区检测方法的分类细分。

定义1。 网络。 一个网络 $G=(V,E,X)$ 由 $n$ 节点 $V=\{v_1,v_2,\mathrm{\dots },v_n\}$、$m$ 边 $E=\{e_{ij}\}\subseteq V\times V$ 和一个节点 $v_i$ 上最大数量的属性 $q$ $x_i$组成，其中所有 $x_i$ 的集合会产生一个 $n\times q$ 属性矩阵 $X={(x_i)}_{n\times q}$。 $G$的拓扑结构可以通过$n\times n$邻接矩阵$A={(a_{ij})}_{n\times n}$来定义，其中$a_{ij}=1$ if $e_{ij}\in E$，或 0，否则。 如果 $a_{ij}=a_{ji}$，则 $G$ 是无向的，否则 [42] 是有向的。

定义2。 社区。 网络$G$包含$k$社区$𝒞=\{{𝒞}_1,{𝒞}_2,\mathrm{\dots },{𝒞}_k\}$，其中${𝒞}_i$是$G$的子图，并且${𝒞}_i$ 是密集连接的，而 ${𝒞}_i$ 和 ${𝒞}_j$ 之间的节点是稀疏连接的。 当 ${𝒞}_i\cap {𝒞}_j=\mathrm{\varnothing }\forall i,j$ 时，社区不重叠。

定义3. 社区检测。 给定一个网络$G$，社区检测就是设计一个映射$ℱ$，将$G$的每个节点$v_i$分配到至少一个网络中$k$社区，即标记$v_i$至少一个社区身份$c_i\in \{{𝒞}_1,{𝒞}_2,\mathrm{\dots },{𝒞}_k\}$。 同样，问题是导出节点 $C=(c_1,c_2,\mathrm{\dots },c_n)$ 的社区分配。

2.2 社区检测方法分类

为了帮助更好地理解现有的基于学习的方法并促进我们在本文其余部分的讨论，我们引入了社区检测方法的分类法（图2)，其中方法分为两种类别、概率图模型和深度学习。

基于概率图形模型的方法在社区生成中采用启发式或元启发式来发现网络社区。 这些方法通常采用一些网络结构模型来通过网络的边缘来描述实体（即节点）之间的依赖关系。 根据所使用的概率图模型的类型，社区检测可以进一步分为三大类：有向图模型、无向图模型和混合图模型。 具体来说，有向图模型主要基于隐藏变量（即样本中未观察到的变量），利用节点或块结构的相似性，生成网络中观察到的边；无向图模型通常基于场结构，利用一元势和成对势的约束（例如，附近节点之间的社区标签一致性）来发现社区；混合图模型通常将这两种模型转换为统一的因子图，以利用这两种模型进行社区检测。

基于深度学习的方法旨在利用新型面向社区的网络表示来识别社区结构。 它通过一些学习策略将网络数据从原始输入空间映射到低维特征空间来推导新的网络表示，具有计算复杂度低和并行化能力强的优点。 根据所使用的学习策略，基于深度学习的方法分为四大类：基于自动编码器、基于生成对抗网络、基于图卷积网络（GCN）以及集成图卷积网络和无向图模型。 具体而言，基于自动编码器的方法利用无监督自动编码器，将网络编码为潜在空间中的低维表示，并从低维表示重建网络及其社区结构。 基于生成对抗网络的方法采用对抗学习的思想。 他们通过生成器和鉴别器之间的对抗游戏来检测社区。 基于图卷积网络的方法通过网络拓扑上特征的传播和聚合来提取社区。 基于混合图形模型的方法将图形卷积网络和无向图形模型集成在一起，例如将马尔可夫随机场（MRF）层转换为 GCN，以利用这两种模型的优点。

3 使用概率图形模型进行社区检测

基于概率图模型的方法通常通过网络建模来检测社区，即利用图模型来解释网络的生成过程。 在本节中，我们将重点讨论三种通用方法：有向图模型、无向图模型以及集成有向图和无向图的混合图模型。

3.1 有向图形模型

我们将回顾最近用于社区检测的有向图模型的发展，包括随机块模型、主题模型和矩阵分解。 这些方法具有扎实的理论基础和良好的性能，得到了广泛的应用。

3.1.1 基于随机块模型的方法

随机块模型（SBM）是一种有效的网络块结构生成模型，首次采用统计建模进行社区发现[28]。 该方法使用节点隶属似然函数将网络中的节点概率性地分配给不同的社区（块结构），然后通过推断似然函数逐步推断节点成员资格的概率，以导出网络中的隐藏社区。 请注意，用于社区检测的 SBM 变体有多种，但它们的核心生成过程是相同的。 基本生成过程可以分为两个步骤：第一步是迭代地为网络中的每个节点分配社区，第二步是计算或更新由边连接的两个节点的概率。

以社交网络为例，SBM 可以用来捕获以社区分布作为隐变量的概率生成过程。 可以通过最大化节点社区成员资格的似然函数来重建社区。 在这个社交网络中，节点被划分为$k$个不相交的社区，概率为$\omega =\{{\omega }_1,\mathrm{\dots },{\omega }_k\}$。 假设有两个节点$v_i$和$v_j$分别属于两个社区${𝒞}_r$和${𝒞}_s$，分别用$c_{ir}$和$c_{js}$。 节点 $v_i$ 和 $v_j$ 通过边连接的概率，即 $a_{ij}$（0 或 1），服从参数为 ${\pi }_{rs}$ 两个社区中节点之间的链接概率的使用使得模型能够灵活地适应各种类型的网络结构[44]。 网络发电分布可以定义为：

$$P(C|\omega )=\prod _{i=1}^n\mathrm{Multinomial}(c_i;1,\omega )=\prod _{i=1}^n\prod _{r=1}^k{\omega }_r^{c_{ir}},$$ (1)

(2)

其中$C=(c_1,c_2,\mathrm{\dots },c_n)$表示节点的社区分配，$\pi ={({\pi }_{rs})}_{k\times k}$表示社区连接概率矩阵。 那么，似然函数可以描述为：

(3)

基于似然函数，可以使用吉布斯采样和期望最大化（EM）算法来获取模型参数，例如$\omega$和$\pi$。 最后，我们可以通过社区之间的交互模型推导出社区划分。 基本SBM的时间复杂度为$O(n^2{k}^2)$，基于伯努利分布的SBM的社区发现过程如附录B[28]所示。 基本SBM的生成过程也可以采用泊松分布[45]。

后来，张等人。 [46]研究基础SBM中的隐藏类推断问题。 他们对合成网络上的三种推理方法（即启发式谱方法、平均场近似和置信传播）进行了比较研究。

混合会员 SBM。 由于基本的 SBM 仅适用于节点仅属于一个社区的假设，Airoldi et al。 [29]提出了一种混合成员资格随机块模型（MMSB），该模型将混合成员资格引入到随机模型中，使得一个节点可以属于多个社区。 MMSB 允许社区在有向网络上重叠，其中 $a_{i\to j}$ 指示是否存在从节点 $v_i$ 到 $v_j$ 的链接（箭头）。 对于每个节点 $v_i$,$c_i$ 服从多项式分布。 如果$v_i\in {𝒞}_r$和$v_j\in {𝒞}_s$，则社区连接概率${\pi }_{rs}$服从Beta分布，并且$a_{i\to j}\sim \mathrm{Multinomial}({\omega }_i)$、$a_{i\leftarrow j}\sim \mathrm{Multinomial}({\omega }_j)$，其中$\omega$是节点的混合成员资格参数。 社区之间的联系由伯努利分布表示。 MMSB 的联合分布可以表示为：

(4)

MMSB的时间复杂度为$O(n^{2}k)$，基于MMSB的社区发现过程在附录B[29]中描述，其中假设参数是通过推理方法估计的，例如作为EM。

原始的MMSB不擅长处理社区中节点的多种类型的信息，例如，节点可能代表基于不同社会关系而相互联系的人。 为了解决这个问题，Fan 等人.[47]提出了一种基于MMSB的新方法，称为Copula混合隶属随机块模型（cMMSB），将Copula函数引入到MMSB 用于对节点之间的依赖关系进行建模。 此外，Miller 等人 [48]通过将狄利克雷过程混合物引入有限混合物（MFM）的混合物来改进MMSB的推理。 Pal 等人 [49]提出了一种混合隶属度校正SBM，并开发了一种马尔可夫链蒙特卡罗（MCMC）后验分布的推理方法，以提高MMSB 的嵌入性能。 度数校正的SBM被广泛使用，我们将在接下来讨论。

表一： 基于SBM的社区检测总结，其中“AD $k$”描述了该方法是否可以自动确定社区的数量，即“是”或“否”。

Categories	Approaches	Sketches	Overlapping	AD $k$
Basic	SBM (1983) [28]	Propose a stochastic model for social network.	No	No
MMSB	MMSB (2008) [29]	Extend blockmodels for relational data to ones that capture mixed membership latent relational structure.	Yes	No
	cMMSB (2016)[47]	Combine an individual Copula function with MMSB with improved in capturing group interactions.	Yes	No
	MMDCB (2019)[49]	Propose a mixed membership degree-correct SBM and develop an inference method of the posterior distribution with Markov chain Monte Carlo (MCMC).	Yes	No
DCSBM	DCSBM (2012)[50]	Introduce expected values to basic SBM to adapt multi-edges and self-edges contained in social networks.	Yes	No
	sparseDCSBM (2017)[51]	Propose a spectral clustering algorithm with normalized adjacency matrix based on DCSBM.	No	Yes
	CMM (2018)[52]	Establish a convexified modularity maximization approach for estimating the hidden communities based on DCSBM.	No	No
	NCV (2018)[53]	Provide a network cross-validation approach to determine the hidden communities based on DCSBM.	No	No
DynSBM	dMMSB (2009)[54]	Propose a state space MMSB which can track across time dynamic evolution.	Yes	No
	DynamicSBM (2010)[55]	Propose a novel Bayesian approach for network tomographic inference buliding on MMSB and apply in dynamic network.	No	No
	DSBM (2011)[56]	Capture the evolution of community by modeling the transition of community memberships for individual nodes.	No	No
	DBTDP (2014)[57]	Propose a dynamic stochastic block model with temporal Dirichlet process for hidden community.	Yes	No
	SBTM (2015)[58]	Provide a local search algorithm for the inference procedure of time evolution.	No	No
	dDCSBM (2016)[59]	Propose a dynamic DCSBM to model and monitor dynamic networks that undergo a significant structural change.	No	Yes
	DPSBM (2019)[60]	Establish a fully Bayesian generation model with the heterogeneity of node degree.	No	Yes
	SNR-DSBM/ER (2020)[61]	Focus on estimating the location of a single change point in a dynamic stochastic block model and take a least squares criterion function for evaluating each point in time.	No	Yes
OSBM	OSBM (2011)[62]	Provide a global and local variational technique for discovering community.	Yes	No
	K-LAFTER (2018)[63]	Present a small-variance asymptotics based SBM for overlapping community detection.	Yes	Yes
	MNPAOCD (2020)[64]	Optimize the inference process and expect parameters in proceeding.	Yes	Yes
LSBM	LMBP (2015)[18]	Combine heterogeneous distribution with SBM to link community detection.	Yes	Yes
GNNSBM	DGLRFM (2019)[65]	Design a GNN-based overlapping SBM framework and can be adapted readily for other types of SBMs.	Yes	Yes

度数校正的 SBM。 Newman 等人 [30]推断基本SBM根据节点的度来划分节点，而节点的度通常是非均匀分布的。 为了适应可能的广泛度分布，他们提出了度校正SBM（DCSBM），它向每个节点引入一个度参数来缩放边缘概率并使预期度与观察到的度匹配。 网络$G$的概率函数定义如下：

(5)

其中${\pi }_{c_i{c}_j}$是邻接矩阵元素$a_{ij}$的期望值。

DCSBM 模型也有多种变体。 Gulikers 等人。 [51]提出了一种适用于稀疏网络的改进的DCSBM。 其他一些不同的努力是通过模型推理来改进和扩展 DCSBM。 陈等人。 [52]提出了一种凸化模块化最大化方法，用于估计 DCSBM 下的隐藏社区。 陈等人。 [53]提供了一种基于块式节点对分裂的网络交叉验证（NCV）方法，以确定 DCSBM 的隐藏社区。

动态 SBM。 与上述方法不同，基于SBM的动态网络分析也是一个相对活跃的领域。 杨等。 [56]提出了一种名为 DSBM 的动态随机块模型，它逐步更新概率模型以在大型动态稀疏网络中寻找社区。 具体来说，DSBM在预测中使用模型参数的分布而不是模型参数的最可能值，并提供离线推理和在线推理来估计参数。 DSBM 假设动态网络中的节点保持不变。 令$C_T=\{C^{(1)},C^{(2)},\mathrm{\dots },C^{(T)}\}$为所有节点在$T$个离散时间步上的社区分配的集合，模型的似然函数如下：

(6)

其中$W^{(t)}$和$C^{(t)}$表示给定时间步$t$的网络快照和节点的社区分配。 DSBM的时间复杂度为$O(nT+mT+k^{2}T)$，其生成过程如附录B[56]所示，

Tang 等人继DSBM之后，[57]将Dirichlet过程引入到SBM中，可以找到最优的进化群体数量，进而缓解进化问题。动态社交网络的固定社区数量。 徐等人。 [66]提出了一种名为随机块转移模型（SBTM）的新方法，其中包括动态网络的两个隐马尔可夫假设。 吴等人。 [67]提出了一种完整的贝叶斯生成模型，该模型结合了节点度的异质性来对动态复杂网络进行建模。 巴塔查吉等人。 [61] 通过动态社交网络中的变化点估计来优化 SBM。 受 MMSB 成功的启发，一些基于 MMSB 的动态 SBM 被提出。 Xing 等人.[55]提出了一种动态网络的变体MMSB模型。 傅等人。 [54]设计具有交叉时间的状态空间混合隶属度随机块模型。 此外，还存在基于DCSBM的方法。 威尔逊等人。 [59]提出了 DCSBM 的动态版本来建模和监控经历重大结构变化的动态网络。

其他。 除了上述方法之外，基本 SBM 还有其他几种可以重叠社区的扩展，如表 2 所示。 例如，OSBM 代表旨在查找重叠社区的 SBM，LSBM 表示扩展以查找链接社区的 SBM。 具体来说，Latouche 等人。引入具有全局和局部变分技术的OSBM。 金等人。 [64]提供了一个随机模型来适应每个社区中每个节点的相对重要性和期望程度，并改进了其使用的推理技术。

链接社区通常比节点社区更具信息性和直观性，因为链接通常具有唯一的身份，而节点可能具有多种角色。 例如，在社交网络中，大多数人属于多个社区，例如家庭或朋友，而两个人之间的联系通常出于主导原因而存在，这可能代表家庭关系或友谊。 此外，连接到一个节点的多个链路可以属于不同的链路社区，使得该节点可以被分配到多个链路社区。 他等人。 [18]将社区规模的异构分布（例如幂律分布）与SBM结合起来进行链接社区检测。 他们提出了链接社区的随机模型，并通过引入交互式二分方案来扩展该模型。 除了上述模型外，Mehta等人。 [65]将图神经网络引入SBM，首次将深度学习与SBM结合起来。

3.1.2 基于主题模型的方法

主题模型，例如潜在狄利克雷分配（LDA）[68]，是一种统计模型，能够对自然语言处理中文本背后的隐藏主题进行建模。 LDA 通过使用潜在变量对主题进行建模，这引起了人们的极大兴趣并已广泛用于检测社区。 主题模型可以分为两类：一类将网络结构建模为文档，另一类将网络属性（例如用户兴趣）建模以检测社区。

将网络结构建模为文档。 我们以LDA为例来描述第一类方法的原理。 具体来说，本组方法首先假设网络中的每个节点可能属于多个社区，因此将社区视为“主题”，将节点视为“文档”。 然后选择几个初始社区，并根据网络的拓扑迭代更新社区以获得结果社区。 现有方法中，代表性模型是SSN-LDA[69]，它是一种基于LDA的分层贝叶斯算法，针对将社区建模为潜在变量的链接网络。 这种社交网络中的节点被视为社会参与者，边缘被视为社会互动。 每个社交参与者的社交交互配置文件（SIP）由一组邻居和权重组成，用于描述参与者的特征。 具体来说，在SSN-LDA中，社交网络被视为语料库，其中社交互动档案被视为文档，社交互动的发生被视为单词。 SSN-LDA将节点建模为语料库，在转换后的语料库上挖掘社区，这个问题相当于利用LDA对语料库进行主题检测。 附录C[69]阐明了一个社交互动简档$(SI{P}_i)$的SSN-LDA生成过程，联合分布写为：

$$\begin{array}{c}\hfill P(a_i,c_i,\overrightarrow{{\theta }_i},\overrightarrow{\varphi }|\overrightarrow{\alpha },\overrightarrow{\beta })=\prod _{j=1}^{N_i}P(a_{ij}|\overrightarrow{{\varphi }_{c_i}})P(c_i|\overrightarrow{{\theta }_i})P(\overrightarrow{{\theta }_i}|\overrightarrow{\alpha })P(\overrightarrow{\varphi }|\overrightarrow{\beta }),\end{array}$$ (7)

其中 $\overrightarrow{\varphi }$ 是社区 $c_i$ 的混合组成部分，$N_i$ 是社交互动配置文件中的社交互动数量 ($SI{P}_i$)， $\overrightarrow{{\theta }_i}$是$SI{P}_i$的社区混合比例，$\overrightarrow{\alpha }$和$\overrightarrow{\beta }$是已知的狄利克雷先验分布超参数。 SSN-LDA的时间复杂度为$O(mk)$。

使用社交网络属性。 许多主题模型利用社交网络的属性（例如用户兴趣）来发现社区。 尹等人。 [70]提出将社区检测和主题模型结合起来，从而产生了潜在社区主题分析（LCTA）。 他们的方法将采样过程分为用户节点采样和链路采样。 该过程是在对用户节点进行采样后，对所有网络连接进行采样，并将这两阶段的采样结果作为用户节点的采样结果。 LCTA为每个用户节点和链路分配社区成员属性。 采样过程结束后，可以根据社区成员资格将用户节点分配到社区。 优点是两阶段采样过程形成以用户节点为核心的采样区域，可以模拟用户节点对周围链接的语义影响。 缺点是LCTA在假设社区成员度时没有考虑社交网络的链接关系，这可能会断开各个社区的联系。 此外，Cha等人。 [71]根据社交网络中关注者的主题信息设计树关系模型，利用分层LDA对树关系模型中的文本信息进行建模，并提出HLDA进行语义社交网络分析。

Xu 等人最近提出了一种主题模型与贝叶斯模型相结合的方法。 [72]。 他们为所有可能的属性网络定义了联合概率分布。 对于要聚类的给定属性社交网络，该模型为每个可能的节点聚类分配概率。 因此，聚类问题可以转化为寻找概率最高的簇的问题。 属性社区聚类算法如附录C[72]所示。 聚类归因网络的贝叶斯概率模型如下：

(8)

其中$\alpha$表示节点属于不同社区的概率，$\theta$表示节点的属性概率分布，$\varphi$表示社区之间的边出现概率，$\epsilon$和$\lambda$是Dirichlet先验分布超参数，$\mu$和$\nu$是Beta先验分布超参数。

后来，何等人。 [73]引入了一种生成模型，用于同时识别社区并推导其语义描述。 他们将嵌套 EM 算法与置信传播相结合，并探索这两部分之间隐藏的相关性，以改进生成的社区和描述。 金等人。 [74]观察到属性通常体现层次语义结构。 为了解决这个问题，他们提出了一种名为 BTLSC 的新颖贝叶斯模型，该模型将单词与背景以及一般主题与专业主题区分开来。

传统的主题模型假定社交网络的主题是独立的，与之不同的是，主题嵌入方法侧重于通过将单词和主题嵌入主题模型来描述主题之间的相关性。 他等人。 [75]提出了一种将分布式表示学习与主题相关性建模相结合的主题嵌入模型。 金等人。 [76]开发了一种名为社区增强主题嵌入（CeTe）的新型主题嵌入模型，该模型结合主题文档和网络结构来检测社区。 CeTe由三个组件组成：用于描述主题的文档组件、用于表示网络社区的拓扑组件以及连接前两部分的概率转换机制。 具体来说，CeTe使用DCSBM来描述网络社区的子组件，其中社区服从狄利克雷分布，主题服从均匀分布。 对于每个文档，社区分配是从多项式分布中得出的，而两个文档之间的链接服从伯努利分布。 对于每个单词，CeTe 绘制遵循多项式分布的主题分布。

3.1.3 基于矩阵分解的方法

非负矩阵分解（NMF）[77]是另一种用于社区检测的有向图模型。 具体来说，基于NMF的方法假设网络中存在$k$个社区，并将邻接矩阵$A={(a_{ij})}_{n\times n}\in {ℝ}_{+}$视为要分解的非负矩阵，其中$a_{ij}$表示节点$v_i$和$v_j$之间存在连接的可能性。 我们定义$𝒲={(w_{ir})}_{n\times k}\in {ℝ}_{+}$和$\mathscr{H}={(h_{jr})}_{n\times k}\in {ℝ}_{+}$，其元素$w_{ir}$和$h_{jr}$表示$v_i$生成输出的可能性边，即从 $v_i$ 开始的边，$v_j$ 生成入边，即以 $v_j$ 结束的边，属于 $r$第一个社区。 那么，节点$v_i$和$v_j$连接的可能性可以描述为：

$$\widetilde{a_{ij}}=\sum _{r=1}^k{w}_{ir}{h}_{jr}^T.$$ (9)

因此，社区检测问题可以表示为$\tilde{A}=𝒲{\mathscr{H}}^T$。 一般来说，有两个经典的损失函数来评估NMF的性能。 一个是$A$和$\tilde{A}$[78]之间差异的Frobenius范数的平方，另一个是衡量它们差异的KL散度。

表二： 基于NMF的社区检测总结，其中“AD $k$”描述了该方法是否可以自动确定社区的数量，即“是”或“否”。

Categories	Approaches	Sketches	Objective Functions	Overlapping	AD $k$
Basic	SymNMF (2012) [79]	Develop a symmetric NMF framework based on Newton-like for graph clustering.	${\Vert A-B{B}^T\Vert }_F^2$	No	No
	PCSNMF (2015) [80]	Present a symmetric NMF method with pairwise constraints generated from the ground-truth community information.	${\Vert A-B{B}^T|}_F^2$+ $\alpha [\mathrm{Tr}(B^TℳB𝒬)+\mathrm{Tr}(B^T𝒫B)]$	No	No
	NSED (2017) [81]	Pose a non-negative symmetric encoder and decoder approach to obtain a better network representation.	${\Vert A-𝒲\mathscr{H}\Vert }_F^2+{\Vert \mathscr{H}-{𝒲}^{T}A\Vert }_F^2$	No	No
Overlapping	SNMF, ANMF, JNMF (2011) [21]	Apply NMF to community detection firstly.	${\Vert A-B{B}^T\Vert }_F^2$	Yes	No
	BIGCLAM (2013) [82]	Present a cluster affiliation model for overlapping, hierarchically nested community detection in large scale networks.	${\sum }_{e_{ij}\in E}\log (1-\exp (-b_i{b}_j^T))$ $-{\sum }_{e_{ij}\notin E}{b}_i{b}_j^T$	Yes	Yes
Attribute	NMTF (2015) [83]	Develop a NMF clustering framework combining nodes’ relations and users’ contents to detect community structure.	${\Vert M_{u-u}-𝒰H_1{𝒰}^T\Vert }_F^2$ $+{\Vert M_{t-f}-𝒱H_2{𝒩}^T\Vert }_F^2$ $+{\Vert M_{u-f}-𝒰H_3{𝒩}^T\Vert }_F^2$	No	No
	SCI (2016) [84]	Propose a semantic community identification method, which can annotate semantic as well as detect community.	${\Vert B-XS\Vert }_F^2$ $+\alpha {\sum }_{r=1}^k{\Vert S(:,r)\Vert }_1^2$ $+\beta {\Vert A-B{B}^T\Vert }_F^2$	No	No
Dynamic	DBNMF (2016) [85]	Present a Bayesian probabilistic model based on NMF to identify overlapping communities in temporal networks.	$-\log P(V_t|B_t)$ $-\log P(B_t|B_{t-1}^{{}^{\prime \prime }},\alpha )$ $-\log P(B_t|{\beta }_t)-\log P({\beta }_i)$	Yes	Yes
	sE-NMF (2017) [86]	Develop a semi-supervised evolutionary NMF framework for dynamic community detection via prior information.	${\Vert A_t-\widetilde{B_t}{\widetilde{B_t}}^{\prime }\Vert }_F^2$	No	No
Semi-supervised	USSF (2015) [87]	Present a unified semi-supervised community detection algorithm based on combination of prior and topology information aimed NMF.	${ℒ}_{\alpha }(A,B)+\lambda {ℛ}_{\beta }(O,B)$	No	No

此外，对于$A$对称的无向网络，非负分解矩阵$𝒲$和$\mathscr{H}$应该相等。 在本文中，我们使用$B$来表示这些矩阵，损失函数可以写为：

$$J=\underset{B\ge 0}{\min }{\Vert A-B{B}^T\Vert }_F^2.$$ (10)

NMF最初用于识别非重叠社区。 由于 NMF 易于扩展，因此已被用来解决其他类型的社区检测问题，例如重叠、归因、动态和半监督问题，如表 3 所示。

基本 NMF。 匡等人。 [79]提出了一种通用的图聚类方法，它继承了NMF的优点，通过在聚类分配矩阵上强制执行非负性。 施等人。 [80]提出了一种新颖的成对约束非负对称矩阵分解（PCSNMF）方法，该方法施加从真实社区信息生成的成对约束，以提高社区检测的性能。 孙等人。 [81]设计一种非负对称编码器-解码器方法来导出更好的潜在表示以改进社区检测。 与其他基于 NMF 的方法仅仅关注解码器的损失不同，它们将解码器和编码器的损失结合起来构建统一的损失函数，使得获得的每个节点的社区成员资格更清晰、更具解释性。

重叠的 NMF。 由于现实世界网络的重叠和嵌套特性，重叠社区检测是另一个活跃的研究主题。 王等人。 [21]开发了一个NMF框架来识别非重叠和重叠的社区结构，并给出了无向网络的对称NMF公式。 此外，他们阐明了非对称 NMF 和联合 NMF 的方法，其中前者能够识别有向网络中的社区结构，而后者更适合复合网络（例如，包含三个网络的自动电影推荐系统：用户网络、电影网络和用户电影网络）。 杨等。 [82] 提出了一种集群隶属关系模型 BIGCLAM，用于检测大规模网络中密集重叠、层次嵌套和非重叠的社区。 具体来说，BIGCLAM首先基于节点的社区归属建立社区，即通过为节点-社区对分配一个非负潜在因子，每个节点对每个社区具有归属强度，然后将NMF与块随机梯度下降相结合，因此估计非负潜在因素来检测大型网络中的社区。 模型的损失函数定义为：

$$J=\sum _{e_{ij}\in E}\log (1-\exp (-b_i{b}_j^T))-\sum _{e_{ij}\notin E}{b}_i{b}_j^T.$$ (11)

BIGCLAM的时间复杂度为$O(n)$。

属性 NMF。 最近，利用 NMF 来获取社区结构的语义信息引起了人们的极大兴趣，即在识别社区结构的同时描绘出相应的社区语义信息[83,84,88]。 尤其是裴等人。 [83] 将社会关系和用户内容结合起来，通过基于非负矩阵三因子分解 (NMTF) 的聚类和三种类型的图正则化来检测社区。 然而，上述方法仅仅利用网络拓扑和内容信息来发现社区，而没有考虑如何利用挖掘到的内容，即语义信息来解释社区的含义。 为了解决这个问题，王等人。 [84]提出了一种称为SCI的语义社区识别方法，它将表示网络拓扑的社区成员矩阵和表示语义信息的社区属性矩阵结合起来。 模型的损失函数定义为：

(12)

其中$S$表示属性社区矩阵，$\alpha$是第一个误差和第二个稀疏项之间的权衡超参数，$\beta$是正参数用于设置网络拓扑的贡献比例。 SCI的时间复杂度为$O((nqk+n^{2}k))$，其中$q$为节点属性的维度。

动态和半监督 NMF。 值得进一步关注的是，近年来，一些研究者将NMF扩展到动态和半监督社区检测领域，并取得了令人鼓舞的成果。 对于动态社区检测，Wang等人。 [85]利用基于NMF的贝叶斯模型来识别时间网络上的重叠社区，并基于自动相关性确定自动推导每个快照网络中的社区数量。 损失函数如下：

(13)

其中$V_t$是时间网络的快照，$B_t$是通过$V_t$获得的非负矩阵，$B_{t-1}^{{}^{\prime \prime }}$是新的$B_{t-1}$根据$B_t$的节点分布进行了调整。 ${\beta }_{(\cdot )}$是半正态分布的参数，$\alpha$是平衡当前和先前快照网络的聚类结果的参数。 随后，Ma 等.[86]通过阐明进化谱聚类、进化NMF和进化模块性优化之间的等价关系，证明NMF可以应用于动态社区检测密度。 因此，他们利用上述等价关系开发了一种半监督进化NMF方法，称为sE-NMF，以整合先验信息来检测动态时间网络中的社区。

表三： 基于MRF的社区检测总结。

Categories	Approaches	Sketches	Object Functions
Topology	NetMRF (2018) [31]	Apply MRF to community detection firstly.	$\sum _{v_i\ne v_j}[-{(-1)}^{\delta (c_i,c_j)}(\frac{d_i{d}_j}{2m}-a_{ij})]$
	GMRF (2019) [89]	Optimize network embedding and develop a general MRF framework by incorporating network embedding into MRF to better detect community structure.	$\sum _{v_i}{\mathrm{\Theta }}_i(c_i)+\sum _{e_{ij}\in E}{\mathrm{\Theta }}_{ij}(c_i,c_j)$
	ModMRF (2020) [90]	Propose a MRF method formalizing modularity as the energy function for community detection.	$\sum _{v_i,v_j\in V}-(a_{ij}-\frac{d_i{d}_j}{2m})\delta (c_i,c_j)$
Topology & attribute	attrMRF (2019) [91]	Present a model integrating LDA into MRF to form an end-to-end learning system for community detection.	$\sum _{v_i\ne v_j}{\mathrm{\Theta }}_{ij}(c_i,c_j;a_{ij})$ $-\sum _{r=1}^n\frac{1}{{\beta }_1}\ln f_{{\theta }_r}-\sum _{p=1}^q\frac{1}{{\beta }_1}\ln f_{{\varphi }_p}$
Combining GNN	MRFasGCN (2019) [92]	Design a new approach based on the combination of GCN and MRF for semi-supervised community detection.	$-\sum _{i=1}^{n^{\prime }}\sum _{j=1}^k{Y}_{ij}\ln Z_{ij}$
	GMNN (2019) [93]	Propose a new approach combining the advantages of both statistical relational learning and graph neural network for semi-supervised node classification.	$E_{q_{\theta }}(y_U|x_V)[\log p_{\varphi }(y_L,y_U|x_V)$ $-\log q_{\theta }(y_U|x_V)]$

针对半监督社区检测，Yang等.[87]结合先验信息和拓扑信息提出了统一的半监督算法针对 NMF 生成的两个非负矩阵。 此外，利用必须链接先验信息（即两个节点组成的节点对必须属于同一社区的先验信息[94])，他们添加了图正则化项作为惩罚函数与损失函数相结合，以最小化同一社区内节点之间的差异，从而提高社区检测的性能。 损失函数定义为：

$$J(B|A,O)={ℒ}_{\alpha }(A,B)+\lambda {ℛ}_{\beta }(O,B),$$ (14)

其中$O$表示先验信息矩阵。 ${ℒ}_{\alpha }(A,B)$是NMF的损失函数，其中 $$αε {LSE, KL, SYM, MOD, ADJ, LAP, NLAP}是衡量相似度的参数。 $\lambda {ℛ}_{\beta }(O,B)$是图调节项，其中$\lambda$是损失函数和图调节项之间的权衡参数，$\beta \in \{LSE,KL\}$是具体的图调节项。

3.1.4 直接图形模型摘要

直接图模型通常将社区检测问题转化为基于观测到的网络数据的贝叶斯推理问题，然后利用最大似然函数或最大后验概率来优化模型参数，以获得模型的隐变量，从而发现网络社区结构。 然而，这些方法往往忽略了现实世界中社区模式的多样性（例如，具有同质或异质的社区结构），并且使用的网络拓扑通常是嘈杂和稀疏的，限制了社区检测的性能。

3.2 无向图形模型

据我们所知，现有的社区检测无向图模型研究主要利用马尔可夫随机场（MRF）[95]。 MRF 是一种随机场，在计算机视觉和图像处理等多种应用领域取得了巨大成功。 我们特别对其在社区检测中的应用感兴趣。 基于MRF的方法可以分为三类（如表4所示）：第一类是基于MRF的建模，基于网络拓扑来检测社区关系，第二类是利用语义属性信息，第三类是结合MRF使用图神经网络（GNN）。

拓扑 MRF。 他等人。 [31]首先将MRF应用于数据在不规则结构的网络上组织的网络分析，并提出一种针对网络的MRF方法，即NetMRF，用于社区检测。 该方法有效地将不规则网络的结构特性编码在能量函数中，从而使能量函数的最小化产生最佳的社区结构。 能量函数可以表示为成对势函数之和，写如下：

(15)

其中$\delta$是节点$v_i$和$v_j$落入同一社区分区的概率，$d_i$是节点$v_i$,$m$是边的数量。 根据[95]，函数越小，社区划分越好。 此外，Jin等人。 [90]将模块化函数形式化为统计模型，并提出一种新的用于社区检测的MRF方法。 该方法通过模块化表示的方法重新定义能量函数，并利用最大和置信传播（BP）来推断模型参数以提高性能。 能量函数表示如下：

$$\begin{array}{c}\hfill E(C;A)=\sum _{v_i,v_j\in V}-(a_{ij}-\frac{d_i{d}_j}{2m})\delta (c_i,c_j).\end{array}$$ (16)

时间复杂度为$O(m)$。

此外，为了克服网络嵌入后节点之间丢失重要结构信息的问题，Jin等人。 [89]提出了一种通用的MRF方法，将网络嵌入中节点对之间的耦合关系纳入其中，以更好地检测社区。 在该方法中，能量函数由两个部分组成：一组使网络嵌入发挥主导作用的一元势，以及一组利用节点对的约束来驱动一元势的成对势。 形式上，完整的能量函数可以定义为：

$$E(C;A)=\sum _{v_i}{\mathrm{\Theta }}_i(c_i)+\sum _{e_{ij}\in E}{\mathrm{\Theta }}_{ij}(c_i,c_j),$$ (17)

其中${\mathrm{\Theta }}_i$和${\mathrm{\Theta }}_{ij}$分别是一元势函数和成对势函数。

拓扑和属性 MRF。 MRF 和节点语义模型（例如主题模型）的结合是最近的研究热点。 然而，直接将MRF与节点语义模型结合的方法通常不能取得令人满意的结果。 主要是因为两种模型的参数无法调整以相互支持，难以结合两种方法的优点。 他等人。 [91]提出了一种新模型，名为attrMRF，将LDA[68]和MRF集成在一起，形成一个端到端的学习系统来联合训练参数。 具体来说，attrMRF首先将LDA和MRF转化为统一的因子图，实现了有向图模型（即LDA）和无向图模型（即MRF）的有效集成。 然后采用反向传播（BP）算法同时训练参数，从而实现两个模型的端到端学习。 该模型的全局能量函数表示为：

(18)

其中${\sum }_{v_i\ne v_j}{\mathrm{\Theta }}_{ij}(c_i,c_j;a_{ij})$表示(15)中定义的MRF的全局能量潜力，${\beta }_1$是温度系数，$f_{{\theta }_r}$和$f_{{\varphi }_p}$是LDA联合概率分布生成的中间结果。 除了 attrMRF 之外，还有几种将概率图模型融入深度学习的方法，例如 MRFasGCN [92] 和 GMNN [93]，稍后将详细介绍。

无向图模型主要利用MRF的特性，即不规则网络结构和节点属性的一元势和成对势来识别社区结构。 然而，不同的能量函数需要进行微调。

3.3 集成有向模型和无向模型

有向和无向图形模型也已被集成以检测复杂网络中的社区。 这种类型的集成通常通过因子图模型来实现。 因子图[96]是一个元组$(V,ℱ,\epsilon )$，由一组变量节点$V$、一组因子节点$F$组成，以及一组$\epsilon \subseteq V\times ℱ$边，每条边连接一个变量节点和一个因子节点。 以MRF为例，因子图的联合概率分布描述为：

$$p(y)=\frac{1}{\mathbb{Z}}\prod _{F\in ℱ}{\psi }_F(y_{N(F)}),$$ (19)

其中$\mathbb{Z}={\sum }_{y\in Y}{\prod }_{F\in ℱ}{\psi }_F(y_{N(F)})$表示归一化因子，$N(F)=\{v_i\in V:(v_i,F)\in \epsilon \}$是与因子节点$F$相邻的变量节点的集合。

杨等。 [97]首先提出了一种基于因子图的实例化模型，该模型包含三层：底层（观测节点）、中间层（隐向量）和顶层（社区潜变量）。 它利用节点特征和边特征函数挖掘底层节点和顶层节点之间的依赖关系来表示相应的社区，从而更好地检测社区。 此外，贾等人。 [98]将因子图模型应用于自我中心网络（人类社交网络的一种表示，用于表示个体与自我有社会关系的其他人之间的网络[99])，并提出了一种以自我为中心的方法来分析社会学术对合著者网络的影响。 该方法在统一的因子图中对以自我为中心的社区检测进行建模，采用参数学习算法来估计主题级社会影响力、这些节点和社区结构之间的社会关系强度，以检测自我社区结构。

这些方法仅仅识别社区的结构，而忽略了社区的语义信息，这对于理解社区结构的含义至关重要。 他等人。 [91]采用因子模型来克服有向图模型（即LDA）和无向图模型（即MRF）由于参数共享和联合训练而不足以集成的缺陷，使得发现的社区结构在语义上是可解释的。 用因子图表示的 MRF 和 LDA 的联合概率分布写为：

$$P(Z,C;A,X,\alpha ,\beta )=\frac{1}{\mathbb{Z}}\prod _{r=1}^n{f}_{{\theta }_r}\prod _{p=1}^q{f}_{{\varphi }_p}\prod _{v_i\ne v_j}{f}_{{\gamma }_{ij}},$$ (20)

其中$\mathbb{Z}$表示归一化项，$f_{{\theta }_r}$和$f_{{\varphi }_p}$在(18)中定义，$f_{{\gamma }_{ij}}$是节点 $v_i$ 和 $v_j$ 的成对电位。 他们的主要贡献在于采用了MRF和LDA的融合技术来处理社区检测，很好地克服了两个模型参数难以通过因子图和置信传播来共享和一起训练的困难。

集成有向图模型和无向图模型的因子图模型的出现，极大地提高了社区检测的性能。 然而，这些概率图模型通常采用变分推理或马尔可夫链蒙特卡罗（MCMC）采样来进行模型优化，这不可避免地导致较高的计算复杂度。 深度学习能够有效优化高维网络数据，在处理社区检测方面具有潜力。

4 利用深度学习进行社区检测

表四： 基于自动编码器的社区检测总结，其中“A”和“X”分别表示该方法是否利用网络拓扑和节点属性，“-”表示没有约束。

Categories	Approaches	A	X	Encoder	Decoder	Focus	Constraints
Stacked	Semi-DNR (2016) [100]	Yes	No	MLP	MLP	Network embedding	Pairwise constraint
	DIR (2017) [101]	Yes	Yes	MLP	MLP	Network embedding	-
	INSNCCD (2018) [102]	Yes	Yes	MLP	MLP	Network embedding	Modularity maximization
	AAGR (2018) [103]	Yes	Yes	MLP	MLP	Network embedding	Adaptive parameter
	CDDTA (2019) [104]	Yes	No	MLP	MLP	Network embedding	Regularization term
	DeCom (2019) [105]	Yes	No	MLP	MLP	Clustering result	Modularity maximization
	NEC (2020) [106]	Yes	Yes	GCN	Inner product	Embedding and clustering	Modularity maximization
Sparse	GraphEncoder (2014) [107]	Yes	No	MLP	MLP	Network embedding	Sparsity constraint
	DFuzzy (2018) [108]	Yes	No	MLP	MLP	Clustering result	Sparsity constraint and modularity maximization
	CDMEC (2020) [109]	Yes	No	MLP	MLP	Clustering result	Sparsity constraint
Denoising	MGAE (2017) [24]	Yes	Yes	GCN	GCN	Network embedding	Interplay exploitation
	GRACE (2017) [110]	Yes	Yes	MLP	MLP	Embedding and clustering	Propagation constraint
Variational	ARVGA (2018) [111]	Yes	Yes	GCN	Inner product	Network embedding	Prior constraint
	VGAECD (2018) [112]	Yes	Yes	GCN	Inner product	Embedding and clustering	-
	DAEGC (2019) [113]	Yes	Yes	GAT	Inner product	Embedding and Clustering	KL divergence constraint
	New VGAECD (2019) [114]	Yes	Yes	GCN	Inner product	Embedding and clustering	-
	Ladder VAE (2019) [115]	Yes	No	GCN	MLP	Embedding and clustering	-
	NetVAE (2019) [116]	Yes	Yes	MLP	MLP	Network embedding	Prior constraint

近年来，深度学习引起了人们的广泛关注，并被证明在解决包括社区检测在内的各种问题上具有巨大的威力。 经典深度学习探索并利用卷积神经网络 (CNN) 和概率建模来进行社区检测。 例如，Sperlì 等人。 [32]设计了一种基于CNN和邻接矩阵拓扑特征的新方法，用于自动社区检测。 孙等人。 [117]提出了一种概率生成模型，即vGraph，来联合检测重叠（和非重叠）社区并学习节点（和社区）表示。 vGraph 通过社区的混合来表示每个节点，并将社区定义为节点上的多项分布。 此外，卡瓦拉里等人。 [118]发现社区检测、社区嵌入和节点嵌入之间存在闭环关系。 在这一见解的指导下，他们提出了一种新颖的社区嵌入方法，称为 ComE，来共同解决这三个任务。 他等人.[119]设计了一种新颖的自翻译网络嵌入（STNE）方法，将内容序列映射到节点身份序列以改进社区检测。

虽然这些方法在发现社区方面具有不错的性能，但它们只是深度学习在社区检测中的直接应用[120]，没有考虑网络的特征，例如网络拓扑的不规则性和复杂的网络结构。 在本节中，我们将讨论以下四种为复杂网络设计的方法，即基于自动编码器的方法、基于生成对抗网络的方法、基于图卷积网络的方法以及集成图卷积网络和无向图模型的方法。

4.1 基于自动编码器的方法

自动编码器[121]是简单但重要的神经模型，可将高维（网络）数据转换为低维表示。 具体来说，自动编码器使用编码器和解码器组件以无监督的方式学习数据的新表示。 它们总是具有多个隐藏层和对称架构，并且一层的输出是其后续层的输入。 自动编码器的目标是最小化原始输入和重构数据之间的误差，以学习最佳的隐藏表示，可以表示为：

$$Loss({\theta }_1,{\theta }_2)=\sum _{i=1}^{n}l(x_i,g(f(x_i;{\theta }_1);{\theta }_2)),$$ (21)

其中$f(\cdot ;{\theta }_1)$和$g(\cdot ;{\theta }_2)$是编码器和解码器，参数为${\theta }_1$和${\theta }_2$,$l(\cdot )$是损失功能。

在这里，我们选择了几种具有代表性的基于自动编码器的模型进行网络社区检测，并在表IV中总结了它们的主要特征。 由于大多数基于自动编码器的方法将网络嵌入作为其输出（例如，[100, 103])，因此随后应用聚类（例如 K 均值和谱聚类）来提取社区。 另一种方法是将聚类集成到模型中（例如，[108, 105])，以直接发现社区。 根据所使用的自动编码器的类型，我们将模型分为四种类型，即堆叠、稀疏、去噪和变分自动编码器。 堆叠式自动编码器是由一系列自动编码器组成的基本类型，通常用作其他类型自动编码器的块。 特别是，当堆叠模型具有其他目标（例如稀疏性和去噪）时，我们将它们分类为稀疏或去噪自动编码器。

堆叠式自动编码器。 semi-DNR [100] 堆叠一系列自动编码器以形成输入网络（DNR）的深度非线性重建，并要求编码器的每一层包含比前一层更少的神经元减少数据维度并提取输入数据中最显着的特征。 Semi-DNR充分利用$v_i$和$v_j$属于同一社区的先验知识来合并网络中两个节点之间的成对约束。 具体来说，它定义了一个先验信息矩阵 $O={(o_{ij})}_{n\times n}$，其中 $o_{ij}=1$ 如果已知 $v_i$ 和 $v_j$ 位于同一社区，或者0，否则。 半 DNR 的损失函数表示为：

$$Loss=l(M,Z)+\lambda \mathrm{Tr}(H^{T}LH),$$ (22)

其中$L=D-O$,$\mathrm{Tr}(\cdot )$是矩阵的迹，$M$是模块化矩阵，$Z$是重建数据，$H$表示矩阵和$\lambda$参数，用于在给定先验信息的情况下在重构误差和新表示的一致性之间进行权衡。 进一步，采用DeCom[105]中的逐层堆叠自动编码器根据网络结构寻找种子节点并将节点添加到社区中。 值得注意的是，DeCom 适合处理大型网络，并且由于自适应学习过程而无需预先定义社区的数量。 此外，CDDTA [104]有效地结合了迁移学习和自动编码器。 AAGR[103]和DIR[101]利用堆叠式自动编码器自适应地融合拓扑和属性信息，从而很好地实现了网络拓扑和节点属性之间的平衡。 NEC[106]采用图卷积网络对网络数据进行编码和解码，以拓扑和属性信息作为输入，但仅选择重建邻接矩阵，以确保模型在没有节点属性的情况下仍然可以工作。

稀疏自动编码器。 大规模网络通常难以存储和处理，因此需要稀疏表示。 为此，一项新的研究方向是通过向自动编码器添加稀疏约束来自适应地找到最佳表示。 GraphEncoder [107] 为隐藏层引入了显式正则化项，以限制隐藏表示的大小。 如果$z_i$是重构数据的第$i$向量，则稀疏约束下的重构误差如下：

$$Loss=\sum _{i=1}^n{\Vert z_i-x_i\Vert }_2+\beta KL(\rho |\widehat{\rho }),$$ (23)

其中 $\beta$ 控制稀疏性惩罚，$\rho$ 和 $\widehat{\rho }$ 是稀疏性参数，其中前者表示训练样本集合中神经元的平均激活，后者表示所有训练样本的平均激活度。 GraphEncoder的时间复杂度为$O(nbd)$，其中$b$是最大隐藏层节点数，$d$是图的平均度。 DFuzzy [108] 是一种并行且可扩展的模糊聚类模型，以稀疏自动编码器作为构建块。 它使用个性化 PageRank 训练自动编码器，这对于捕获网络节点之间的关系非常有效。 此外，CDMEC [109]将迁移学习与自动编码器相结合，其中输入矩阵$A$用于构建复杂网络的四个相似度矩阵。 CDMEC以一个矩阵作为源域，另外三个矩阵作为目标域，以获得多个不同的低维特征表示。 然后将所有表示放入聚类算法中，并将聚类结果整合到一个新的共识矩阵$Q$中。 引入一致性矩阵$Q$来衡量聚类结果中样本的共现情况，其中$Q_{ij}$表示$v_i$和$v_j$

去噪自动编码器。 去噪自动编码器可以应用于噪声输入，以获得对噪声具有鲁棒性的节点表示。 MAGE [24]首先采用卷积网络整合内容和结构信息，然后在自动编码过程中迭代地将随机噪声添加到内容信息中。 这样，结构信息和内容信息就被整合到一个统一的框架中，并且可以分析两者之间的相互作用。 此外，杨等人。 [110]提出GRACE来处理动态网络。 他们在网络动力学的考虑下对集群进行建模，并认为集群的形成需要动态嵌入才能达到稳定状态。

变分自动编码器。 还有一些基于变分自动编码器[122]的方法，它将隐藏表示视为具有自己的先验分布的潜在变量。 在变分推理中，它利用潜在变量的真实后验 $p(H|X)$ 的近似 $q(H|X)$ ，并尝试将变分后验 $q(H|X)$ 逼近真实先验 $p(H)$ 使用 KL 散度作为衡量标准。 例如，ARVGA [111] 的主题不仅是最小化网络结构的重建错误，而且还强制潜在代码匹配先验分布：

$$Loss={𝔼}_{q(H|(X,A))}[\log p(\widehat{A}|H)]-KL[q(H|X,A)||p(H)].$$ (24)

在 VGAECD [112] 的训练过程中，重建损失偏离了其聚类的主要目标。 新的 VGAECD [114] 通过引入双变分目标纠正了这个问题。 此外，萨卡等人。 [115]提出了一种基于伽玛梯VAE的深度生成模型，通过多层随机潜变量推断节点的多层嵌入，以提高社区检测的性能。 金等人。 [116]提出了NetVAE，使用一个编码器和一个双解码器以及两种不同的生成机制来分别重建网络拓扑和节点属性。

4.2 基于生成对抗网络的方法

受极小极大两人游戏启发的生成对抗网络（GAN）[123]在各个领域取得了前所未有的成功。 GAN 通常由两个模块组成：生成器 $𝒢$ 和判别器 $𝒟$。 生成器是捕获数据分布，即生成尽可能与真实数据相似的样本；而判别器是估计样本是真实数据而不是生成器生成的合成数据的概率。 形式上，GAN的训练过程可以定义为：

$\underset{𝒢}{\min }\underset{𝒟}{\max }𝒱(𝒢,𝒟)=$ $\underset{𝒢}{\min }\underset{𝒟}{\max }({𝔼}_{x\sim p_{data(x)}}[\log 𝒟(x)]$

$+{𝔼}_{z\sim p_{z(z)}}[\log (1-𝒟(𝒢(z)))]),$ (25)

其中第一个期望是鉴别器对真实数据的损失，第二个期望是鉴别器对生成器生成的合成数据的损失。

将GAN应用于社区检测的灵感来自于GAN通常是无监督的，并且（理论上）生成的新数据与真实数据具有相同的分布，这提供了强大的网络数据分析能力。 贾等人。 [26]提出了一种称为CommunityGAN的新方法，采用隶属图模型（AGM）的思想，通过引入网络基序级生成器和鉴别器之间的极小极大竞争来提高性能。 它首先通过为每个节点-社区对分配一个表示节点对社区的隶属程度的非负因子来组成节点的一些表示向量，然后通过专门设计的 GAN 来优化这种表示以检测社区。 联合价值函数表述为：

$\underset{{\theta }_{𝒢}}{\min }\underset{{\theta }_{𝒟}}{\max }$ $𝒱(𝒢,𝒟)={\displaystyle \sum _{i=1}^n}({𝔼}_{m\sim p_{true(.|v_i)}}[\log 𝒟(m;{\theta }_{𝒟})]$

$+{𝔼}_{s\sim {𝒢}_{(s|v_i;{\theta }_{𝒢})}}[\log (1-𝒟(𝒢(s;{\theta }_{𝒟})))]),$ (26)

其中${\theta }_{𝒟}$（和${\theta }_{𝒢}$)是鉴别器$𝒟$（和生成器$𝒢$)中所有节点表示向量的并集，$m$ 网络的主题和 $s$ 节点的子集。 通过使用 GAN，CommunityGAN 可以找到重叠的社区并共同学习图形表示。 此外，Zhang等人。 [27]提出了一种利用生成对抗性学习（SEAL）进行种子扩展的新方法。 它使用判别器来预测社区是否真实，并使用生成器来构建社区，通过隐式拟合真实社区的特征来欺骗判别器，以学习社区检测的启发式方法。 陶等人。 [124]提出了一种对抗性图自动编码器（AGAE）方法，它将集成聚类合并到深度图嵌入过程中，以利用对抗性正则化器指导网络训练。

还有一些基于 GAN 的方法来导出可应用于社区检测的节点表示，例如使用 K-means 等聚类算法来导出嵌入以获得结果社区[125, 126, 127] 。 他等人。 [128]进一步认为，现有的基于GAN的方法没有充分利用GAN的本质优势，即学习底层表示机制而不是表示本身。 为此，他们提出利用表示机制上的对抗性思想来获取下游任务的节点表示。 具体来说，训练损失定义如下：

$\underset{ℰ,𝒢}{\min }\underset{𝒟}{\max }$ $𝒱(𝒢,𝒟,ℰ)={𝔼}_{x\sim p_{data(x)}}[\log 𝒟(MI(x,ℰ(x)))]$

$+{𝔼}_{z\sim p_{z(z)}}[\log (1-𝒟(MI(𝒢(z),z)))]),$ (27)

其中$ℰ$表示导出节点表示的编码器，$MI(x,ℰ(x))$是节点属性和节点表示之间的互信息，$𝒟$是识别互信息的判别器分别来自正样本和负样本，$𝒢$是生成器，通过基于高斯噪声计算假节点属性之间的互信息来生成负样本。 杨等。 [129] 认为大多数 GAN 将嵌入的结果与从高斯分布获得的样本进行比较，而没有根据实际数据进行校正，这使得它们并不能真正有益于对抗性学习。 因此，他们设计了一种联合对抗网络嵌入（JANE）模型，共同区分嵌入、拓扑信息和节点属性的真假组合，以提高节点嵌入和网络分析的性能。

4.3 基于图卷积网络的方法

图卷积网络（GCN）[33]，用于从图数据中学习表示的图神经网络方法[130]最具代表性的分支，由于其在网络中节点的监督和半监督分类方面的成功，引起了广泛的关注。 最近还开发了几种基于 GCN 的新颖算法，以利用 GCN 的强大功能来有效建模和推断高维复杂网络数据以进行社区检测。

金等人。 [131] 引起人们的关注，即源自 GCN 的嵌入不是面向社区的，并且社区检测本质上是无监督的。 为了解决这个问题，他们引入了一种名为 JGE-CD 的无监督模型，通过联合 GCN 嵌入进行社区检测。 它由三个模块组成，一个双编码器，使用原始属性网络及其变体派生两个嵌入；社区检测模块，堆叠在双编码器之上以检测社区；拓扑重建模块，用于重建网络拓扑。 形式上，第$i$个节点属于第$r$个社区的概率定义为：

$$u_{ir}=\frac{\exp ({\theta }_r^T{h}_i)}{{\sum }_{r=1}^k\exp ({\theta }_r^T{h}_i)},$$ (28)

其中$h_i$表示从GCN获得的节点$v_i$和$\theta$模型参数的嵌入。 此外，He等人。 [132] 通过设计一种新的 GCN 方法来扩展 JGE-CD，该方法将 MRFasGCN（稍后将在第 4.4 节中讨论）作为编码器，并利用以社区为中心的双编码器来重建网络拓扑和节点分别属性，从而进行无监督的社区检测。 特别地，用于重建网络拓扑的解码器表示为：

$$\widehat{A}=\mathrm{sigmoid}\left(DUW{U}^T{D}^T\right),$$ (29)

其中$U$是编码器导出的属于不同社区的节点的概率分布矩阵，$D$是节点度矩阵，$W$是神经网络的权重矩阵。 用于重建属性的解码器受到主题建模的启发，即同一社区中的节点更有可能具有相似的属性词分布。 属性矩阵可以通过以下方式生成：

$$\widehat{X}=U\cdot R,$$ (30)

其中$U$的定义与(29)中的定义相同，$R$是社区从整个词集中选择属性词的概率矩阵。

最近，一些社区检测研究利用了包含多种类型节点和关系的异构网络上的 GCN。 郑等人。 [133]设计一个异构时间GCN，即HTGCN，从异构时间网络中检测社区。 具体来说，它首先采用异构GCN获得每个异构网络在每个时间步的特征表示，然后利用残差压缩聚合机制来表达社区的静态和动态特征。 除此之外，还有一些将图卷积网络与无向图模型相结合的方法，例如 MRFasGCN [92] 和 GMNN [93]，接下来将讨论这些方法。

4.4 集成图卷积网络和无向图模型

在过去的几年中，许多研究已经开始集成图卷积网络（GCN）和无向图模型（例如，MRF或CRF）来进行社区检测。 该研究的主要思想是，GCN本质上是通过局部特征平滑来构造节点嵌入，这没有考虑社区属性，使得节点嵌入不面向社区。 虽然无向图模型通常提供良好的全局目标来描述社区，但它不考虑节点上的信息，并且需要大量计算来学习模型。 因此，GCN和无向图模型是互补的，可以结合起来发挥各自的优势。

该领域的一项主要工作是 MRFasGCN [92]，它将 GCN 与 MRF 结合起来，解决属性网络中的半监督社区检测问题。 该方法首先通过添加一元势和属性信息将 NetMRF（如第 3.2 节中所述）扩展为扩展 MRF (eMRF)，然后重新参数化 MRF 模型以使其适合 GCN 架构。 eMRF的能量函数定义为：

$$E(C;A,X)=\sum _{v_i}-p(h_i^{c_i})+\alpha \sum _{v_i\ne v_j}\mu (c_i,c_j)\eta (v_i,v_j),$$ (31)

其中，$-p(h_i^{c_i})$ 的值来自 GCN 的结果，表示节点 $v_i$ 属于群落 $c_i$ 的概率的一元势；$\mu (c_i,c_j)\eta (v_i,v_j)$ 是成对势，其中 $\mu (c_i,c_j)$ 表示节点 $v_i$ 和 $v_j$ 的群落之间的相似性关系、和 $\eta (v_i,v_j)$ 是节点 $v_i$ 和 $v_j$ 属性的相似性，而 $\alpha$ 是在一元势能和成对势能之间进行权衡的参数。 MRFasGCN的时间复杂度为$O(mqlk{}_{}{}^2)$，其中$q$是节点属性的维度，$l$是第一层隐藏单元的数量。

在 MRFasGCN 之后，其他几项工作将 MRF 或 CRF 合并到 GCN 中，以学习用于社区检测的节点嵌入。 曲等人。 [93]提出了一种新方法，称为图马尔可夫神经网络（GMNN），结合了统计关系学习和图神经网络的优点。 GMNN能够学习有效的节点表示，并对不同节点之间的标签依赖关系进行建模，从而完成半监督节点分类的任务。 模型参数可以通过使用伪似然变分期望最大化[134]来优化对数似然函数的证据下界（ELBO）来学习，其公式为：

(32)

其中 $\log p_{\varphi }(y_L|x_V)$ 是观察到的节点标签的对数似然函数，$q_{\theta }(y_U|x_V)$ 是 $y_U$ 上的任何分布。 请注意，当 $q_{\theta }(y_U|x_V)=p_{\varphi }(y_U|y_L,x_V)$ 时，等式成立。 高等人。 [135]发现现有的GCN无法保留隐藏在网络数据中的不同节点之间的相似关系。 为了解决这个问题，他们在 GCN 中添加了一个 CRF 层，以强制相似的节点具有相似的隐藏特征。 这将提高节点嵌入的质量，进而提高网络分析的性能。

4.5 深度学习总结

基于深度学习的方法通常通过设计面向社区的或通用的网络表示，然后是一些聚类算法来实现社区检测。 人们采用了不同类型的深度学习方法来导出网络表示，例如 GCN 或 GAN。 学习这样的表示就是将网络数据从高维输入空间映射到低维特征空间，具有计算复杂度低、数据融合有效的优势。 然而，与大多数概率图模型类似，现有的基于深度学习的方法更适合具有同质性的社区结构（社区中的节点紧密连接，而不同社区中的节点连接稀疏），这可能会限制鲁棒性这些模型。

5 社区检测的应用

我们首先总结社区检测领域使用的基准数据集。 然后我们描述社区检测在许多应用领域的实际应用。

5.1 开放数据集

我们已将用于社区检测的数据集的详细信息放在可公开访问的网络 促进对这一快速发展主题的开放研究。 这些数据集可以分为两组：合成网络和真实世界网络。

5.1.1 合成网络

有两类具有已知社区结构的随机生成的合成网络，即 Girvan-Newman (GN) [1] 和 LFR 网络 [136]。 GN网络由四个大小相同、不重叠的社区组成。 每个社区有 32 个节点，每个社区平均与 16 个其他节点连接。 在这16条边中，$Z_{in}$边连接同一社区的节点，$Z_{out}$边连接不同社区的节点，$Z_{in}+Z_{out}=16$边。 LFR 网络是另一个广泛采用的用于测试社区检测算法性能的基准，其节点度和社区规模的分布遵循指数可调的幂律。 LFR 网络捕获了现实世界系统的几个重要特征，例如无标度属性。

5.1.2 现实世界网络

我们研究的现实世界网络包括四种类型，即社交网络、引用网络、协作网络等，如表 5 所示。 具体来说，社交网络是由个体及其交互形成的，包括足球、DBLP等八个代表性数据集（表5）。 引文网络由论文（或专利）及其关系（例如引用或包含）组成，包括 Cora 和 arXiv 等八个经典数据集。 协作网络由科学家及其协作（即共同撰写论文）组成，包括计算机科学和医学等四个典型数据集。 这些网络中的节点数量从数十到数百万不等，边数最大可达数百至数亿。

表五： 现实世界网络的统计数据。

Categories	Datasets	#Nodes	#Edges
Social Networks	Friendship7 [37]	68	220
	Football [1]	115	613
	Facebook [137]	1,045	26,749
	LiveJournal [138]	44,093	871,409
	Twitter [27]	87,760	1,293,985
	Orkut [138]	297,691	7,747,026
	DBLP [139]	317,080	1,049,866
	Youtube[139]	1,134,890	2,987,624
Citation Networks	Small-hep	397	812
	Polblogs [140]	1490	16718
	Cora [141]	2708	5429
	Citeseer [141]	3312	4732
	Large-hep	11,752	134,956
	Pubmed [142]	19,729	44,338
	arXiv [143]	576,000	6,640,000
	US patents [144]	3,700,000	16,500,000
Collaboration Networks	Computer Science [145]	22,000	96,800
	Chemistry [145]	35,400	157,400
	Medicine [145]	63,300	810,300
	Engineering [145]	14,900	49,300
Others	Amazon [139]	334,863	925,872
	Google [146]	875,000	4,320,000

5.2 实际应用

我们首先讨论社区检测在不同领域的应用，然后扩展到其他网络分析任务。 最后我们讨论社区检测对网络科学的潜力。

5.2.1 不同领域的应用

社区检测在不同领域有多种应用[147]，例如在线社交网络、神经科学和图像理解。 在线社交网络，包括 Facebook、Twitter 和微信，构成了人们通过网络进行的互动。 在此类网络中发现社区是推断个体关系的有效方法，该方法已被用于垃圾邮件发送者检测和危机响应等任务。 尹等人。 [148]开发一个统一的概率生成模型，即用户社区地理主题（UCGT），基于贝叶斯网络，通过结合时空数据和语义信息来推断用户的社交社区提高社交社区检测的准确性和可解释性。 吴等人。 [149]设计了一种新颖的MRFwithGCN模型，该模型引入了一个MRF层，该层捕获用户关注信息，以细化GCN针对社交垃圾邮件发送者检测所做的预测。

神经科学是一门研究神经系统和大脑的学科。 随着脑图谱和神经成像技术的最新发展，大脑已经开始被建模为网络。 人们已经付出了大量的努力来利用这种网络来帮助提取大脑的功能细分。 刘等人。 [150]提出了暹罗社区保存图卷积网络（SCP-GCN）的框架。 该方法首先在学习过程中考虑社区内和社区间的属性，保留社区结构，然后使用对成对相似性进行建模的孪生架构来指导学习过程。 金等人。 [151]认为现有研究通常利用静息态功能磁共振成像（fMRI）数据构建大脑网络的群落结构。 他们引入了动态时间规整（DTW）算法，该算法分析功能磁共振成像时间序列的同步和异步，以提取大脑区域之间的相关性。

图像理解是生成图像的语义描述。 最近，出现了利用社区进行图像理解的工作。 李等人。 [152]提出了一种新颖的深度协作嵌入（DCE）模型，该模型从弱监督的社区贡献的资源中学习知识，同时用于多个图像理解任务。 李等人。 [153]通过显式探索图像表示数据的块对角线结构，提出了一种新颖的半监督 RSNMF 模型。

5.2.2网络分析推广

随着社区检测的巨大成功，许多应用问题，例如推荐和链接预测，已被表述为在网络系统中寻找社区结构。 我们现在讨论如何利用现有的社区检测方法来解决其中一些问题。

推荐是一项常见的任务，它通过根据用户购买或浏览历史记录中的项目建立用户兴趣档案，然后向用户推荐类似的项目来解决用户信息过载的问题。 现有的推荐方法包括协同过滤[154]和神经网络[155]。 特别是，社区的概念被用来提高推荐的质量。 艾萨等人。 [156] 根据基于主题的归因社交网络生成的基于兴趣的社区进行推荐。 Satuluri 等人。 [2] 提出了一个通用表示层，即基于相似性的集群 (SimClusters)，它通过检测用户-用户网络中的二分社区并利用它们来解决 Twitter 上的大量推荐任务作为表示空间。

链接预测是网络挖掘中的另一个重要任务。 它通过分析观察到的网络结构和外部信息来处理丢失的连接并预测未来可能的连接。 已经提出了大量方法来通过考虑社区来促进链接预测。 徐等人。 [157]表明现有的链接预测度量学习忽略了包含丰富结构信息的社区。 因此，他们通过联合社区检测的方式设计了社区特定的相似性度量，以处理节点之间的边缘不可用的冷启动链路预测。 德等人。 [158]提出了一种堆叠式两级学习框架，该框架首先学习利用局部结构和节点属性的局部相似性模型，然后将该模型与利用共聚类导出的社区级特征相结合链接预测。

5.2.3网络科学的推广

网络科学是一个跨学科的研究领域，它不仅可以应用于计算机科学，还可以应用于社会学、生物学等其他领域。 社区发现是网络分析中最重要的问题之一，可以极大地促进网络科学的发展。 例如，在引文网络中，节点代表论文，边代表论文之间的引用。 通过对论文进行分组（即发现论文具有相似属性（如属于同一作者或主题）的社区），我们可以分析作者的影响力，准确掌握最新的研究趋势或技术，这对于理解网络具有指导意义并进一步分析网络模式[159]。 同样，在社会学和生物学中，社区检测也提供了对网络结构更深入的理解，并促进其在学术界和工业界的发展。

6 未来方向

虽然基于学习的社区检测（包括概率图模型和深度学习）已在各种问题和领域中表现出卓越的性能，但仍存在需要解决的挑战。 在本节中，我们将简要讨论这些挑战和未来可能值得追求的研究方向。

6.1 大型网络

随着网络数据规模的迅速增加，更大型的网络已成为许多不同科学领域的标准。 这些网络通常具有数万或数十亿个节点和边缘以及复杂的结构模式。 由于对内存和计算的潜在需求过高，大多数现有的社区检测方法在如此大的网络上面临着过度的限制。 他们可能需要大量的训练实例[160]或模型参数[161]才能使现有方法有效。 此外，现有方法通常通过网络约简或近似来处理这些问题，这可能会丢失一些重要的网络信息并影响建模精度。 这就提出了如何设计一个在准确性和效率方面远远超过当前基准的框架的问题。

6.2 社区可解释性

尽管社区检测已经研究了十多年，但社区的可解释性仍然是一个需要充分解决的重要且关键的问题。 当前大多数社区检测方法利用结果中排名最高的单词或短语来概括社区，尽管节点的属性信息通常是比单个单词[162, 73]具有更多信息的完整句子。 然而，由于单词数量较少且单词之间的关系不明确，这些方法对于理解社区的语义可能不够直观。 如何充分利用网络信息为社区提供更好的语义解释是未来的研究方向之一。

6.3 自适应社区模型选择

社区检测的自适应模型选择旨在根据不同网络的特征（例如异构或动态）或不同任务的具体要求（例如最高的准确性或最低的时间复杂度）选择最合适的算法来发现社区。 尽管现有方法可以在一定程度上从一个网络或任务扩展到另一个网络或任务（这不可避免地影响所得模型的准确性和稳定性）[163],[164]，很少有人考虑如何进行模型自适应。 因此，重点已经转移到设计一个统一的架构，可以自动适应特定的任务或网络，同时保持模型的准确性和稳定性，而不是为不同的网络或任务提出不同的框架。 这是一个新兴的研究领域，充满挑战，但回报丰厚。

6.4 复杂结构的网络

许多现实世界的网络是异构的、动态的、分层的或不完整的。 异构网络[165]是包含不同类型的节点和边，或者包含不同类型的节点和边的描述（例如文本和图像）的网络。 动态网络[166]是拓扑和/或属性随时间变化的网络。 当添加或删除节点和边时，就会出现动态网络，从而改变节点或边的属性。 分层网络[167]由多个层组成，每个层都有特定的语义和功能。 不完整网络[168]是指缺少拓扑、节点或边信息的网络。 虽然这些网络可以通过基于学习的社区检测进行部分探索，但仍然存在一些严重的问题。 首先，大多数现有方法都假设同质网络，这实际上可能很难处理。 其次，由于动态网络的可变性，大多数现有方法，尤其是基于深度学习的方法，在网络演化时需要经过一系列步骤进行重新训练，这非常耗时且可能无法满足实时性加工需求。 第三，层次网络通常在网络层次结构中具有不同类型的关系，这很重要，但现有方法通常不能很好地处理。 此外，几乎所有现有方法都认为待分析的网络是完整且准确记录的，没有噪声。 不幸的是，在实践中这种情况很少发生，因为获取网络的完整信息具有挑战性。 因此，应该开发新的方法来处理这些问题，以更好地提高此类复杂网络上社区检测的性能。

6.5 集成统计建模和深度学习

尽管已经提出了几种将统计建模与深度学习相结合的方法，例如 MRFasGCN，但它仍然是一个处女地但有前途的研究领域。 例如，现有方法通常利用统计模型提供的先验知识（例如社区）来细化 GCN 的嵌入，以改善生成的社区。 然而，这些方法可能没有充分考虑模型的时间复杂度或可解释性，给实践中的社区检测带来了巨大的挑战。 此外，现实世界网络中的社区模式通常是多种多样的，例如，社区结构具有异质性（不同社区中的节点紧密相连，而同一社区中的节点稀疏连接）或随机性（节点之间的边更有可能是随机生成的），因此有必要通过集成统计建模和深度学习来设计新的鲁棒方法[92]，从而更准确地检测网络中的社区结构。 此外，将统计建模集成到深度学习方法中仍然是一个悬而未决的问题。 例如，很难应用推荐或医疗诊断的策略来使深度学习成为更好的表示学习，从而促进更准确的推荐或诊断。 非常需要新的创新算法来整合统计推理和深度学习，以帮助深度学习更多地产生适用于广泛应用领域中的各种网络问题的可解释的网络表示模型。

7 结论

在本文中，我们对社区检测方法进行了全面且最新的文献综述。 我们的主要目标之一是以统一的视角组织和呈现迄今为止所做的大部分工作。 第一步，我们详细讨论社区检测问题，并提供一种新的分类法，从学习的角度将大多数现有方法分为两类：概率图模型和深度学习。 然后，我们彻底回顾、比较和总结这两类现有的方法，并讨论其中一些方法如何引起人们的兴趣。 此外，由于该问题具有高度的应用导向性，因此我们介绍了社区检测在各个领域的广泛应用。 我们还强调，需要付出更多努力来解决社区检测研究中的几个具有挑战性的开放问题。 最后但并非最不重要的一点是，虽然我们无法列出有关社区检测的所有文献，但我们希望尝试综合社区检测的最新技术将有助于更好地理解这个高度活跃且日益重要的领域网络科学的研究成果，为进入该领域的新研究人员和在该领域工作的研究人员提供信息来源，并促进下一代社区检测方法的未来发展。

附录A

我们在表 1 中列出了正文中的关键术语和符号。

表六： 符号摘要。

Notations	Descriptions
$G$	A network.
$V,E$	The sets of nodes and edges of a network.
$A,X$	The adjacency matrix and node attribute matrix.
$D$	The node degree matrix.
$n,m$	The numbers of nodes and edges.
$e_{ij}$	The edge between nodes $v_i$ and $v_j$.
$a_{ij}$	The connection between nodes $v_i$ and $v_j$.
$x_i$	The attribute vector and degree of node $v_i$.
$q$	The maximal number of node attributes.
$𝒞$	The set of communities.
$C$	The community assignments of nodes.
$k$	The numbers of communities.
$c_i$	The community which node $v_i$ belongs to.
${\omega }_r$	The probability of nodes assigned to community ${𝒞}_r$.
${\pi }_{rs}$	The probability of link generation within two communities ${𝒞}_r$ and ${𝒞}_s$.
$\delta (c_i,c_j)$	The probability of nodes $v_i$ and $v_j$ falling into the same community partition.
$E(C;A)$	The energy function in MRF.
${\mathrm{\Theta }}_i$	The unary potential function in $E(C;A)$.
${\mathrm{\Theta }}_{ij}$	The pairwise potential function in $E(C;A)$.
$KL(\cdot ||\cdot )$	KL-divergence.
$\tilde{A}$	The estimation matrix of $A$ in NMF.
$B,S$	Community membership matrix and attribute community matrix in NMF.
$H,W$	Node representation matrix and weight matrix of neural networks.
$M,L$	Modularity matrix and Laplacian matrix.
$ℱ$	The set of factor nodes.
$\widehat{A},\widehat{X}$	Reconstructed adjacency matrix and node attribute matrix.
$𝒢,𝒟$	The generator and discriminator of GAN.
$ℰ$	The encoder that derives node representation.

附录B

在第 3.1.1 节中，我们引入了几种用于社区检测的 SBM 变体。 在这里，我们给出了基于具有伯努利分布[28]、MMSB [29]和DSBM [56]<的基本SBM的社区检测的整体过程。 /t2>分别在算法1、算法2和算法3中。

Input: $n$, $k$.

Output: the community assignments of nodes $C$.

1 Assume that nodes are independently divided into $k$ communities;

2 Inference the parameters $\omega$, $\pi$ of likelihood function by using EM algorithm;

3 for each node $v_i$ do

4 for each node $v_j$ do

5 $c_i\stackrel{i\cdot i\cdot d}{\sim }\mathrm{Multinomial}(1;\omega )$;

6 ;

7

8

9return $C$;

Algorithm 1 The basic SBM-based method [28]

Input: $n$, $k$, $\alpha$, $\beta$.

Output: the community assignments of nodes $C$.

1 for each node $v_i$ do

2 ${\omega }_i\sim \mathrm{Dirichlet}(\alpha )$;

3 Assigns the community assignments $c_i$ with ${\omega }_i$;

4 for each node $v_j$ do

5

6 ;

7 $a_{i\to j}\sim \mathrm{Multinomial}({\omega }_i)$;

8 $a_{i\leftarrow j}\sim \mathrm{Multinomial}({\omega }_j)$;

9 $a_{ij}\sim \mathrm{Bernoulli}(a_{i\to j}^T{\pi }_{rs}{a}_{i\leftarrow j})$;

10

11return $C$;

Algorithm 2 The MMSB-based method [29]

Input: $n,\pi ,A,T$.

Output: the community assignments of nodes $C^{(T)}$.

1 if time $t==1$ then

2 generate the social network followed by SBM;

3for each time $t>1$ do

4 generate ;

5for each pair of nodes $(v_i,v_j)$ at time $t$ do

6 generate ;

7

8return $C^{(T)}$;

Algorithm 3 The DSBM-based method [56]

附录C

在 3.1.2 节中，我们提出了几种用于社区检测的主题模型。 这里，我们给出了算法4中一个社交互动简档的SSN-LDA[69]的生成过程，并提供了算法中属性社区[72]的聚类过程5.

Input: $k,\overrightarrow{\alpha },\overrightarrow{\beta },\epsilon .$

Output: the community assignment of one node $c_i$.

1 sample mixture components $\overrightarrow{\varphi }\sim \mathrm{Dirichlet}(\overrightarrow{\beta })$;

2 choose $\overrightarrow{{\theta }_i}\sim \mathrm{Dirichlet}(\overrightarrow{\alpha })$;

3 choose $N_i\sim \mathrm{Poisson}(\epsilon )$;

4 for each neighbor $v_j$ of $v_i$ do

5 choose a community $c_i\sim \mathrm{Multinomial}(\overrightarrow{\theta })$;

6 choose a social interaction $a_{ij}\sim \mathrm{Multinomial}(\overrightarrow{{\varphi }_{c_i}})$;

7return $c_i$;

Algorithm 4 The SSN-LDA method [69]

Input: $n,k,T,𝒞$, a time attributes set $\mathrm{\Lambda }=\{{\lambda }^{(1)},\mathrm{\dots },{\lambda }^{(T)}\}$, parameters $\epsilon ,\mu ,\nu$.

Output: the community assignments of nodes $C$, attribute matrix $X$.

1 choose $\alpha \sim \mathrm{Dirichlet}(\epsilon )$;

2 for ${𝒞}_i\in \{{𝒞}_1,{𝒞}_2,\mathrm{\dots },{𝒞}_k\}$ do

3 for each attribute ${\lambda }^{(t)}$ do

4 choose ${\theta }_i^{(t)}\sim \mathrm{Dirichlet}({\lambda }^{(t)})$;

5 for each community ${𝒞}_j\in \{{𝒞}_i,{𝒞}_{i+1},\mathrm{\dots },{𝒞}_k\}$ do

6 choose ${\varphi }_{ij}\sim \mathrm{Beta}(\mu ,\nu )$;

7

8for each node $v_i$ do

9 choose $c_i\sim \mathrm{Multinomial}(\alpha )$;

10 for each attribute ${\lambda }^{(t)}$ do

11 choose $x_i^{(t)}\sim \mathrm{Multinomial}({\theta }_{c_i}^{(t)})$;

12 for each node $v_j$ with $i>j$ do

13 choose ;

14

15return C, X;

Algorithm 5 The generation of Bayesian attributed graph clustering (BAGC) [72]