社区发现图法
社区发现算法思路GN算法
社区发现算法思路
社区划分问题大多基于这样一个假设：同一社区内部的节点连接较为紧密，社区之间的节点连接较为稀疏。因此，社区发现本质上就是网络中结构紧密的节点的聚类。
从这个角度来说，这跟聚类算法一样，社区划分问题主要有两种思路：
(1)凝聚方法(agglomerative method)：添加边
(2)分裂方法(divisive method)：移除边
另一方面，我们也可以认为同一个社区内的节点，之所以能够聚集在一起，是因为它们有相似性。因此只要我们能够将一个节点很好地表示，成为一个向量，那么同样可以用相似性大法来寻找社区聚集，不过这点上需要向量对节点的描述足够好和足够完备。
GN算法据说是社区发现领域的第一个算法，或者说它开启了这个领域的研究。下面我们来分别介绍这个领域及其算法是如何演化的。
GN算法
计算每一条边的边介数删除边界数最大的边；重新计算网络中剩下的边的边阶数；重复(3)和(4)步骤，直到网络中的任一顶点作为一个社区为止。 GN算法的R分析代码
> library("igraph")
> karate
<- graph
.famous("Zachary")
> ebc
<- edge
.betweenness
.community(karate
)
> ebc
Graph community structure calculated
with the edge betweenness algorithm
Number
of communities (best split
): 5
Modularity (best split
): 0.4012985
Membership vector
:
[1] 1 1 2 1 3 3 3 1 4 5 3 1 1 1 4 4 3 1 4 1 4 1 4 4 2 2 4 2 2 4 4 2 4 4
> modularity(ebc
)
[1] 0.4012985
> membership(ebc
)
[1] 1 1 2 1 3 3 3 1 4 5 3 1 1 1 4 4 3 1 4 1 4 1 4 4 2 2 4 2 2 4 4 2 4 4
> plot(ebc
,karate
)
