[科普中国]-CNM社团发现算法

在NewmanFastGN算法的基础上,Clauset1等人采用堆的数据结构来计算和更新网络的模块性,提出了一种新的贪心算法,这里称为，该算法的复杂度只有，已接近线性复杂度。

Newman贪心算法通过初始的连接矩阵计算模块度的增量ΔQ，而CNM算法直接构造一个模块度的增量矩阵ΔQ,然后通过对它的元素进行更新来得到模块性最大的一种社团结构。显然,如果合并两个不相连的社团,模块度Q的值是不会变的。因此只需要存储那些有边相连的社团i和j相应的元素,从而节省了存储空间。辅助数据结构包括：模块性增量矩阵、最大堆、辅助向量。

算法流程：

1）初始化，初始化网络为n个社团，即每个节点就是一个独立的社团，并计算模块性增量矩阵。

2）从最大堆中选择最大的,合并相应的社团i和j,标记合并后的社团的标号为j;更新模块性增量矩阵ΔQ、最大堆H和辅助向量a。

3)重复步骤2),直到网络中所有的节点都归到一个社团内。