格文-纽曼算法

格文-纽曼算法（得名于米歇尔·格文和马克·纽曼）是复杂系统启发式社区发现算法。

边介数和社会结构

格文-纽曼算法通过不断地删除网络中的边来检测网络中的社区。在最终剩余的网络中的连通分量也就是社区。格文-纽曼算法并不是去测量哪些边具有最高的中心度，而是去关注哪些最有可能连接着社区。

顶点介数是一种反应网络中顶点的中心度的指标。对于一个顶点i，顶点介数是指网络中经过该顶点的所有最短路径的数量。

格文-纽曼算法将介数扩展到了边。类似地，一条边的边介数是指网络中经过该边的最短路径的数量。如果一个网络所包含的社区之间是由少量的边连接的，那么经由不同社区的最短路径都需要从这些边上经过，因此这些边的边介数会非常高。通过移除这些边，各个社区之间将会被分割开来，从而可以发现这些社区。

格文-纽曼算法的步骤如下：

重新计算剩余每条边的边介数需要不少计算时间，然而，并没有较好的办法省去这些开销。当一条边被删除了之后，网络的结构发生了变化，举个例子来说，假设两个社区之间有不止一条边连接，那么并不是每条边都会有较高的边介数，我们只能逐渐地删除这些边，在这个过程中会发现至少有一条边会有较高的边介数。

格文-纽曼算法的结果是一个树状图。这个树状图自顶向下地描绘了社区的结构。树状图的叶子则是图的每个结点。