直观来看，在社群内部节点之间相互连接的边密度较大，因此，通过边来识别社群是一种较为直观的社群发现算法。Girvan-Newman算法即在该启示下发展而言，如果去除社群之间连接的边，留下的就是社群。对于社群而言，较先去除的边，中心性较低，而中介中心性则较大。因此，逐步去除中介中心性最大的边，直至结束(Girvan andNewman 2002)。

Girvan-Newman算法的详细步骤：

（1）计算网络中所有边的中介中心性；

（2）去除中介中心性最高的边；

（3）重新计算去除边后的网络中所有边的中介中心性；

（4）跳至步骤2，重新计算，直至网络中没有边存在。

Girvan-Newman算法所得到的结果实质上是网络中节点的树图（dendrogram）如下所示：

该算法给出了如何去除边得到社群结构。但在得到最终的社群数之前，还有一个问题没有得到解决，即如何确定合适的社群数，使社群划分结果最优。在他们随后的文章(Newman and Girvan 2004)中提出了Modularity Q的概念，并形成一个更为完整的方法。

Q值能够体现网络划分为社群后社群结构的质量，该值逼近于1，说明社群结构越明显，该值逼近于0则社群结构不明显。对于同一个网络而言，不同算法可能得到的Q值不同，Q值高则代表了该算法较优。利用Q值寻找合适的社群数的思路如下：

在上面Girvan-Newman算法中每去除一次边，则计算一下所得社群结构的Q值，寻找到Q值最大时的社群数量。一般而言，计算时不可能会在所有去边过程中都计算Q值，往往是寻找某一区间的Q值，取得局部最大值即可。Q一般有1-2次局部最大值。在下面的示例图中，当边去除后，社群数量为4时，所得Q值最大，因此该网络划分为4个社群最优。

References:

Girvan, M., and Newman, M. E. (2002). "Communitystructure in social and biological networks." Proceedings of theNational Academy of Sciences, 99(12), 7821-7826.

Newman, M. E. J., and Girvan, M. (2004). "Findingand evaluating community structure in networks." Phys Rev E, 69(2),26113.