创建度服从幂律分布的二分图及NetworkX相关技术问题

我需要创建一个顶点度服从幂律分布的二分图，并用以下代码验证是否为二分图：

print(bipartite.is_bipartite(G))

但遇到了两个问题：

• 使用bipartite.projected_graph()函数时，传入幂律度分布的随机图和顶点列表，无法得到二分图；如果传入二分图和幂律分布数据集则持续报错，不清楚该函数为何生成非二分图。
• 尝试生成幂律度分布的图时，bipartite.is_bipartite(G)的结果随机返回True或False。

我尝试的代码与运行结果 #

代码1：随机生成幂律度序列图 #

from networkx.algorithms import bipartite
from networkx.generators.degree_seq import random_degree_sequence_graph
from networkx.algorithms.graphical import is_graphical
from networkx.utils.random_sequence import powerlaw_sequence
n, t = 10, 2
while True:  # 不断生成序列直到找到可图序列
    seq = sorted([int(round(d)) for d in powerlaw_sequence(n, t)], reverse=True)  # 取整得到离散度序列
    if is_graphical(seq):
        break
G_1 = random_degree_sequence_graph(seq, tries=100)  # 可调整尝试次数
print(sorted(d for _, d in G_1.degree()))
print(bipartite.is_bipartite(G_1))
degrees = dict(G_1.degree())
degree_distribution = {}
for d in degrees.values():
    if d in degree_distribution:
        degree_distribution[d] += 1
    else:
        degree_distribution[d] = 1

print(degree_distribution)

代码2：绘制度分布直方图 #

degrees = dict(G_1.degree())
degree_distribution = {}
for d in degrees.values():
    if d in degree_distribution:
        degree_distribution[d] += 1
    else:
        degree_distribution[d] = 1

x = np.array(list(degree_distribution.keys()))
y = np.array(list(degree_distribution.values()))

plt.loglog(x, y, 'ro')
plt.title('度分布')
plt.xlabel('顶点度数')
plt.ylabel('顶点数量')
plt.show()

代码3：构建二分图并添加节点 #

import networkx as nx
import random

n = 100  # 总节点数
m = 4  # 新节点的连接数
p = 0.5  # 连接到第一分图的概率

G = nx.Graph()

G.add_nodes_from(range(n), bipartite=0)  # 第一分图
G.add_nodes_from(range(n, 2*n), bipartite=1)  # 第二分图

for i in range(n):
    for j in range(n, 2*n):
        if random.random() < p:
            G.add_edge(i, j)

for i in range(2*n, n+m):
    # 连接到第一分图的节点（优先选择度数高的节点）
    targets = []
    for j in range(n):
        targets += [j] * G.degree(j)
    target = random.choice(targets)
    G.add_edge(i, target)

    # 连接到第二分图的节点（优先选择度数高的节点）
    targets = []
    for j in range(n, 2*n):
        targets += [j] * G.degree(j)
    target = random.choice(targets)
    G.add_edge(i, target)

print(nx.bipartite.is_bipartite(G))

degrees = dict(G.degree())
degree_distribution = {}
for d in degrees.values():
    if d in degree_distribution:
        degree_distribution[d] += 1
    else:
        degree_distribution[d] = 1
for d, count in degree_distribution.items():
    print(f"度数 {d}: {count} 个节点")

代码3运行结果 #

True
度数 50: 18 个节点
度数 54: 5 个节点
度数 51: 20 个节点
度数 46: 14 个节点
度数 49: 17 个节点
度数 56: 7 个节点
度数 45: 14 个节点
度数 40: 4 个节点
度数 44: 9 个节点
度数 48: 16 个节点
度数 53: 11 个节点
度数 47: 16 个节点
度数 52: 11 个节点
度数 61: 4 个节点
度数 43: 7 个节点
度数 57: 4 个节点
度数 55: 9 个节点
度数 59: 1 个节点
度数 41: 4 个节点
度数 42: 3 个节点
度数 39: 3 个节点
度数 58: 1 个节点
度数 38: 1 个节点
度数 62: 1 个节点

问题分析与解决方案 #

问题1：bipartite.projected_graph()的使用误区 #

bipartite.projected_graph()的作用是从二分图生成单分图投影，它本身不会生成二分图。传入非二分图的幂律随机图，自然得不到二分图；传入二分图时，必须指定要投影的分图节点集合（比如bipartite.projected_graph(G, top_nodes)，其中top_nodes是二分图其中一个分图的节点列表），否则会报错。如果目标是生成幂律度分布的二分图，这个函数不是生成工具，而是分析工具。

问题2：随机幂律图的二分性不稳定 #

random_degree_sequence_graph()生成的是普通无向图，不是二分图。这类图是否为二分图完全随机——只有当图中不存在奇数环时才是二分图，而随机生成的幂律图可能包含奇数环，所以is_bipartite()结果随机。

正确生成幂律度分布二分图的方法 #

直接针对二分图的两个分图分别指定幂律度序列，用bipartite.configuration_model()生成：

import networkx as nx
from networkx.algorithms import bipartite
from networkx.utils.random_sequence import powerlaw_sequence

# 定义两个分图的节点数
n_top = 50
n_bottom = 100

# 生成两个分图的幂律度序列（确保序列和相等，否则无法生成二分图）
while True:
    top_degrees = [int(round(d)) for d in powerlaw_sequence(n_top, exponent=2.5)]
    bottom_degrees = [int(round(d)) for d in powerlaw_sequence(n_bottom, exponent=2.5)]
    if sum(top_degrees) == sum(bottom_degrees):
        break

# 用配置模型生成二分图
G = bipartite.configuration_model(top_degrees, bottom_degrees)

# 移除自环（配置模型可能生成自环）
G.remove_edges_from(nx.selfloop_edges(G))

# 验证是否为二分图
print(bipartite.is_bipartite(G))

# 查看度分布
top_nodes = {n for n, d in G.nodes(data=True) if d['bipartite'] == 0}
bottom_nodes = set(G) - top_nodes

print("第一分图度分布：")
top_deg = sorted(d for n, d in G.degree(top_nodes))
print(top_deg)

print("第二分图度分布：")
bottom_deg = sorted(d for n, d in G.degree(bottom_nodes))
print(bottom_deg)

代码说明：

1. bipartite.configuration_model()专门用于根据两个分图的度序列生成二分图，只要两个序列的和相等（总边数一致），就能保证生成合法的二分图。
2. 生成幂律序列取整后，必须校验两个序列的和是否相等，否则无法生成二分图。
3. 配置模型可能生成自环，需要手动移除，避免影响后续分析。

如果想在已有的二分图基础上添加幂律分布的节点，可以修改代码3的逻辑，直接给新节点指定幂律度数：

# 在代码3的基础上，给新节点添加幂律分布的边
new_nodes_degree_seq = [int(round(d)) for d in powerlaw_sequence(m, exponent=2.5)]
for i, deg in enumerate(new_nodes_degree_seq):
    node_id = 2*n + i
    # 随机分配到某个分图
    G.add_node(node_id, bipartite=0 if random.random() < 0.5 else 1)
    target_part = 1 if G.nodes[node_id]['bipartite'] == 0 else 0
    targets = [n for n in G.nodes if G.nodes[n]['bipartite'] == target_part]
    # 优先选择度数高的节点连接（模拟偏好依附）
    target_weights = [G.degree(n) for n in targets]
    selected_targets = random.choices(targets, weights=target_weights, k=deg)
    for target in selected_targets:
        G.add_edge(node_id, target)

内容的提问来源于stack exchange，提问作者Александр Соколов