模块度

模块度也称模块化度量值，是目前常用的一种衡量网络社区结构强度的方法，最早由马克·纽曼提出。模块度的定义为：

$Q={\frac {1}{2m}}*\sum _{ij}\left[A_{ij}-{\frac {k_{i}*k_{j}}{2m}}\right]\delta (C_{i},C_{j})$

模块度值的大小主要取决于网络中结点的社区分配C，即网络的社区划分情况，可以用来定量的衡量网络社区划分质量，其值越接近1，表示网络划分出的社区结构的强度越强，也就是划分质量越好。因此可以通过最大化模块度Q来获得最优的网络社区划分。

模块度最优化算法

由于网络所有可能的划分数量是巨大的，假设网络的结点数和边数分别为n和m，则所有可能的社区划分数是一个以n为指数的数。因此，在所有可能的划分中找出最优划分是一个NP-hard问题。针对这一问题，目前一些相应算法已被提出，其可以在合理的时间内找出模块度最大化的近似最优划分。

经典贪心算法

模块度最大化问题是一个经典的最优化问题，马克·纽曼基于贪心思想提出了模块度最大化的贪心算法FN 。贪心思想的目标是找出目标函数的整体最优值或者近似最优值，它将整体最优化问题分解为局部最优化问题，找出每个局部最优值，最终将局部最优值整合成整体的近似最优值。FN算法将模块度最优化问题分解为模块度局部最优化问题，初始时，算法将网络中的每个结点都看成独立的小社区。然后，考虑所有相连社区两两合并的情况，计算每种合并带来的模块度的增量。基于贪心原则，选取使模块度增长最大或者减小最少的两个社区，将它们合并成一个社区。如此循环迭代，直到所有结点合并成一个社区。随着迭代的进行，网络总的模块度是不断变化的，在模块度的整个变化过程中，其最大值对应网络的社区划分即为近似的最优社区划分。
贪心算法FN具体步骤：

1. 去掉网络中所有的边，网络的每个结点都单独作为一个社区；
2. 网络中的每个连通部分作为一个社区，将还未加入网络的边分别重新加回网络，每次加入一条边，如果加入网络的边连接了两个不同的社区，则合并两个社区，并计算形成新社区划分的模块度增量。选择使模块度增量最大或者减小最少的两个社区进行合并。
3. 如果网络的社区数大于1，则返回步骤（2）继续迭代，否则转到步骤（4）；
4. 遍历每种社区划分对应的模块度值，选取模块度最大的社区划分作为网络的最优划分。
   

该算法中，需要注意的是，每次加入的边只是影响网络的社区划分，而每次计算网络划分的模块度时，都是在网络完整的拓扑结构上进行，即网络所有的边都存在的拓扑结构上。

快速模块度优化算法

为了降低算法的时间复杂度，Vincent Blondel等人提出了另一种层次的贪心算法。该算法包括两个阶段，第一阶段合并社区，算法将每个结点当作一个社区，基于模块度增量最大化标准决定哪些邻居社区应该被合并。经过一轮扫描后开始第二阶段，算法将第一阶段发现的所有社区重新看成结点，构建新的网络，在新网络上重复进行第一阶段，这两个阶段重复运行，直到网络社区划分的模块度不再增长，得到网络的社区近似最优划分。
这个简单算法具有一下几个优点：首先，算法的步骤比较直观并且易于实现；其次，算法不需要提前设定网络的社区数，并且该算法可以呈现网络的完整的分层社区结构，能够发现在线社交网络的分层的虚拟社区结构，获得不同分辨率的虚拟社区；再次，计算机模拟实验显示，在稀疏网络上，算法的时间复杂度是线性的，在合理的时间内可以处理结点数超过$10^{9}$的网络，因此十分适合在线社交网络这样超大规模的负责网络中虚拟社区的发现。