模块度

模块度也称模块化度量值，是目前常用的一种衡量网络强度的方法，最早由提出。模块度的定义为：

Q = \frac{1}{2m}\sum_{ij}\left[A_{ij}-\frac{k_ik_j}{2m}\right]\delta(C_i,C_j)

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

模块度最优化算法
由于网络所有可能的划分数量是巨大的，假设网络的结点数和边数分别为n和m，则所有可能的社区划分数是一个以n为指数的数。因此，在所有可能的划分中找出最优划分是一个NP-hard问题。针对这一问题，目前一些相应算法已被提出，其可以在合理的时间内找出模块度最大化的近似最优划分。
经典贪心算法
模块度最大化问题是一个经典的最优化问题，马克·纽曼基于贪心思想提出了模块度最大化的贪心算法FN。该算法包括两个阶段，第一阶段合并社区，算法将每个结点当作一个社区，基于模块度增量最大化标准决定哪些邻居社区应该被合并。经过一轮扫描后开始第二阶段，算法将第一阶段发现的所有社区重新看成结点，构建新的网络，在新网络上重复进行第一阶段，这两个阶段重复运行，直到网络社区划分的模块度不再增长，得到网络的社区近似最优划分。

这个简单算法具有一下几个优点：首先，算法的步骤比较直观并且易于实现；其次，算法不需要提前设定网络的社区数，并且该算法可以呈现网络的完整的，能够发现在线社交网络的分层的虚拟社区结构，获得不同分辨率的虚拟社区；再次，计算机模拟实验显示，在上，算法的时间复杂度是线性的，在合理的时间内可以处理结点数超过10^9的网络，因此十分适合在线社交网络这样超大规模的负责网络中虚拟社区的发现。

参考资料