![](https://csdnimg.cn/release/download_crawler_static/86376244/bg8.jpg)
体的近似最优值。FN 算法将模块度最优化问题分解为模块度局部最优化问题,初始
时,算法将网络中的每个结点都看成独立的小社区。然后,考虑所有相连社区两两
合并的情况,计算每种合并带来的模块度的增量。基于贪心原则,选取使模块度增
长最大或者减小最少的两个社区,将它们合并成一个社区。如此循环迭代,直到所
有结点合并成一个社区。随着迭代的进行,网络总的模块度是不断变化的,在模块
度的整个变化过程中,其最大值对应网络的社区划分即为近似的最优社区划分。
贪心算法 FN 具体步骤:
1. 去掉网络中所有的边,网络的每个结点都单独作为一个社区;
2. 网络中的每个连通部分作为一个社区,将还未加入网络的边分别重新加
回网络,每次加入一条边,如果加入网络的边连接了两个不同的社区,
则合并两个社区,并计算形成新社区划分的模块度增量。选择使模块度
增量最大或者减小最少的两个社区进行合并。
3. 如果网络的社区数大于 1,则返回步骤(2)继续迭代,否则转到步骤
(4);
4. 遍历每种社区划分对应的模块度值,选取模块度最大的社区划分作为网
络的最优划分。
该算法中,需要注意的是,每次加入的边只是影响网络的社区划分,而每次
计算网络划分的模块度时,都是在网络完整的拓扑结构上进行,即网络所有的边
都存在的拓扑结构上。
为了降低算法的时间复杂度,Vincent Blondel 等人提出了另一种层次贪心算
法,简称为快速模块度优化算法。该算法包括两个阶段,第一阶段合并社区,算
法将每个结点当作一个社区,基于模块度增量最大化标准决定你哪些邻居社区应
该被合并。经过一轮扫描后开始第二阶段,算法将第一阶段发现的所有社区重新
看成结点,构建新的网络,在新网络上重复进行第一阶段,这两个阶段重复运行,
直到网络社区划分的模块度不再增长,得到网络的社区近似最优划分。
这个简单算法具有一下几个优点:首先,算法的步骤比较直观并且易于实现;
其次,算法不需要提前设定网络的社区数,并且该算法可以呈现网络的完整的分
层社区结构,能够发现在线社交网络的分层的虚拟社区结构,获得不同分辨率的
虚拟社区;再次,计算机模拟实验显示,在稀疏网络上,算法是时间复杂度是线