[科普中国]-Fast Girvan Newman社团发现算法

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

贪心算法FN具体步骤如下所述：

（1）去掉网络中所有的边，网络的每个节点都单独作为一个社区；

（2）网络中的每个连通部分作为一个社区，将还未加入网络的边分别重新加回网络，如果加入网络的边连接了两个不同的社区，即合并了两个社区，则计算形成的新的社区划分的模块度的增量。选择使模块度增长最大或者减小最少的两个社区进行合并；

（3）如果网络的社区数大于1，则返回步骤 （2） 继续迭代，否则转到步骤 （4）；

（4）遍历每种社区划分对应的模块度的值，选取模块度最大的社区划分作为网络的最优划分。