一种复杂网络中社区发现的方法是寻找位于社区之间的边，如果能找到并移除这些边，最终将只剩下孤立的社区。

谈及一条位于社区之间的边，由于与多方法可以对其量化，并基于此实现社区发现算法。2004年，Newman和Girvan的论文中提出了利用介数中心性（betweenness centrality）的方法，称之为Girvan-Newman算法，这篇论文也是开创了社区发现这一领域的文章。本文主要针对无权和有权网络，对此类算法进行一定的研究分析。

在图论中，介数中心性（betweenness centrality）是基于最短路径的图的中心的度量方法。对于连通图中的每对顶点，在顶点之间至少存在一条最短路径，而一个节点的介数一般是指通过该节点的最短路径数。

介数中心性的定义为：

$C_B(v)= \sum_{s\ne v\ne t \in V}{\frac{\sigma_{st(v)}}{\sigma_{st}}}$

Newman和Girvan针对社区发现问题的同时，提出了模块度函数 $Q$

模块度，是指复杂网络中连接社区内部节点的边所占的比例，与另一个随机网络中连接社区内部节点的边所占的比例的期望值的差值。其中，这个随机网络的构造方法为：保持每个节点的社区属性不变，根据节点度对节点间的边进行随机连接。如果社区结构比较明显，则社区内部连接的边的比例应改高于随机网络的期望值。

因此，可以用模块度函数 $Q$

$Q = \sum_{s}^{M}{\left[\frac{l_s}{L}-(\frac{d_s}{2L})^2 \right]}$

上式的物理意义是：网络中连接两个同种类型的节点的边（即社区内部边）比例，减去在同样的社区结构下任意连接这两个节点的边的比例的期望值。如果社区内部边的比例不大于任意连接时的期望值，则有 $Q=0$

这样的社区发现算法的主要思路为：计算网络中所有边的边介数，然后寻找边介数值最大的边并移除。在移除时，会改变一些边的边介数。以前经过被移除边的最短路径，现在改为经由其他边，因此必须重新计算边介数，然后再次搜索值最大的边并移除，依此类推。当一条接一条边被移除时，最初连通的网络最终会被分成两部分、三部分等等，直至网络的每一个成为一个社区，是一种 分裂算法 。

算法的执行过程可用树状图表示，如下图所示。算法从顶部开始生成树状图，首先是单个连通网络，然后将其不断划分，直至每个分支只有单个结点为止。在算法运行期间，每个独立的网络结构状态对应于树状图的水平切分，在图2中用红线表示。与红线相交的每个分支代表一组节点，即一个社区，沿分支向下到底部的全部节点都为其成员。因此对于一个连通网络，树状图能够得到算法执行全过程中每个阶段里网络划分的社区结构。

这样我们可以发现，这种算法并不是给出将网络划分成社区的唯一划分，而是给出多种不同程度的划分。范围比较粗的划分，将网络划分为几个大的社区，范围比较细的划分，将网络划分为许多比较小的社区。这种不同程度的划分，可以揭示关于层次网络结构的信息。同时，用户可根据目标社区数来决定进行哪些划分，或者利用模块度函数 $Q$

如前所述，直观来看，在社区内部节点之间相互连接的边密度较大，因此，通过边介数（连接社区的边的边介数大）来识别社区是一种较为直观的社区发现算法。Girvan-Newman算法即是一种基于介数的社区发现算法，其基本思想是根据边介数中心性（edge betweenness）从大到小的顺序不断的将边从网络中移除直到整个网络分解为各个社区。因此，Girvan-Newman算法实际上是一种分裂方法。