NetworkX谱聚类后如何找到跨子图连接权重最高的节点？

一、统计节点跨子图连接权重 #

首先从原图提取每个节点与其他子图节点的边权重信息，以此筛选子图中与外部连接最紧密的节点。可选择累计跨子图边总权重或最大单条跨子图边权重作为判定依据，按需选择：

# 建立节点到所属聚类的映射
node_to_cluster = {node: cidx for node, cidx in zip(nodes_list, clusters)}
# 统计每个节点的跨子图边总权重
cross_total_weights = {node: 0.0 for node in nodes_list}
# 统计每个节点的最大单条跨子图边权重（可选）
cross_max_weights = {node: 0.0 for node in nodes_list}

# 遍历原图所有边（稀疏邻接矩阵可改用对应遍历方式）
for i, u in enumerate(nodes_list):
    u_cluster = clusters[i]
    for j, v in enumerate(nodes_list):
        if i == j:
            continue
        v_cluster = clusters[j]
        edge_weight = adj_matrix[i][j]
        if u_cluster != v_cluster and edge_weight > 0:
            cross_total_weights[u] += edge_weight
            if edge_weight > cross_max_weights[u]:
                cross_max_weights[u] = edge_weight

二、为每个子图筛选源点与目标点 #

对每个子图，按跨子图权重降序排序节点，选出权重最高的两个节点作为源点（source）和目标点（sink）；子图节点数不足2时特殊处理：

def pick_source_sink(subgraph_nodes, weight_dict):
    sorted_nodes = sorted(subgraph_nodes, key=lambda x: weight_dict[x], reverse=True)
    source = sorted_nodes[0]
    # 子图仅1个节点时，源汇复用；否则选权重次高节点作为sink
    sink = sorted_nodes[1] if len(sorted_nodes) >= 2 else source
    return source, sink

# 逐个处理子图
H_source, H_sink = pick_source_sink(list(H.nodes()), cross_total_weights)
I_source, I_sink = pick_source_sink(list(I.nodes()), cross_total_weights)
J_source, J_sink = pick_source_sink(list(J.nodes()), cross_total_weights)
K_source, K_sink = pick_source_sink(list(K.nodes()), cross_total_weights)
L_source, L_sink = pick_source_sink(list(L.nodes()), cross_total_weights)

三、在子图上运行最小费用最大流算法 #

为子图边添加容量和费用属性（按需定义），再调用最小费用最大流算法（以NetworkX为例）：

import networkx as nx

def run_min_cost_max_flow(subgraph, source, sink):
    # 为边设置容量和费用：这里假设容量为1，费用取原图边权重（可按需调整）
    for u, v, attr in subgraph.edges(data=True):
        subgraph[u][v]['capacity'] = 1  # 可根据业务场景设置更大值
        subgraph[u][v]['cost'] = attr.get('weight', 0.0)  # 若权重为相似度，可改为1/attr['weight']
    
    # 计算最小费用最大流
    max_flow, min_cost = nx.max_flow_min_cost(subgraph, source, sink)
    return max_flow, min_cost

# 执行每个子图的计算
H_flow, H_cost = run_min_cost_max_flow(H, H_source, H_sink)
I_flow, I_cost = run_min_cost_max_flow(I, I_source, I_sink)
J_flow, J_cost = run_min_cost_max_flow(J, J_source, J_sink)
K_flow, K_cost = run_min_cost_max_flow(K, K_source, K_sink)
L_flow, L_cost = run_min_cost_max_flow(L, L_source, L_sink)

关键注意点 #

• 跨子图权重逻辑：若需针对特定子图的连接（如仅统计与子图X的边），可修改遍历逻辑，只计算目标子图节点的边权重。
• 容量与费用定义：若边权重代表传输收益，可将费用设为负权重，此时最小费用等价于最大收益；容量需结合实际场景设置（如边的最大承载量）。
• 边界处理：子图节点数为1时，流值必然为0，可提前判断避免无效计算。

内容的提问来源于stack exchange，提问作者mleafer