networkx Girvan-Newman社团检测

Girvan-Newman算法是一种基于图的社团检测算法，可以用来识别网络中的社团结构。它基于图的边介数（edge betweenness）的概念，该概念指的是在所有最短路径中经过某条边的次数。该算法的基本思想是：不断地割掉介数最大的边，直到图被分为若干个连通分量或者达到预设的社团数量为止。

在Python中，可以使用networkx库来实现Girvan-Newman算法。具体步骤如下：

1. 构建图：使用networkx库中的Graph()函数构建一个无向图。

import networkx as nx

G = nx.Graph()

2. 添加边：使用add_edges_from()函数添加图的边。

G.add_edges_from([(1,2), (1,3), (2,3), (2,4), (3,4), (4,5)])

3. 计算边介数：使用betweenness_centrality()函数计算每条边的介数。

eb = nx.edge_betweenness_centrality(G)

4. 删除介数最大的边：使用edge_betweenness()函数找到介数最大的边，并使用remove_edges_from()函数删除这些边。

max_eb = max(eb.values())
for k, v in eb.items():
    if v == max_eb:
        G.remove_edge(k[0], k[1])

5. 重复步骤3和步骤4，直到达到预设的社团数量或者图被分为若干个连通分量为止。

def girvan_newman(G, k):
    c = list(nx.connected_components(G))
    while len(c) < k:
        eb = nx.edge_betweenness_centrality(G)
        max_eb = max(eb.values())
        for k, v in eb.items():
            if v == max_eb:
                G.remove_edge(k[0], k[1])
        c = list(nx.connected_components(G))
    return c

girvan_newman(G, 2)

上述代码将图分为两个社团，并返回每个社团的节点集合。