利用GN算法进行社区发现

上一篇推送提出了如何从社会关系网中发现不同的团体：如何从社会关系网中发现不同的团体？。今天来介绍通过GN算法来发现这些团体。

01算法原理

这个算法是这样做的。根据边的重要性将边一条一条的删去，那么随着边的删除，那些节点也会慢慢变成独立的子连通图。如下图：

所以，怎么来确定边的重要性了？一种估量方式就是Edge betweenness，它被定义为节点对之间的最短路径经过该条边的节点对数。举个栗子，假设图1是原始网络，节点旁边是节点编号；图2中边旁边是每条边的Edge betweenness，如边(3,4)的Edge betweenness是12，即共有{{1,4},{1,5},{1,6},{1,7},{2,4},{2,5},{2,6},{2,7},{3,4},{3,5},{3,6},{3,7}}这12对节点对的最短路径经过边(3,4)。

那么就可以算每条边的Edge betweenness了，然后排序取最大值对应的那条边删除，即图2。接着继续计算Edge betweenness，再删... (图3，4)。完整的算法逻辑如下：

1. 计算所有边的betweenness；

2. 移去betweenness最高的那条边；

3. 重新计算剩余边的betweenness；

4. 重复步骤2和3，直到没有边可被移去。

02评价方法

按上面的方法确实可以划分不同的社区(团体)，但是会出现很多中划分方式，那么哪一种才是最好的呢？如上图，画出了图3和图4两种划分的团体。因此需要一个评估方法来评价哪种划分方式更合理。

作者是这样做的：

修正：eii是每个社区边数量（双向图），从所有的划分方式中选择Q值最大的方式作为最终的社区划分结果。

03结果

实验结果：

算法具体实现代码可后台回复“社区发现”。

▼更多精彩推荐，敬请关注我们▼