GN 算法[1]是社区发现中的第一个算法，也就是它开启了这个研究领域。GN 算法是一个经典的社区发现算法

GN 算法

GN 算法[1]是社区发现中的第一个算法，也就是它开启了这个研究领域。GN 算法是一个经典的社区发现算法，它属于分裂的层次聚类算法，最初，由 Michelle Girvan 和 Mark Newman 提出,2004 年 Newman 又提出了加权的 GN 算法，用以进行加权网络的划分.

重要概念

边介数（betweenness）：网络中任意两个节点通过此边的最短路径的数目。

GN 算法的思想：

在一个网络之中，通过社区内部的边的最短路径相对较少，而通过社区之间的边的最短路径的数目则相对较多。下图中展示了变得强度以及边介数在现实网络中的分布情况。GN 算法是一个基于删除边的算法，本质是基于聚类中的分裂思想，在原理上是使用边介数作为相似度的度量方法。在 GN 算法中，每次都会选择边介数高的边删除，进而网络分裂速度远快于随机删除边时的网络分裂。

GN 算法的步骤如下：

（1）计算每一条边的边介数； （2）删除边界数最大的边； （3）重新计算网络中剩下的边的边阶数； （4）重复(3)和(4)步骤，直到网络中的任一顶点作为一个社区为止。

GN 算法的准确性很好，但是时间复杂度却太高，GN 算法计算边界数的时间复杂度为 O(mn)，总时间复杂度在 m 条边和 n 个节点的网络下为 O(m2n)。

GN 算法的缺陷：

（1）不知道最后会有多少个社区； （2）在计算边介数的时候可能会有很对重复计算最短路径的情况，时间复杂度太高； （3）GN 算法不能判断算法终止位置。 为了解决这些问题，Newman 引入了模块度 Q 的概念，它用来一个评价社区结构划分的质量。网络中的社区结构之间的边数并不是绝对数量上的少，而是应该比期望的边数要少。关于模块度的概念请参考社区划分的标准–模块度。

k-团渗透算法(CPM 算法-Cluster Percolation method)

k-团渗透算法(CPM)[3]是第一个能够发现重叠社区的算法，重叠社区指的是结点可以同时属于多个社区。重叠社区在社交网络中是十分常见的，因为每个人都有着多种多样的社交关系。

重要概念

派系：派系过滤 CPM 方法(clique percolation method)用于发现重叠社区，派系(clique)是任意两点都相连的顶点的集合，即完全子图。 1）完全子图/全耦合网络/k-派系：所有节点全部两两相连

这些全耦合网络也成为派系，k-派系表示该全耦合网络的节点数目为 k

1）k-派系相邻：两个不同的 k-派系共享 k-1 个节点，认为他们相邻

2）k-派系连通：一个 k-派系可以通过若干个相邻的 k-派系到达另一个 k-派系，则称这两个 k-派系彼此联通

思路

  1. 第一步首先找到网络中大小为 K 的完全子图，例如图 2 中 k=3 的完全子图有{1, 2, 3} {1, 3, 4} {4, 5, 6} {5, 6, 7} {5, 6, 8} {5, 7, 8} {6, 7, 8}
  2. 第二步将每个完全子图定义为一个节点，建立一个重叠矩阵
  3. 第三步将重叠矩阵变成社团邻接矩阵，其中重叠矩阵中对角线小于 k，非对角线小于 k-1 的元素全置为 0
  4. 从图中可以看出包含了两个社区{1，2，3，4}和{4，5，6，7，8}，节点 4 属于两个社区的重叠节点

注意事项

CPM 算法不适用于稀疏矩阵，K 的取值对结果影响不大，一般实验证明 4-6 为最佳

由于 k 是个输入参数值，从而 k 的取值将会影响 CMP 算法的最终社区发现结果，当 k 取值越小社区将会越大，且社区结构为稀疏。但是实验证明 k 的取值影响不是很大，一般 k 值为 4 到 6。然而，由于该算法是基于完全子图，因此 CPM 比较适用于完全子图比较多的网络，即边密集的网络，对于稀疏网络效率将会很低，且该算法还无法分配完全子图外的顶点。CPM 的效率取决于寻找所有极大完全子图的效率，尽管寻找所有极大完全子图是 NP 完全问题，但在真实网络上是非常快的。

LPA：标签传播算法(Label Propagation)

基本思想是：

将一个节点的邻居节点的标签中数量最多的标签作为该节点自身的标签。给每个节点添加标签（label）以代表它所属的社区，并通过标签的“传播”形成同一标签的“社区”结构。简而言之，你的邻居属于哪个 label 最多，你就属于哪个 label。该算法的有点是收敛周期短，除了迭代次数无需任何先验参数(不需事先指定社区个数和大小)，算法执行过程中不需要计算任何社区指标。

时间复杂度：

对顶点分配标签的复杂度为 O(n)，每次迭代时间为 O( m)，找出所有社区的复杂度为 O (n +m)，这是一次迭代的时间复杂度，非多次。标签传播算法的计算复杂度十分便宜，但是它不保证收敛，且迭代次数足够多之后，所有联通节点最终收敛为一个社区。

基本的标签传播算法(LPA)[6]的思想非常简单，就是让每个结点与它的大多数邻居在同一个社区中。具体算法流程为：初始化，每个结点携带一个唯一的标签；然后更新结点的标签，令其标签与它的大多数邻居的标签相同，若存在多个则随机选择。迭代直至每个结点的标签不再变化。

LPA 算法的优点是简单、快速接近线性时间，5 次迭代就可使 95%的结点标签稳定。缺点是算法结果不稳定，多次执行可能得到的结果都不同。

针对基本的标签传播算法有时会形成过大(“monster”)的社区，[7]提出一个令标签跳跃衰减的方法。初始时给每个标签权重为 1.0，在更新结点标签时，令其与它的邻居标签中权重最大的相同，并令权重损失一部分。

传播过程：

1)初始时，给每个节点一个唯一的标签；

2)每个节点使用其邻居节点的标签中最多的标签来更新自身的标签。

3)反复执行步骤 2)，直到每个节点的标签都不再发生变化为止。