格文-纽曼算法

格文-纽曼算法(得名於米歇尔·格文英语Michelle Girvan马克·纽曼英语Mark Newman)是复杂系统启发式社区发现算法。[1]

边介数和社会结构 编辑

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

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

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

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

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

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

參考文獻 编辑

  1. ^ Girvan M. and Newman M. E. J., Community structure in social and biological networks, Proc. Natl. Acad. Sci. USA 99, 7821–7826 (2002)