跳转到内容

Girvan–Newman算法

来自维基学院

Girvan–Newman算法(以Michelle Girvan和k Newman的名字命名 )是复杂系统中一种启发式的社区发现算法,本文旨在说明该算法的一部分特性。

边介数和社会结构[编辑 | 编辑源代码]

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

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

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

Girvan-Newman算法的步骤如下:

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

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