如何对NetworkX生成的MultiDiGraph网络进行聚类？

一、把MultiDigraph转成聚类可用的数值矩阵 #

聚类算法（比如你熟悉的k-means）需要每行对应一个节点、每列对应一个特征的数值矩阵。针对有向多重图，你可以从这两个方向提取特征：

1. 提取节点结构特征（最直接高效） #

从每个节点的图结构属性入手，生成低维特征向量，适合k-means这类算法：

• 入度/出度：统计节点的所有入边、出边数量（包括重复边）
• 去重邻居数：统计节点的独特前驱/后继节点数量
• 中心性指标：比如PageRank值、介数中心性，反映节点在图中的重要性

代码示例：

import networkx as nx
import numpy as np

# 替换成你的MultiDigraph
G = nx.MultiDiGraph()
G.add_nodes_from(range(300))
G.add_edges_from([(np.random.randint(0,300), np.random.randint(0,300)) for _ in range(1000)])

# 提取每个节点的特征
feature_list = []
for node in G.nodes():
    in_degree = G.in_degree(node)  # 统计入边总数（含重复）
    out_degree = G.out_degree(node)
    unique_in_neighbors = len(set(G.predecessors(node)))
    unique_out_neighbors = len(set(G.successors(node)))
    pagerank = nx.pagerank(G)[node]
    betweenness = nx.betweenness_centrality(G)[node]
    
    feature_list.append([in_degree, out_degree, unique_in_neighbors, unique_out_neighbors, pagerank, betweenness])

# 转成numpy矩阵，直接喂给k-means
feature_matrix = np.array(feature_list)

2. 构建节点间距离矩阵 #

如果想基于节点间的连通性聚类，可以生成距离矩阵，再通过降维转成特征向量：

• 最短路径距离：两个节点间的最短有向路径长度，无路径则设为无穷大
• 邻接矩阵：记录每对节点间的边数，但300节点的邻接矩阵是300×300的高维矩阵，建议用MDS降维后再聚类

代码示例（最短路径距离+MDS降维）：

n_nodes = len(G.nodes())
distance_matrix = np.zeros((n_nodes, n_nodes))

for i, u in enumerate(G.nodes()):
    for j, v in enumerate(G.nodes()):
        if u != v:
            try:
                distance_matrix[i][j] = nx.shortest_path_length(G, source=u, target=v)
            except nx.NetworkXNoPath:
                distance_matrix[i][j] = np.inf
        else:
            distance_matrix[i][j] = 0

# 用MDS把距离矩阵转成2维特征向量，适配k-means
from sklearn.manifold import MDS
mds = MDS(n_components=2, dissimilarity='precomputed')
feature_matrix = mds.fit_transform(distance_matrix)

二、你的思路是否需要调整？ #

你想聚类后跑TSP/禁忌搜索，这里有个关键前提：TSP要求集群内部节点能形成连通的回路。单纯用k-means基于结构特征聚类，可能出现集群内部不连通的情况，建议结合图专属的聚类方法：

1. 社区发现算法（更适合图结构） #

直接用针对图的社区发现工具，比如Louvain算法（支持无向图，可先把MultiDigraph转成无向图处理），能自动划分出内部连接更紧密的集群：

# 转成无向图（合并双向边）
G_undir = G.to_undirected()

# 用Louvain算法划分社区（需先安装python-louvain：pip install python-louvain）
from community import community_louvain
partition = community_louvain.best_partition(G_undir)

# 按社区分组
clusters = {}
for node, cluster_id in partition.items():
    clusters.setdefault(cluster_id, []).append(node)

2. 基于强连通分量的聚类 #

先提取图中的强连通分量（SCC），如果分量太大就细分，太小就合并相邻分量，保证每个集群内部是强连通的，完美适配TSP的连通性要求：

# 提取所有强连通分量
sccs = list(nx.strongly_connected_components(G))

# 合并小分量（比如把节点数<5的分量合并到相邻的大分量）
large_sccs = [scc for scc in sccs if len(scc) >=5]
small_nodes = [node for scc in sccs if len(scc)<5 for node in scc]

# 把小节点分配到距离最近的大分量
for node in small_nodes:
    closest_scc = None
    min_distance = np.inf
    for scc in large_sccs:
        # 找节点到scc中任意节点的最短路径
        for scc_node in scc:
            try:
                dist = nx.shortest_path_length(G, node, scc_node)
                if dist < min_distance:
                    min_distance = dist
                    closest_scc = scc
            except nx.NetworkXNoPath:
                continue
    closest_scc.add(node)

三、实用提醒 #

• 若你的边有权重，提取特征时要改用G.in_degree(node, weight="weight")这类带权重的统计方法
• 聚类后务必检查每个集群的连通性，若出现内部不连通的情况，要么调整聚类参数，要么拆分/合并集群
• 集群大小要适配TSP的计算量：300节点全跑TSP不现实，建议每个集群控制在20-50节点范围内

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