使用NetworkX配置模型生成的图与原图边数不一致的问题咨询

问题详情 #

我有一个图G，其属性如下：

{'node_num': 63717,
 'edges_num': 373718}

我尝试通过NetworkX按照如下方式生成配置模型图：

cm = nx.configuration_model([y[1] for y in G.degree()], nx.Graph(), seed=42)

向模型输入了原图G所有节点的度序列，但最终得到的cm图属性为：

{'node_num': 63717,
 'edges_num': 373602
}

既然使用了完全相同的度序列，两者的边数难道不应该一致吗？如果是这样的话，问题是否与我使用的原图G有关？

原因与解决方案 #

这是NetworkX生成无向简单图时的正常行为，和原图G无关，核心出在配置模型的自环、重边处理逻辑上：

• 配置模型的原理是给每个节点分配对应度数的「半条边（stub）」，再随机配对这些stub。但随机过程中必然会出现两种无效配对：
  • 自环：同一节点的两个stub配对
  • 重边：两个节点之间的stub配对多次
• 当你指定生成nx.Graph()（无向简单图）时，NetworkX会自动移除所有自环和重边，这就导致最终边数少于原图——因为原图是无自环无重边的简单图，但配置模型生成的中间图会产生这些无效边，移除后自然边数减少。

如果要保证边数与原图一致，可按以下方式处理：

• 生成允许自环和重边的图：去掉nx.Graph()参数，默认生成nx.MultiGraph()，此时边数会严格等于原度序列总度数的一半（和原图边数一致）
• 若需要简单图，可使用nx.random_degree_sequence_graph，它会优先生成无自环重边的图，尽可能匹配度序列，边数偏差会比configuration_model更小，但仍可能因度序列的可图性限制出现少量差异。

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