单目标优化——模块度最优化算法

1.基于K派系过滤的社团检测（基于物理模型）

相关基础概念：

K-派系（clique）：网络中包含K个节点的全耦合子图，即K个节点中的任意两个节点之间都是相互连接的。

相邻：若两个K-派系中有K-1个公共节点，称这两个K-派系相邻。

连通：若一个K-派系可以通过若干个相邻的K-派系到达另一个K-派系，称其彼此连通。

K-派系社团：所有彼此连通的K-派系构成的集合，称为一个K-派系社团。

对上述网络进行K-派系过滤划分：

(1)在给定网络中找出所有规模为k=3的团，具体包括{1,2,3},{1,3,4},{4,5,6},{5,6,7},{5,6,8},{5,7,8},{6,7,8}。

(2)构建团图。若两个k团共享k-1即2个节点，那么将其连接起来。

连接1：{1,2,3},{1,3,4} 共享节点{1,3}。

连接2：{4,5,6},{5,6,7},{5,6,8},{5,7,8},{6,7,8}。

(3)每个连接的部分形成一个社区，得到两个社区C1={1,2,3,4}，C2={4,5,6,7,8}，其中节点4同时属于两个社区，因此为重叠节点。

---

2（聚合思想的算法）

2.1)基于fastgreedy算法的社团检测（模块度增量）

该算法的三个名称：CNM=fastgreedy=fastmodularity

算法原理：该算法以贪婪地最大化图的模块度的方式将单个节点合并到社区中。 可以证明，如果没有合并可以增加当前的模块度，则算法可以停止，因为无法进一步增加.

(1) 初始时将每个节点看作一个社团，每个社团中只有一个节点。

(2) 计算任意两社团合并对应Q值的增量，选择使Q值增加幅度最大的社团进行合并。

(3) 重复步骤(2)直到任意两社团合并都不能使Q值继续增加，Q值达到峰值。

该算法的性能优势：据说该算法在稀疏图上几乎以线性时间运行。

该算法存在的问题：Q最大值不一定是全局最优，可能是局部最优。

2.2)快速模块度优化算法——BGLL算法*

2.3)MSG-VM算法*

---

（直接寻优算法）

极值优化EO算法*

主要思想类似于生物系统演化中的断续平衡问题，之后用离散和连续的NPC问题，解决如图分割、伊辛模型、原子最优团簇结构等问题。

---

3.基于GN算法的社团检测（切割最大边介数）（分裂思想的算法）

算法基本思想：如果两个社区只是由少数几条边连接，那么两个社区之间的路径都要经过这几条边中的一条，因此边介数（edge betweenness）会很大。 利用边介数的概念，通过不断地切断边介数最大的边，获得层次性的社团结构。

算法的基本流程：

(1) 计算网络中每条边的边介数；

(2) 找出边介数最大的边，并将其移除；

(3) 重新计算网络中剩余各条边的边介数；

(4) 重复(2)和(3)步，直到网络中所有边都被移除，获得系统树图；

(5) 按照模块度函数Q值最大的原则，对系统树图进行切割，获得社区划分。

---

4.基于标签传播label propagation的社团检测（标签传染：邻居节点最多标签）

算法基本原理：

1.为网络中每个节点分配一个不重复的标签label。

2.在每次迭代过程中，节点根据其所有邻居节点中出现次数最多的label更新自身label。如果最佳候选label超过一个，则在其中随机选择。

3.具有相同label的节点被归入同一个社区。

算法性能优势：在大多数情况下可以快速收敛。

算法性能缺陷：迭代的结果有可能不稳定，尤其在不考虑连边的权重时，如果社区结构不明显或者网络规模比较小时，有可能所有的节点都被归入同一社区。

---

5.基于拉普拉斯矩阵的特征向量Leading eigenvector的社团检测*

算法基本原理：

拉普拉斯矩阵L = 度矩阵（degree matrix）D - 邻接矩阵（adjacency matrix）A

L中最小的特征根总等于0，而L的特征根中0的个数即为无向网络G中社区的个数，因此如果除了最小特征根没有别的特征根为0，则整个网络构成一个整体。

第二小的特征根（或者最小的非零特征根）又叫做代数连通性（algebraic connectivity），其对应的特征向量叫做Fidler vector。

根据Fidler vector特征向量值中元素取值进行社区划分。

---

6.基于层次聚类multilevel的社团检测（模块度标准）

算法基本原理：

层次聚类为一种自底向上的算法，初始化时定义每个节点归属于一个分离的社区，根据总体社区划分模块度最大化的原则，以迭代的方式最大化每个节点社区移动所带来的局部贡献。

算法基本过程：

(1) 将每个节点当作一个社区。

(2) 基于模块度标准决定哪些邻居应该被合并。经过一次迭代之后，一些社区合并为一个社区。

(3) 每个社区被当作一个节点，对其度和连接信息进行统计，基于统计结果再进行下一次迭代合并。

(4) 重复步骤(3)直到网络社区划分对应的总体模块度不能再增加为止。

---

7.基于community_optimal_modularity算法的社团检测

---

8.基于随机游走walktrap的社团检测**

P. Pons 和 M. Latapy 2005年提出了基于随机游走的网络社区划分算法，使用两点到第三点的流距离之差来衡量两点之间的相似性，从而为划分社区服务。

算法具体操作步骤：

1.对网络G的邻接矩阵A按行归一化D.^(-1)*A得到概率转移矩阵（transition matrix）P，D是度矩阵。利用P矩阵的马可夫性质可知，它的t次方的元素Pijt就代表着随机游走的粒子经过t步从节点i到j的概率。

2.定义两点ij间的距离如下：其中t是流的步长,k是某一目标节点。步长t必须恰当选择，因为如果t太小，不足以体现网络的结构特征；如果t太大，则Pijt趋近于与j的度数d(j)成正比，出发点i的拓扑信息被抹去。t经验值为2到5之间。

---

9.基于community_spinglass算法的社团检测

---

10.基于infomap的社团检测（推测随机游走粒子，求‘平均流’）

算法核心思想： 好的社区划分要令网络上流的平均描述长度最短。分析有向加权网络的一个好的视角是观察某类实体（货币、能量、信息）在网络上的流动，即使没有实体流动的数据，也可以根据网络的基本结构来推测随机游走粒子的轨迹，然后对得到的“平均流”进行信息编码。对“平均流”描述长度最短的编码机制，就对应着对社区的一种最有效划分。