论文地址
推荐直接看原文。
译文

深度学习分类框架，包括基于深度神经网络、深度非负矩阵分解和深度稀疏滤波的深度学习模型，并进一步将深度神经网络模型细分为卷积网络，图注意网络，生成对抗网络和自编码器。

对于一些小型的网络和简单的场景，研究人员已经提出了一系列基于谱聚类、统计推断等传统技术的社区发现方法。然而，由于计算及存储空间成本巨大，这类方法并没有扩展到大型网络或具有高维特征的网络上。在现实世界的网络中，大量的非线性结构信息使传统的模型并不能够很好地应用于实际场景。因此，我们需要发展出具有良好计算性能的更强大的技术。如今，针对这一问题，深度学习从以下3个方面给出了最为灵活的解决方案：（1）学习非线性网络属性，如节点之间的关系；（2）提供能够保留复杂网络结构特征的低维网络表示；（3）利用更多信息进行社区发现以提高性能。

符号与定义：

如果节点$V$有属性 X = { x i } 1 n X = \{x_i\}_1^n X={xi​}1n​ ，$G=(V,E,X)$ 为属性网络，其中$X_i\subseteq R^d$ 表示节点 $v_i$的属性向量，否则 $G$为无属性网络。当网络随时间 $t$演化时，即为动态网络 $G(t)=(V_t,E_t)$或时态网络 $G(t)=(V,E,X_t)$。

• 社区发现输入： 基于深度学习的社区发现模型将网络结构和其它属性信息作为输入，如节点属性和带符号的边。网络结构是以节点和边代表的拓扑关系。边上的权重代表连接强度。节点属性代表节点的语义信息，例如在线社交网络中用户的账号信息。带符号的边代表连接状态，如正连接（+）和负连接（-）。
• 社区发现输出： 社区发现模型的输出通常是一些将节点和边分组后的社区，这些社区可以是重叠或非重叠的。。

社区发现的发展：

传统方法在网络结构上进行社区发现，它们大致可以分为7类，但只能发现浅层关联，因此结果往往是次优的。而基于深度学习的社区发现方法可以发现深层的网络信息和复杂的关系、处理高维数据。

传统社区发现方法与基于深度学习的社区发现方法：

发展历史：

七类传统方法：

图划分(Graph Partition):
此类方法也被称为图聚类，它将网络划分为 k 个社区。社区内的边要比社区之间的边更为稠密。代表性的算法包括：Kernighan-Lin 启发式方法、谱二分法等。此类方法在深度学习方法中仍然被使用。

统计推断(Statistical Inference)：
代表性的算法为随机块模型（SBM），这是一类被广泛使用的生成式模型，它将节点分配到社区中，并控制它们的似然概率。其变体包括：DCSBM、MMB、OSBM等。

层次聚类(Hierarchical Clustering)：
此类方法通过分裂式、凝聚式和混合式三种方式发现不同层次上的社区结构。Girvan-Newman（GN）算法通过分裂式方法依次删除网络中的边从而发现新的社区，输出一种关于社区结构的层次化树状表征。FastQ(FN算法)是一种凝聚式算法，它逐渐将节点合并为一个社区。CDASS 算法同时应用了分裂式和凝聚式策略，基于结构相似度对图进行划分，并将其合并为层次化的社区。

动力学方法(Dynamical Methods)：
随机游走利用随机游走器在一段较短的游走中陷入某个社区的趋势，是最常被用于社区发现任务的动力学方法。代表性的算法包括：WalkTrap（使用随机游走计算社区内测量接地那相似性的概率和距离）、InfoMap（利用最小长度编码描述随机游走的路径检测社区）、LPA（通过信息传播机制来识别社区）、LPAm（LPA与模块度结合）。

谱聚类(Spectral Clustering)：
网络的谱属性可以被用于社区发现任务。谱聚类基于网络的正则化邻接矩阵的归一化拉普拉斯矩阵划分节点，并且使用伪似然算法将划分结果拟合到 SBM 算法上。

基于密度的方法(Density-based Algorithms)：
此类方法的代表性算法包括：DBSCAN、SCAN、LCCD。它们通过测量实体密度来确定社区、中心和异常。LCCD特别使用密度峰值聚类算法从网络中定位结构中心，然后通过局部搜索过程将社区从确定的中心扩展到边界。

优化方法(Optimizations)：
社区发现方法利用优化算法来达到某个极值，通常期望表明社区的似然。最经典的优化函数为Modularity(Q) 及其变体FastQ，它被用来估计网络划分得到的社区结构。Louvain是另一种著名的优化算法，它采用节点移动策略提取具有更大网络模块度的社区结构。此外，贪婪优化方法还包括模拟退火、极值优化、以及谱优化。演化社区发现方法在局部学习和全局搜索中十分有效，它分为单目标优化和多目标优化。多智能体遗传算法（MAGA-Net）等单目标优化算法利用了模块度函数，而 Combo等算法则融合了归一化互信息(NMI)、Conductance(CON)在内的多个优化目标。CE-MOEA 算法基于非支配排序遗传算法（NSGA-II）来优化模块度和相似性目标。

