在前两个博客中，我们都知道GN算法的时间复杂性并不理想，如果网络包含成千上万个顶点，该算法需要很多时间。 因此，Newman[2004][1]描述了一种快速算法。 测试表明，该算法能够较好地分析生成的网络和真实世界网络，比原算法快了近千倍
高速算法的时间复杂度为o(mn ) n )，当时稀疏网络为o(mn )，其中m为顶点数，n为边数。 该算法是凝聚法的一种，基于模块度q。 q值越大，被分割社区的结构越好，所以排列一个网络的所有分割情况后再计算q值，找出q值最大的分割情况不是最好吗？ 但是罗列出所有的划分情况非常花时间！ 也就是说，如果存在n个顶点并且划分为g个社区(0=g=n )，则基于第二种斯特林数共享sn )-g
1克！ k=0g(1) k ) gk ) n ) n frac { 1 } { g！ }sum _ { k=0} ^ { g } {-1 } ^ { k }left (begin { array } { c } gkend { array } ) right ) g-k 1k=00aray
另一方面，sn(1) sn(1)=2
n − 1 S _ { n } ^ { ( 1 ) } + S _ { n } ^ { ( 2 ) } = 2 ^ { n - 1 } Sn(1)+Sn(2)=2n−1，可知总情况数目是指数型增长的，所以当网络中有20以上的顶点时，计算总情况数是不可行的。故我们可以转而求局部最优解，而快速算法是基于贪婪算法的寻求局部最大Q值。在正式介绍快速算法之前，我们先明确一个概念，即 e i j e _ { i j } eij,当表示社团i和社团j之间的边数占总边数的比例。Newman做了特别的声明:一条边的计数不能同时出现在e矩阵的对角线的上方和下方，例如当总边数为17，而i,j之间有5条边，则 e i j e _ { i j } eij= e j i e _ { ji } eji= 1 2 × 5 17 frac { 1 } { 2 } times frac { 5 } { 17 } 21×175，即将i，j之间边数分为两份，一份计入 e i j e _ { i j } eij，一份计入 e j i e _ { ji } eji。故 e i j e _ { i j } eij+ e j i e _ { ji } eji为社团i和社团j之间的边数占总边数的比例（我们先记下这点，下文会用到。）
快速算法的步骤如下：
1，将网络每个顶点均看做一个社团，初始的顶点i和j之间有边相连，则 e i j e _ { i j } eij= 1 2 m frac { 1 } { 2 m } 2m1，否则为0。
a i = k i 2 m a _ { i } = frac { k _ { i } } { 2 m } ai=2mki, k i k_{i} ki是顶点i的度。
2，依次合并有边相连的社团对，并计算合并后的Q值的增量 Δ Q Delta Q ΔQ :
Δ Q = e i j + e j i − 2 a i a j Delta Q = e _ { i j } + e _ { j i } - 2 a _ { i } a _ { j } ΔQ=eij+eji−2aiaj
下面解释一下 Δ Q Delta Q ΔQ的由来：根据上篇博客给出的Q值定义，则可知 Δ Q Delta Q ΔQ定义为（新增的内部边数）-（该类边的期望边数）
两个社团i,j合并后，之前社团i、j内部的仍是新社团内部的边，而之前社团i,j之间连接的边也成了新社团内部的边。所以整个网络的内部边的增量为 e i j + e j i e _ { i j } + e _ { j i } eij+eji,而i,j间边数期望值是 k i k j 2 m frac { k i k j } { 2 m } 2mkikj= 2 a i a j 2 a _ { i } a _ { j } 2aiaj 。
虽然快速算法在时间复杂度方面由于GN算法，但是据实验表明，它的准确度是差于GN算法的。
参考文献：
[1]:Newman M E . Fast algorithm for detecting community structure in networks[J]. Phys Rev E Stat Nonlin Soft Matter Phys, 2004, 69(6 Pt 2):066133.