Girvan–Newman算法
Girvan–Newman算法（以Michelle Girvan和k Newman的名字命名 ）是复杂系统中一种启发式的社区发现算法，本文旨在说明该算法的一部分特性。
边介数和社会结构
编辑Girvan-Newman算法通过不断地删除网络中的边来检测网络中的社区。在最终剩余的网络中的连通分量也就是社区。Girvan-Newman算法并不是去测量哪些边具有最高的中心度，而是去关注哪些最有可能连接着社区。
顶点介数是一种反应网络中顶点的中心度的指标。对于一个顶点i，顶点介数是指网络中经过该顶点的所有最短路径的数量。
Girvan-Newman算法将介数扩展到了边。类似地，一条边的边介数是指网络中经过该边的最短路径的数量。如果一个网络所包含的社区之间是由少量的边连接的，那么经由不同社区的最短路径都需要从这些边上经过，因此这些边的边介数会非常高。通过移除这些边，各个社区之间将会被分割开来，从而可以发现这些社区。
Girvan-Newman算法的步骤如下：
重新计算剩余每条边的边介数需要不少计算时间，然而，并没有较好的办法省去这些开销。当一条边被删除了之后，网络的结构发生了变化，举个例子来说，假设两个社区之间有不止一条边连接，那么并不是每条边都会有较高的边介数，我们只能逐渐地删除这些边，在这个过程中会发现至少有一条边会有较高的边介数。
Girvan-Newman算法的结果是一个树状图。这个树状图自顶向下地描绘了社区的结构。树状图的叶子则是图的每个结点。