为什么需要深度学习进行社区发现？ 特别是在大型复杂网络中，深度学习模型具有利用节点、邻域、边、子图等的高维非线性特征（即网络拓扑信息）和高维关系特征（即网络属性信息）并对特征进行编码的优势。 这样的模型对稀疏网络更具弹性，并且更适合现实世界场景中的无监督学习任务。

深度学习社区发现的分类：

本文提出了一个针对基于深度学习的社区发现方法的分类框架。该框架将相关方法总结为六类：卷积网络、图注意力网络 (GAT)、生成对抗网络 (GAN)、自编码器 (AE)、深度非负矩阵分解 (DNMF) 和深度稀疏过滤 (DSF)。卷积网络包括卷积神经网络（CNN）和图卷积网络（GCN）。AE 进一步分为堆叠 AE、稀疏 AE、去噪 AE、图卷积 AE、图注意力 AE 和变分 AE (VAE) 等子类别。

基于卷积网络的社区发现：

卷积神经网络（CNN）是一种针对网格式拓扑数据，如图像数据，而提出的前馈深度神经网络（DNN），其中卷积层降低了计算成本，而池化操作保证了 CNN 在特征表达上的鲁棒性。图卷积网络（GCN）是基于CNN 和图的局部谱滤波器的一阶近似而提出的用于图结构数据的卷积网络模型。GCN中使用的传播规则设计为：
$$H^{(l+1)}=\sigma ({\tilde{D}}^{-\frac{1}{2}}\tilde{A}{\tilde{D}}^{-\frac{1}{2}}{H}^{(l)}{W}^{(l)})$$
其中，$H^{(l)}$ 通过激活函数$\sigma (\cdot )$ 和层特定的可训练权重矩阵$W^{(l)}$保留第$l层中的潜在表示矩阵(H^{(0)}=X)；\tilde{A}=A+I_n为无向图G加入自连接后的邻接矩阵，I_n是单位矩阵；{\tilde{D}}_{ii}={\sum }_j{\tilde{a}}_{ij}，其中{\tilde{a}}_{ij}\in \tilde{A}。$

基于CNN的社区发现:

现有的基于CNN的社区发现方法具有严格的数据输入限制：需要是图像格式数据和带标签数据。 因此，这些方法需要对其输入进行预处理：（1）将网络样本映射为图像数据格式，以及（2）提前手动标记节点或社区，因为大多数现实世界的网络没有标签。 下图展示了基于 CNN 的社区发现方法的通用框架：

由于CNN模型通常仅处理图像数据(image)，当输入数据为图(graph)时，必须根据节点或边对数据进行预处理。总体框架中，CNN的隐藏层可以对数据的d维潜在特征进行卷积映射，接下来，由全连接层输出每个节点或每条边的表示以进行社区的分类。根据节点进行数据预处理时，图中的工作流①将节点分类为k类(即k个社区)，具有相同标签的节点会被划分到同一个社区中;根据边进行数据预处理时，工作流②将边分为两类——社区内与社区间的边。训练过程中，通过删除社区间的边形成社区结构，并通过反向传播到CNN嵌入中进行优化，从而得到最佳的社区划分结果，如模块度Q。

基于GCN的社区发现：

GCN在深度图卷积层中聚合节点的邻域信息，从而可以从全局捕获用于社区发现的复杂特征。基于GCN的社区发现方法有两类：(1)监督/半监督社区分类；(2)基于无监督网络表示的社区聚类。社区分类方法受到现实世界中缺乏标签的限制，相比之下，网络表示方法通过矩阵重构和目标优化等技术更灵活的聚类社区。下图展示了GCN通常如何应用于社区发现。

一个基于GCN的社区检测的通用框架。它输入一个图结构(A)和可能的节点属性(X)。在多个图卷积网络(GCN)层中，基于社区检测要求来平滑图的潜在特征(信息聚合)。图表示学习是通过σ(·)作激活函数的。四个社区检测框架在工作流①-④中，应用最终的节点表示(①和②)或隐藏层的特征表示(③和④)。①基于给定节点的标签，使用节点分类检测社区，②通过嵌入(H)对节点实现聚类，③中通过评估（例如互信息MI）进一步优化节点表示，以获得最佳的社区关系。④同时优化聚类结果和GCN表示，根据卷积表示节点嵌入，逐步将每个节点检测到社区中。

下表对比了一些基于GCN的方法。

基于图注意力网络GAT的社区发现：

基于图注意力网络（GAT）的社区发现方法可以发现复杂网络场景中的社区。框架如下图所示：
GAT在每个隐藏层I中为每个节点及其相邻的节点之间分配注意力系数(图中绿色，蓝色，紫色的箭头所示)。不同工作流所代表的向量分别聚合了所有的可用星系：①多层网络中同一对节点之间的多种关系；②异构网络中的语义路径。通过将社区结构分析嵌入到GAT表示汇总，将输出嵌入H应用于社区发现。

