社区检测_社区检测算法

1.Kernighan–Lin二部算法

属于图分割方法。
核心思想：通过对节点的迭代交换将网络分割成两组，以减少两组节点之间的边缘切割。
Kernighan-Lin算法可描述为下面的步骤：
Step1：给定N个节点的图，随机划分图节点到两个指定规模大小的 n1,n2 群组；
Step2：分别从 n1,n2 群组中选择节点i和节点j组成顶点对(i, j)，交换i和j的位置，并计算交换前后群组之间割集规模的变化量并记录该变化量P；
Step3：重复上步骤，已交换过的节点不再参与；
Step4：直到没有可以交换的顶点对，算法结束。
需要注意的是，在顶点对交换的过程中，P值并不一定是单调增加的。不过，即使某一步的交换会使P值有所下降，仍然可能在其后的步骤中出现一个更大的P值。当交换完毕后，便找到上述交换过程中所记录的最大的P值，这时对应的割集规模达到最优。这是一种贪婪算法，从初始解开始搜索，直到从当前的解出发找不到更优的候选解，然后停止。
缺点：只能分成两个社区，计算量很大，而且容易受初始划分结果的影响。
(1)原文:Link
Kernighan B W, Lin S. An efficient heuristic procedure for partitioning graphs[J]. The Bell system technical journal, 1970, 49(2): 291-307.
(2)介绍和对算法的改进: link.
(3)code: kernighan_lin_bisection(G, partition=None, max_iter=10, weight=‘weight’, seed=None)

2.派系过滤算法（cliquepercolationmethod，CPM）

核心思想：CPM算法是最早的重叠社区发现算法，它的思想是基于团渗透理论的，认为社区是具有共享节点的全连通子图集合，并通过一种团过滤算法来识别网络中的社区结构。
Step1：设定k，找到大小为k的所有完全子图（全连接）；
Step2：将每个完全子图看成节点，建立重叠矩阵；
Step3：将重叠矩阵变成社团邻接矩阵，其中重叠矩阵中对角线小于k，非对角线小于k-1的元素全置为0。这样，有连边的k完全子图是一个大的社团，其中会存在重叠的节点。
算法介绍：Link
维基定义：Link
原文：Link
code:k_clique_communities(G, k, cliques=None)

3.GN算法

思想：在一个网络之中，通过社区内部的边的最短路径相对较少，而通过社区之间的边的最短路径的数目则相对较多。GN算法是一个基于删除边的算法，本质是基于聚类中的分裂思想，在原理上是使用边介数作为相似度的度量方法。在GN算法中，每次都会选择边介数高的边删除，进而网络分裂速度远快于随机删除边时的网络分裂。
GN算法的步骤如下：
Step1：计算每一条边的边介数；
Step2：删除边界数最大的边；
Step3：重新计算网络中剩下的边的边阶数；
Step4：重复(3)和(4)步骤，直到网络中的任一顶点作为一个社区为止。
缺点：
（1）不知道最后会有多少个社区；
（2）在计算边介数的时候可能会有很对重复计算最短路径的情况，时间复杂度太高；
（3）GN算法不能判断算法终止位置。
原文：Finding and evaluating community structure in networks
为了解决这些问题，Newman引入了模块度Q的概念，它用来一个评价社区结构划分的质量。网络中的社区结构之间的边数并不是绝对数量上的少，而是应该比期望的边数要少。

模块度（Modularity）用来衡量一个社区的划分是不是相对比较好的结果。一个相对好的结果在社区内部的节点相似度较高，而在社区外部节点的相似度较低。
模块度的大小定义为社区内部的总边数和网络中总边数的比例减去一个期望值，该期望值是将网络设定为随机网络时同样的社区分配所形成的社区内部的总边数和网络中总边数的比例的大小。

4.快速Newman算法

GN算法通过模块度可以准确的划分网络，但它只适用于中小型规模的网络。Newman提出一种基于贪心的快速社区发现算法，算法的基本思想是：首先将网络中的每个顶点设为一个单独社区，然后选出使得模块度Q的增值最大的社区对进行合并；如果网络中的顶点属于同一个社区，则停止合并过程。整个过程是自底向上的过程，且这个过程最终得到一个树图，即树的叶子节点表示网络中的顶点，树的每一层切分对应着网络的某个具体划分，从树图的所有层次划分中选择模块度值最大的划分作为网络的有效划分。
Step1：初试化网络，将每个节点看做一个社区；
Step2：选择使得Q增值最大的合并方式合并有连边的社区对；
Step3：合并以后更新邻接矩阵；
Step4：重复2和3，直到整个网络合并成一个社区。
原文：Fast algorithm for detecting community structure in networks

标签传播算法
https://juejin.im/post/6844904117115027464

References:
社团结构定义
社区发现算法总结（一）