networkx割边检测代码？

可以使用NetworkX库中的`minimum_cut`函数来检测割边。示例代码如下：

import networkx as nx
G = nx.Graph()
# 添加边
G.add_edge(1, 2, weight=4.7 )
G.add_edge(2, 3, weight=8.2 )
G.add_edge(3, 4, weight=7.4 )
G.add_edge(4, 5, weight=9.3 )
G.add_edge(1, 5, weight=14.1)
cut_value, partition = nx.minimum_cut(G, 1, 5)
print(cut_value)  # 打印割边权值
print(partition)  # 打印割边两边的点集

该函数返回割边的最小权值和割边两边的点集。

相关问题

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)

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