基于生成对抗网络GAN的社区发现：

对抗性训练在生成模型中是有效的，可以提高判别能力，但在应用于社区发现时需要解决过拟合问题。 生成对抗网络 (GAN) 在对抗训练中，在生成器${\varphi }_g$和判别器${\varphi }_d$之间进行竞争。 表示输入${\varphi }_d(x)$数据的概率，而 ${\varphi }_g$(z)学习生成器在输入噪声变量 $p_z(z)$上的数据 x上的分布 $p_g$。生成器通过生成假样本来欺骗鉴别器。其目标函数定义为：

基于GAN的社区发现总体框架。在基于GAN的社区发现方法中，GAN通过生成器生成人造样本来欺骗判别器，判别器将多层感知机、图神经网络等深度神经网络作用于表征上。因此，真实样本和人造样本会通过竞争博弈进行调优，从而得到最优的社区特征。GAN中使用的真实样本包括:①拓扑结构A;②)拓扑结构与节点属性(A，X);③节点嵌入;④节点的社团归属。网络的拓扑结构以三元组、派系、社区等形式在表征或GAN模型中得到分析。这类方法能够在融合网络拓扑、属性和表征的过程中发现社区。

基于自编码器AE的社区发现：

自编码器(AE)是最常被用于无监督社区发现的模型，社区发现中常见的AE变体包括堆叠AE、稀疏AE、去噪AE、卷积AE、变分AE。AE 能够描绘非线性、有噪声的现实世界网络并产生平滑的表示。AE的通用框架由编码器$Z={\varphi }_r(A,X)$和解码器$X^{\prime }={\varphi }_r(Z)$构成。编码器 ( ${\varphi }_e$) 将高维网络结构 ( A ) 和可获取的属性 (X) 映射到低维潜在特征空间 (Z)。解码器 (${\varphi }_r$) 则根据编码器得到的表示 (H) 进行网络重构 (Z )，其中 X’继承了 A和 X中的首选信息。损失函数$L(x,{\varphi }_r({\varphi }_e(x))$ 最大化源数据x 和解码数据 ${\varphi }_r({\varphi }_e(x))$之间的似然。
基于堆叠自编码器的社区发现：
基于堆叠AE的社区发现总体框架。堆叠AE在多个隐层中将一组AE堆叠起来，以更加灵活地处理丰富的输入。我们在静态图、动态图.
跨域图、异构图中，分别考虑各种社区信息(A:邻接矩阵;A(+，-):带符号邻接矩阵; X:节点属性; B:模块度矩阵; O:节点对社区归属的先验信息矩阵; S︰节点对相似矩阵; {Aij}:锚链接矩阵）的5个代表性工作流，5种工作流都使用了成对约束和重建损失优化。在工作流①中，其输入为拓扑结构（(A或B)，优化重建损失和KL损失，输出最终用于节点聚类的嵌入Z。在工作流②中，输入为动态图的快照（At)，然后使用与工作流①中相同的堆叠AE嵌入过程。基于当前嵌入(Zt)和前一时刻嵌入(Z(t-1)的时序平滑性进行聚类，从而集成与前一时刻社区C(t-1)相似的当前社区结构Ct。在工作流③中，输入为拓扑结构(A或B)和节点属性 (X)，使用两个堆叠AE对这些属性进行表征，并同时使用重建损失优化由拓扑结构得到的嵌入和由节点属性得到的嵌入($Z^{A/B},Z^X$)。在工作流④中，将源域节点对的相似度信息迁移到目标域中。为了分析跨域的关系，通过同时在两个域上最小化可训练变量的损失，旨在最小化源域Zs,和目标域Zt嵌入的KL损失。因此，社区发现任务是在两个域的Zt编码图上进行的。在工作流⑤中，输入为不同元路径中对齐后的图，以及图i和图j之间的锚链接矩阵(Aij)。对于每一个Aij，最小化2-范数损失$||Z_1,Z_2|{|}_2$,和所有的损失都被赋予了堆叠AE权重。社区发现基于堆叠AE所得的嵌入进行聚类。

基于稀疏自编码器的社区发现：

稀疏性普遍存在于现实世界的网络中，并导致社区发现算法的计算困难。为了解决这一问题，稀疏 AE在隐藏层h中引入了稀疏惩罚$\Omega (h)$ 。重构损失函数如下：
GraphEncoder (Autoencoder-based Graph Clustering Model) 是第一个使用 AE 进行图聚类的研究。 它通过作为以下损失函数（最小化）的一部分的稀疏项来处理稀疏性：
GraphEncoder 提高了大规模网络的聚类效率，并证明了稀疏网络可以为表示提供足够的结构信息。

CDMEC (Community Detection Method via Ensemble Clustering) 的社区发现方法将稀疏 AE 与迁移学习模型相结合，以从局部网络结构中发现更多有价值的信息。

Dfuzzy (Deep Learning-based Fuzzy Clustering Model)用于并行处理框架下稀疏大规模网络中的重叠社区发现。

基于降噪自编码器的社区发现:

降噪过程减去了 DNN 层内的噪声。 降噪 AE能够处理损坏的输入数据 ($\tilde{x}$) 并最小化去噪数据 (x ) 和解码数据之间的重构损失：
DNGR (Deep Neural Networks for Graph Representation)是在具有 3 个隐藏层的堆叠降噪自编码器框架中设计的。DNGR 应用堆叠降噪编码器来增加发现社区时捕获局部结构信息的鲁棒性。具体来说，它通过随机遍历社区来生成概率共现矩阵，并将其转换为移位的正逐点 MI 矩阵作为输入。

对于损坏的节点属性，GRACE (GRAph Clustering with dynamic Embedding)是一个非线性多层 DNN 的降噪 AE，由邻域内的影响传播引导，以发现动态变化的社区间活动，通过自训练聚类达到了有效的社区发现性能。

MGAE (Marginalized Graph AutoEncoder )对图的属性和结构进行降噪，以通过边缘化过程改进社区发现。它在 m 次内获得损坏的特征 $\tilde{X}$。MGAE训练中的目标函数定义为：
其中 L(W)表示系数为 $\lambda$的参数 W的正则化项。

基于卷积自编码器的社区发现:

将 GCN 引入 AE 是一个巨大的成功，因为 GCN 提供了高阶图正则化，而 AE 缓解了 GCN 中的过度平滑问题。 例如，基于 GCN 的无监督社区检测 (GUCD) 方法采用半监督 MRF 作为 GCN 中的卷积层（即MRFasGCN)作为其编码器，并提出了一种以社区为中心的双重解码器来检测属性网络中的社区。具体来说，GUCD使用一个解码器重构网络拓扑，另一个解码节点属性，以直接识别社区结构。

SDCN (Structural Deep Clustering Network)设计了一个传递算子来在 DNN 层上连接 AE 和 GCN，从而使图卷积可以完全支持 AE 的结构表示。当 SDCN 将结构信息集成到深度聚类中时，它通过分别对 AE 和 GCN 应用双重自监督优化来更新社区。

O2MAC (One2Multi Graph Autoencoder for Multi-view Graph Clustering 是一种针对多视图属性图的，由单视图到多视图 (One2Multi) 的图聚类 AE。它由一个编码器和多个解码器组成。在编码器中，应用 GCN 来嵌入一组视图分隔图。同时将解码器分别分配给这些单视图，并与编码器共同选择包含信息最多的单视图。O2MAC 能够捕获多视图之间的共享特征，并通过自训练优化改进聚类结果。

基于图注意力自编码器的社区发现:

该类别的社区发现方法不是集成 GCN，而是将 GAT 应用于 AE。DAEGC (Deep Attentional Embedded Graph Clustering) 采用 GAT 作为编码器对邻域内属性节点的重要性进行排序，利用高阶邻域来聚类社区。 多视图网络有两种基于 GAT 和 AE 的社区发现方法。MAGCN (Multi-View Attribute Graph Convolution Networks ) 设计了一个双路径编码器：第一个路径使用能够去噪的多视图属性 GAT 进行编码，第二个路径设计了一个编码器以在多视图属性上获得一致的嵌入。因此，MAGCN 为社区发现任务去除了噪声和分布方差。DMGC (Deep Multi-Graph Clustering)引入了 AE 来表示每个图的注意力系数，多个图的节点嵌入将通过跨图质心聚类以获得 Cauthy 分布上的社区。

基于变分自编码器的社区发现:

变分自动编码器（VAE）是基于变分推理（如特征的均值和协方差）的 AE 的扩展。它由变分图自编码器（VGAE） 首次引入图学习领域，它假设高斯分布并应用 GCN 作为编码器。基于 VAE 的社区发现由 SBM 等模型激活，以快速推断节点表示中的社区归属。推理过程考虑了网络的不确定性，例如连接多个社区的边界节点的邻居之间的社区矛盾。VAE 还可以处理社区发现的稀疏性问题。同时，VAE 很容易与更深层次的非线性关系信息相结合。例如，TGA/TVGA (Triad Variational Graph Autoencoder ) 用新的 triad 解码器替换了 VAE/VGAE 的解码器，它描述了现实世界的社区中现有的三元闭包属性。

基于深度非负矩阵分解的社区发现:

非负矩阵分解旨在将一个矩阵分解成两个小的非负矩阵，该方法具有高度的可解释性，能够发现如何将节点分配给社区。应用于社区发现的基本 NMF 模型将邻接矩阵 A) 分解为两个非负矩阵 ( $U\in R^{n\times k}和P\in R^{n\times k}$)，其非负约束为 $P\ge 0$ 和 $U\ge 0$ 。矩阵U 对应于原始网络和社区归属空间之间的映射。矩阵$P=[p_{ij}]$的每一列表示节点vi属于社区 cj的归属强度为概率 pij 。NMF 适用于非重叠和重叠的社区发现。由于现实世界的网络包含复杂的拓扑信息，传统的 NMF 无法完全揭示它们来检测社区。受深度学习成功的启发，人们对深度 NMF 进行了广泛的研究，它堆叠多层 NMF ( {$U_1,...,U_p$} ) 以捕获各个级别/方面的节点成对相似性.

基于稀疏滤波的社区发现:

稀疏滤波是一种简单的双层学习模型，它可以处理高维的图数据，将高度稀疏的输入表征为低维特征向量。高度稀疏的输入（具有很多 0 元素的 ）将被表示为低维特征向量（具有非零值的 ）。为了探索节点的社团归属等更深入的信息，深度SF将多个隐层堆叠起来，从而对更多超参数 ( $\Theta$) 和大量的平滑数据分布($Pr(h_i)$ )进行调优。

DSFCD (Community Discovery based on Deep Sparse Filtering) 作为一种代表性的方法，可以分为三个步骤：网络表示、社区特征映射和社区发现。 网络表示阶段分别在邻接矩阵 ( A)、模块度矩阵 (B ) 和两个相似性矩阵 (S 和 S") 上执行。选择最佳表示输入到深度 SF 中，以获得在每个节点上表示的社区特征映射(hi ) 。同时， 保留了原始网络( A)中的节点相似性和潜在社区归属特征。节点成对约束在损失函数中建模：
其中$||\cdot |{|}_1$是优化稀疏度的L1范数惩罚， $h_j^{\ast }$为节点 的最相似表示，通过在 Euclidean 或 KL 上计算 distance(hi,hj)距离得到。在最小化损失上优化学习过程中，相似的节点会聚集到同一社区中。深度 SF 架构在现实世界数据集的实验中具有重要意义，DSFCD 能比 SF 更准确地发现社区结构。

数据集：

评价指标

实际应用

未来方向：

未知的社区数量

社区嵌入

层次化网络

多层网络

异构网络

网络异质性

拓扑不完备的网络

跨域网络

多属性视图网络

带符号的网络

动态网络

大规模网络

Louvain 算法

原始论文为：《Fast unfolding of communities in large networks》。

所以又被称为Fast unfolding算法。

Louvain算法是一种基于模块度的社区发现算法。其基本思想是网络中节点尝试遍历所有邻居的社区标签，并选择最大化模块度增量的社区标签。在最大化模块度之后，每个社区看成一个新的节点，重复直到模块度不再增大。

首先复习下模块度：

这里引入了权重方便扩展到有权图，但其实对于无权图，可以看做所有边权重为1，这时候就等于用节点的度计算，用度理解一样。

算法详述：

1. 模块度优化阶段：每个节点将自己作为自己社区标签。每个节点遍历自己的所有邻居节点，尝试将自己的社区标签更新成邻居节点的社区标签，选择模块度增量最大(贪婪思想)的社区标签，直到所有节点都不能通过改变社区标签来增加模块度。

   也就是说，首先将每个节点指定到唯一的一个社区，然后按顺序将节点在这些社区间进行移动。怎么移动呢？假设有一节点 i ，它有三个邻居节点 j1, j2, j3，我们分别尝试将节点 i 移动到 j1, j2, j3 所在的社区，并计算相应的 modularity 变化值ΔQ，哪个变化值最大就将节点 i 移动到相应的社区中去（当然，这里我们要求最大的 modularity 变化值要为正，如果变化值均为负，则节点 i 保持不动）。按照这个方法反复迭代，直到网络中任何节点的移动都不能再改善总的 modularity 值为止。

   移动到一个社区C中所获得的模块化Q增益可以很容易地计算出来：

   =$\frac{1}{2m}(k_{i,in}-\frac{{\Sigma }_{tot}ki}{m})$

   其中${\Sigma }_{in}$是在社区C内的链路的权重总和(权重为1时就等于度数)，如果是初始情况，即一个节点作为一个社区时，它就为这个节点自己到自己的连接，这时候仍然需要起点加weight，终点加weight（即使这个时候起点和终点为同一节点，对于无环图权为0）

   ${\Sigma }_{tot}$是关联到C中的节点的链路上的权重的总和

   ki是关联到节点i的链路的权重的总和

   ki,in是从节点i连接到C中的节点的链路的总和

   m是网络中的所有链路的权重的总和

2. 网络凝聚阶段：每个社区合并为一个新的超级节点，超级节点的边权重为原始社区内所有节点的边权重之和，形成一个新的网络。

   将第一个阶段得到的社区视为新的“节点”（一个社区对应一个），重新构造子图，两个新“节点”之间边的权值为相应两个社区之间各边的权值的总和。如这个图所示，如果第一个阶段得到的社区有以下三个，那么第二个阶段的任务就是将这三个社分别看一个新的节点，然后将任意两个新节点之间的所有连线的权重相加得到的和，作为这两个新节点之间的连线的权重。

上述两个阶段迭代进行，直到模块度不再增大。
  下图很好的描述了这两个阶段。第一次迭代，经过模块度优化阶段，总的 modularity 值不再改变，算法将16个节点划分成4个社区；在网络凝聚阶段，4个社区被凝聚成4个超级节点，并重新更新了边权重。之后就进入第二次迭代中。

算法通过引入分步迭代的思想(类比EM算法)，避免陷入贪婪思想导致的局部最优。

算法流程：

1、初始时将每个顶点当作一个社区，社区个数与顶点个数相同。
2、依次将每个顶点与之相邻顶点合并在一起，计算它们最大的模块度增益是否大于0，如果大于0，就将该结点放入模块度增量最大的相邻结点所在社区。
3、迭代第二步，直至算法稳定，即所有顶点所属社区不再变化。
4、将各个社区所有节点压缩成为一个结点，社区内点的权重转化为新结点环的权重，社区间权重转化为新结点边的权重。
5、重复步骤1-3，直至算法稳定。

可以看到Louvain 算法与FN算法非常相似，我觉得最大的不同时Louvain 算法在凝聚阶段是将整个社区看做一个新的超节点来看，而FN算法是以社区的观点来凝聚。

算法优缺点

优点

1、时间复杂度低，适合大规模的网络。
  2、社区划分结果稳定，有具体指标能够评估社区划分好坏。
  3、消除了模块化分辨率的限制。由于模块度是全局指标，最大化的时候很难发现小型的社区，很容易将小型社区合并。而算法第一次迭代是以单个节点作为社区的粒度，规避了这种问题。
  4、天然自带层次化的社区划分结果，每一次迭代的社区划分结果都可以保留下来，作为社区划分的中间结果，可供选择。

缺点

1、社区过大，不能及时收敛。如果我们将模块度类比为损失函数的话，Fast Unfolding在模块度优化阶段采用的贪婪思想很容易将整个社区划分“过拟合”。因为Fast Unfolding是针对点遍历，很容易将一些外围的点加入到原本紧凑的社区中，导致一些错误的合并。这种划分有时候在局部视角是优的，但是全局视角下会变成劣的。
  
  Python代码如下：

class Louvain:
    def __init__(self, G):
        self._G = G
        self._m = 0  # 边数量 图会凝聚动态变化
        self._cid_vertices = {}  # 需维护的关于社区的信息(社区编号,其中包含的结点编号的集合)
        self._vid_vertex = {}  # 需维护的关于结点的信息(结点编号，相应的Vertex实例)
        for vid in self._G.keys():
            # 刚开始每个点作为一个社区
            self._cid_vertices[vid] = {vid}
            # 刚开始社区编号就是节点编号
            self._vid_vertex[vid] = Vertex(vid, vid, {vid})
            # 计算边数  每两个点维护一条边
            self._m += sum([1 for neighbor in self._G[vid].keys() if neighbor > vid])

    # 模块度优化阶段
    def first_stage(self):
        mod_inc = False  # 用于判断算法是否可终止
        visit_sequence = self._G.keys()
        # 随机访问
        random.shuffle(list(visit_sequence))
        while True:
            can_stop = True  # 第一阶段是否可终止
            # 遍历所有节点
            for v_vid in visit_sequence:
                # 获得节点的社区编号
                v_cid = self._vid_vertex[v_vid]._cid
                # k_v节点的权重(度数)  内部与外部边权重之和
                k_v = sum(self._G[v_vid].values()) + self._vid_vertex[v_vid]._kin
                # 存储模块度增益大于0的社区编号
                cid_Q = {}
                # 遍历节点的邻居
                for w_vid in self._G[v_vid].keys():
                    # 获得该邻居的社区编号
                    w_cid = self._vid_vertex[w_vid]._cid
                    if w_cid in cid_Q:
                        continue
                    else:
                        # tot是关联到社区C中的节点的链路上的权重的总和
                        tot = sum(
                            [sum(self._G[k].values()) + self._vid_vertex[k]._kin for k in self._cid_vertices[w_cid]])
                        if w_cid == v_cid:
                            tot -= k_v
                        # k_v_in是从节点i连接到C中的节点的链路的总和
                        k_v_in = sum([v for k, v in self._G[v_vid].items() if k in self._cid_vertices[w_cid]])
                        delta_Q = k_v_in - k_v * tot / self._m  # 由于只需要知道delta_Q的正负，所以少乘了1/(2*self._m)
                        cid_Q[w_cid] = delta_Q

                # 取得最大增益的编号
                cid, max_delta_Q = sorted(cid_Q.items(), key=lambda item: item[1], reverse=True)[0]
                if max_delta_Q > 0.0 and cid != v_cid:
                    # 让该节点的社区编号变为取得最大增益邻居节点的编号
                    self._vid_vertex[v_vid]._cid = cid
                    # 在该社区编号下添加该节点
                    self._cid_vertices[cid].add(v_vid)
                    # 以前的社区中去除该节点
                    self._cid_vertices[v_cid].remove(v_vid)
                    # 模块度还能增加 继续迭代
                    can_stop = False
                    mod_inc = True
            if can_stop:
                break
        return mod_inc

    # 网络凝聚阶段
    def second_stage(self):
        cid_vertices = {}
        vid_vertex = {}
        # 遍历社区和社区内的节点
        for cid, vertices in self._cid_vertices.items():
            if len(vertices) == 0:
                continue
            new_vertex = Vertex(cid, cid, set())
            # 将该社区内的所有点看做一个点
            for vid in vertices:
                new_vertex._nodes.update(self._vid_vertex[vid]._nodes)
                new_vertex._kin += self._vid_vertex[vid]._kin
                # k,v为邻居和它们之间边的权重 计算kin社区内部总权重 这里遍历vid的每一个在社区内的邻居   因为边被两点共享后面还会计算  所以权重/2
                for k, v in self._G[vid].items():
                    if k in vertices:
                        new_vertex._kin += v / 2.0
            # 新的社区与节点编号
            cid_vertices[cid] = {cid}
            vid_vertex[cid] = new_vertex

        G = collections.defaultdict(dict)
        # 遍历现在不为空的社区编号 求社区之间边的权重
        for cid1, vertices1 in self._cid_vertices.items():
            if len(vertices1) == 0:
                continue
            for cid2, vertices2 in self._cid_vertices.items():
                # 找到cid后另一个不为空的社区
                if cid2 <= cid1 or len(vertices2) == 0:
                    continue
                edge_weight = 0.0
                # 遍历 cid1社区中的点
                for vid in vertices1:
                    # 遍历该点在社区2的邻居已经之间边的权重(即两个社区之间边的总权重  将多条边看做一条边)
                    for k, v in self._G[vid].items():
                        if k in vertices2:
                            edge_weight += v
                if edge_weight != 0:
                    G[cid1][cid2] = edge_weight
                    G[cid2][cid1] = edge_weight
        # 更新社区和点 每个社区看做一个点
        self._cid_vertices = cid_vertices
        self._vid_vertex = vid_vertex
        self._G = G

    def get_communities(self):
        communities = []
        for vertices in self._cid_vertices.values():
            if len(vertices) != 0:
                c = set()
                for vid in vertices:
                    c.update(self._vid_vertex[vid]._nodes)
                communities.append(list(c))
        return communities

    def execute(self):
        iter_time = 1
        while True:
            iter_time += 1
            # 反复迭代，直到网络中任何节点的移动都不能再改善总的 modularity 值为止
            mod_inc = self.first_stage()
            if mod_inc:
                self.second_stage()
            else:
                break
        return self.get_communities()

参考结果如下：

社区 1 [0, 1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 12, 13, 16, 17, 19, 21]
社区 2 [32, 33, 8, 14, 15, 18, 20, 22, 26, 29, 30]
社区 3 [23, 24, 25, 27, 28, 31]
0.388560157790927
算法执行时间0.002000093460083008

​2004年，Newman在GN(Girvan and Newman, 2002)算法的基础上，提出了另外一种快速检测社区的算法，称为FN算法。该算法能得到和GN算法相似的结构，但是时间复杂度更低，GN算法的时间复杂度为$O(m^{2}n)$，FN算法的时间复杂度为$O((m+n)n)$，其中，$m$是边的数量，$n$是节点的数量。此处给出FN算法的Python实现，并给出对比实验以及社区发现的三种评价指标。

Newman, M. E. J. ,2004. Fast algorithm for detecting community structure in networks. phys rev e stat nonlin soft matter phys, 69, 066133.

去看原文

算法原理

FN算法是一种层次聚类算法。起初每个节点都是一个类。每次合并让Q值增加（即$\Delta Q$）最大的一对节点，重复这个过程，直到所有节点都在一个社区为止。在这个合并的过程中，选择Q值（社区发现评估指标）最大的作为最终划分结果。

$$\Delta Q=2(e_{ij}-a_i{a}_j)$$
其中，$e_{ij}$表示连接社区$i$和社区$j$的边的比例；$a_i$表示连接到社区$i$的所有末端节点比例，$a_i={\sum }_j{e}_{ij}$。以下是一个合并的结构图，从下往上进行合并。

评价指标

社区发现的评估指标主要有三个：互信息和标准化互信息（Normalized Mutual Information，NMI指数）、调整兰德指数（Adjusted Rand Index，ARI指数）、模块度Q（modularity Q）。

当无法获取真实社区划分结果时，可以采用模块度Q来评价。Modularity用于评判社区划分结果的优劣。模块度越大则表明社区划分效果越好，其范围在$[-0.5,1)$，论文(Newman, 2003)表示当Q值在0.3~0.7之间时，说明聚类的效果很好。

$$Q=\sum _{i=1}^n(e_{ii}-a_i^2)$$
其中$e_{ij}={\sum }_{vw}\frac{A_{vw}}{2m}$，$a_i=\frac{k_i}{2m}={\sum }_j{e}_{ij}$。
$m$表示边的数量，$e_{ij}$表示一个节点在社区$i$内，另一个节点在社区$j$内的边的比例。$e_{ii}$表示在社区$i$内所有的边与整个网络所有的边的一个比值（一个社区内部的度比上整个网络的度），而$a_i$则表示i社区内的节点的度（包含了一点在社区$i$内一点在社区$i$外的边的度）占整个网络的度比值。

可将模块度用矩阵形式表示，即
$$Q=\frac{1}{2m}Tr(S^{T}BS)$$
其中，$B_{ij}=A_{ij}-\frac{k_i{k}_j}{2m}$，$k_i$代表的是节点$i$的度，$A_{ij}$为邻接矩阵; $S$为每个节点所属社区的one-hot表示，$S_{ir}=1$表示第$i$个节点属于第$r$社区。

当已知真实社区划分结果时，可采用NMI指数和ARI指数进行评价。
1.NMI指数
如果结果越相似NMI值应接近1；结果很差则NMI值接近0。
$$NMI(X,Y)=\frac{2MI(X,Y)}{H(X)+H(Y)}$$
其中，$MI(X,Y)={\sum }_{i=1}^{|X|}{\sum }_{j=1}^{|Y|}P(i,j)log(\frac{P(i,j)}{P(i)P^{\prime }(j)})$；$H(X)=-{\sum }_{i=1}^{|X|}P(i)log(P(i))$；$H(Y)=-{\sum }_{j=1}^{|Y|}{P}^{\prime }(j)log(P^{\prime }(j))$，$X，Y$是划分类别唯一标签和真实类别唯一标签。

以下将用一个例子来介绍如何计算。
输出的划分结果：A=[1 2 1 1 1 1 1 2 2 2 2 3 1 1 3 3 3]
真实的划分结果：B=[1 1 1 1 1 1 2 2 2 2 2 2 3 3 3 3 3]

那么$X=unique(A)=[1,2,3]，Y=unique(B)=[1,2,3]$，
$P(i,j)$表示同时属于社区$i$和社区$j$的节点的联合概率，$P(i,j)=\frac{|X_i\bigcap Y_j|}{N}$,$N$为节点数,$i\in X,j\in Y$；
$P(i),P(j)$分别为类别$i,j$的概率分布，$P(i)=\frac{|X_i|}{N},P^{\prime }(j)=\frac{|Y_j|}{N}$；
$H(X),H(Y)$分别为$X,Y$的信息熵。
所以$P(X)=[8/17,5/17,4/17]$，$P(Y)=[6/17,6/17,5/17]$
$$P(X,Y)=\left[\begin{array}{ccc}5/17& 1/17& 2/17\\ 1/17& 4/17& 0\\ 0& 1/17& 3/17\end{array}\right]$$
因此，$MI(X,Y)=sum(P(X,Y)\ast log(P(X,Y)/(P(X{)}^{T}P(Y))))$，$H(X)=-P(X)log(P(X{)}^T)$，$H(Y)=-P(Y)log(P(Y{)}^T)$，则$NMI(X,Y)=0.3646$

[1] Detecting the overlapping and hierarchical community structure in complex networks

2.ARI指数
兰德指数（RI指数）是两种划分$X,Y$中顶点对正确分类的数量（顶点对在同一个社团中或者在不同的社团中）与总的顶点对的数量的比值，可以使用下式表示：
$$RI(X,Y)=\frac{a_{00}+a_{11}}{a_{00}+a_{01}+a_{10}+a_{11}}=\frac{a_{00}+a_{11}}{C_2^n}$$
其中，$a_{00}$表示在真实社团划分与实验得到的社团划分里都不属于同一社团的点对数目；$a_{11}$表示在真实社团划分与实验得到的社团划分里都属于同一社团的点对数目；$C_2^n$指可以组成的总顶点对对数。$RI$取值范围为$[0,1]$，值越大意味着两种划分结果越吻合。然而$RI$会存在区分度不高的情况。因此为了提高区分度，提出了ARI指数：
$$ARI=\frac{RI-E(RI)}{max(RI)-E(RI)}$$
$ARI$取值范围为$[-1,1]$，值越大意味着两种划分结果越吻合。从广义的角度来讲，ARI衡量的是两个数据分布的吻合程度。

结果对比

为了验证FN算法的结果质量和计算效率，采用了3个不同的测试案例来和GN算法进行对比实验。

以下是实验结果（football网络有真实划分结果，分割线|前的为GN算法，后为FN算法，即GN | FN）：

可以看出，FN算法的结果质量稍逊于GN算法，但是计算效率更高。

以下是dolphins网络中两个算法结果的可视化：
FN算法结果（4个社区）：

GN算法结果（5个社区）：

源码

原文有源码，去看原文

一种高效实现

FN算法的一种高效实现
FN算法的一种高效实现
FN算法的一种高效实现

更多内容，请关注地学分析与算法。