模块化最大化问题是一个经典的优化问题。 基于贪心思想,Mark提出了模块化最大化的贪心算法FN。 贪心思维的目标是寻找目标函数的整体最优值或近似最优值。 它将整体优化问题分解为局部优化问题,找到各个局部最优值,最后将局部最优值整合为整体近似最优值。 FN算法将模块化优化问题分解为模块化局部优化问题。 最初,该算法将网络中的每个节点视为一个独立的小社区。 然后,考虑所有连接的社区成对合并的情况,并计算每次合并带来的模块化增量。 基于贪心原则,选择模块度增加最多或模块度减少最少的两个社区合并为一个社区。 这一循环不断迭代,直到所有节点合并为一个社区。 随着迭代的进行,网络的总模块化程度不断变化。 在整个模块度变化过程中,其最大值对应的网络社区划分即为近似最优社区划分。
贪心算法FN的具体步骤:
去除网络中的所有边,网络中的每个节点作为一个社区; 网络中的每个连接部分都充当一个社区,尚未添加到网络中的边将重新添加回网络,一次添加一条边。 如果加入网络的边连接两个不同的社区,则将这两个社区合并,并计算形成新的社区划分的模块度增量。 选择最大化或最小化模块化增加的两个社区进行合并。 若网络中社区数量大于1,则返回步骤(2)继续迭代,否则转步骤(4); 遍历每个社区划分对应的模块度值,选择模块度最大的社区划分作为网络的最优划分。
在该算法中,需要注意的是,每条添加的边仅影响网络的社区划分,并且每次计算网络划分的模块度时,都是在网络的完整拓扑上进行的,即网络的所有边网络存在于拓扑结构上。