[科普中国]-快速模块度优化(BGLL)算法

为了降低算法的时间复杂度，Vincent Blondel1等人提出了另一种层次性贪心算法（BGLL算法）。该算法包括两个阶段，这两个阶段重复迭代运行，直到网络社区划分的模块度不再增长。第一阶段合并社区，算法将每个节点当作一个社区，基于模块度增量最大化标准决定哪些邻居社区应该被合并。经过一轮扫描后开始第二阶段，算法将第一阶段发现的所有的社区重新看作节点，构建新的网络，在新的网络上迭代的进行第一阶段。当模块度不再增长时，得到网络的社区近似最优划分。

算法的基本步骤如下：

1）.初始化，将每个节点划分在不同的社区中。

2）.逐一选择各个节点，根据公式计算将它划分到它的邻居社区中得到的模块度增益。如果最大增益大于0，则将它划分到对应的邻居社区；否则，保持归属于原社区。

3）.重复步骤2，直到节点的社区不再发生变化。

4）.构建新图。新图中的点代表上一阶段产生的不同社区，边的权重为两个社区中所有节点对的边权重之和。重复步骤2，直到获得最大的模块度值。

这个简单的算法具有几个优点，首先，算法的步骤比较直观并且易于实现；第二，算法不需要提前设定网络的社区数，并且该算法可以呈现网络完整的分层社区结构，能够发现在线社交网络的分层的虚拟社区结构，获得不同分辨率的虚拟社区；最后，计算机模拟实验显示，在稀疏网络上，算法的时间复杂度是线性的，在合理的时间内可以处理节点数超过10^9的网络，因此十分适合在线社交网络这样超大规模的复杂网络中虚拟社区的发现。