基于GN算法的二十人网络社区分析

GN算法是一种分裂型的社区结构分裂算法。该算法根据网络中社区内部高内聚、社区之间低内聚的特点，逐步去除社区之间的边，取得相对内聚的社区结构。算法用边介数的概念来探测边的位置，某边的边介数定义为网络上所有顶点之间的最短路径通过该边的次数。由定义可知，如果一条边连接两个社区，那么这两个社团节点之间的最短路径通过该边的次数就会最多，相应的边介数最大。如果删除该边，那么两个社团就会分割开。GN算就就是基于此思想反复计算当前网络的最短路径，计算每条边的边介数，删除边介数最大的边。最后在一定条件下，算法停止，即可得到网络的社区结构。