Mark Newman基于贪心思想提出了模组度最大化的贪心算法,基于贪心原则,选取使模组度增长最大或者减小最少的两个社区,将它们合併成一个新的社区。如此循环叠代,直到所有节点合併成一个社区。随着叠代的进行,网路总的模组度是不断变化的,在模组度的整个变化过程中,其最大值对应的网路的社区划分即为近似的最优社区划分
基本介绍
- 中文名:Fast Girvan Newman社团发现算法
- 外文名:Fast GN community detection method
模组度最大化问题是一个典型的最最佳化问题,Mark Newman基于贪心思想提出了模组度最大化的贪心算法FN。贪心思想的目标是为了找出目标函式的整体最优值或者近似最优值,它将整体最最佳化问题分解为局部最最佳化问题,找出每个小的局部最优值,最终将局部最优值整合成整体的近似最优值。FN算法将模组度最最佳化问题分解为模组度局部最最佳化问题,初始时,算法将网路中的每个节点都单独的看作独立的小社区。然后,考虑所有相连社区两两合併的情况,计算每种合併带来的模组度的增量。基于贪心原则,选取使模组度增长最大或者减小最少的两个社区,将它们合併成一个新的社区。如此循环叠代,直到所有节点合併成一个社区。随着叠代的进行,网路总的模组度是不断变化的,在模组度的整个变化过程中,其最大值对应的网路的社区划分即为近似的最优社区划分。
贪心算法FN具体步骤如下所述:
(1)去掉网路中所有的边,网路的每个节点都单独作为一个社区;
(2)网路中的每个连通部分作为一个社区,将还未加入网路的边分别重新加回网路,如果加入网路的边连线了两个不同的社区,即合併了两个社区,则计算形成的新的社区划分的模组度的增量。选择使模组度增长最大或者减小最少的两个社区进行合併;
(3)如果网路的社区数大于1,则返回步骤 (2) 继续叠代,否则转到步骤 (4);
(4)遍历每种社区划分对应的模组度的值,选取模组度最大的社区划分作为网路的最优划分。