模组度也称模组化度量值,是目前常用的一种衡量网路社区结构强度的方法。
基本介绍
- 中文名:模组度
- 外文名:Modularity
模组度介绍
模组度也称模组化度量值,是目前常用的一种衡量网路社区结构强度的方法,最早由Mark NewMan 提出了。模组度的定义为:

模组度值的大小主要取决于网路中结点的社区分配C,即网路的社区划分情况,可以用来定量的衡量网路社区划分质量,其值越接近1,表示网路划分出的社区结构的强度越强,也就是划分质量越好。因此可以通过最大化模组度Q来获得最优的网路社区划分。
最最佳化算法
由于网路所有可能的划分数量是巨大的,假设网路的结点数和边数分别为n和m,则所有可能的社区划分数是一个以n为指数的数。因此,在所有可能的划分中找出最优划分是一个NP-hard问题。针对这一问题,目前一些相应算法已被提出,其可以在合理的时间内找出模组度最大化的近似最优划分。
经典贪心算法
模组度最大化问题是一个经典的最最佳化问题,Mark NewMan 基于贪心思想提出了模组度最大化的贪心算法FN。贪心思想的目标是找出目标函式的整体最优值或者近似最优值,它将整体最最佳化问题分解为局部最最佳化问题,找出每个局部最优值,最终将局部最优值整合成整体的近似最优值。FN算法将模组度最最佳化问题分解为模组度局部最最佳化问题,初始时,算法将网路中的每个结点都看成独立的小社区。然后,考虑所有相连社区两两合併的情况,计算每种合併带来的模组度的增量。基于贪心原则,选取使模组度增长最大或者减小最少的两个社区,将它们合併成一个社区。如此循环叠代,直到所有结点合併成一个社区。随着叠代的进行,网路总的模组度是不断变化的,在模组度的整个变化过程中,其最大值对应网路的社区划分即为近似的最优社区划分。
贪心算法FN具体步骤:
贪心算法FN具体步骤:
- 去掉网路中所有的边,网路的每个结点都单独作为一个社区;
- 网路中的每个连通部分作为一个社区,将还未加入网路的边分别重新加回网路,每次加入一条边,如果加入网路的边连线了两个不同的社区,则合併两个社区,并计算形成新社区划分的模组度增量。选择使模组度增量最大或者减小最少的两个社区进行合併。
- 如果网路的社区数大于1,则返回步骤(2)继续叠代,否则转到步骤(4);
- 遍历每种社区划分对应的模组度值,选取模组度最大的社区划分作为网路的最优划分。
该算法中,需要注意的是,每次加入的边只是影响网路的社区划分,而每次计算网路划分的模组度时,都是在网路完整的拓扑结构上进行,即网路所有的边都存在的拓扑结构上。
快速模组度最佳化算法
为了降低算法的时间複杂度,Vincent Blondel等人提出了另一种层次贪心算法。该算法包括两个阶段,第一阶段合併社区,算法将每个结点当作一个社区,基于模组度增量最大化标準决定你哪些邻居社区应该被合併。经过一轮扫描后开始第二阶段,算法将第一阶段发现的所有社区重新看成结点,构建新的网路,在新网路上重複进行第一阶段,这两个阶段重複运行,直到网路社区划分的模组度不再增长,得到网路的社区近似最优划分。
这个简单算法具有一下几个优点:首先,算法的步骤比较直观并且易于实现;其次,算法不需要提前设定网路的社区数,并且该算法可以呈现网路的完整的分层社区结构,能够发现线上社交网路的分层的虚拟社区结构,获得不同解析度的虚拟社区;再次,计算机模拟实验显示,在稀疏网路上,算法是时间複杂度是线性的,在合理的时间内可以处理结点数超过10^9的网路,因此十分适合线上社交网路这样超大规模的负责网路中虚拟社区的发现。
这个简单算法具有一下几个优点:首先,算法的步骤比较直观并且易于实现;其次,算法不需要提前设定网路的社区数,并且该算法可以呈现网路的完整的分层社区结构,能够发现线上社交网路的分层的虚拟社区结构,获得不同解析度的虚拟社区;再次,计算机模拟实验显示,在稀疏网路上,算法是时间複杂度是线性的,在合理的时间内可以处理结点数超过10^9的网路,因此十分适合线上社交网路这样超大规模的负责网路中虚拟社区的发现。