如何用R语言生成指定节点度分布与循环数的有向循环图？

1. 解决度分布精准控制问题 #

erdos.renyi.game是基于概率的随机图生成器，无法直接指定节点度的比例分布。要实现精准控制，需先为每个节点分配目标度，再基于目标度构建边：

• 根据输入的节点总数和度分布比例，计算每个度对应的节点数量（例如n=100时，80个节点度为3，15个为2，5个为1），取整后调整总数确保等于节点数；
• 为每个节点标记目标度数，后续生成边时严格满足该目标，保证无孤立节点（已通过最小度为1的设置实现）。

2. 优先生成多节点循环，控制循环数量 #

要避免两节点互指的2-循环，需优先构建长度≥3的环，再填充剩余边：

1. 确定目标循环数num_cycles，从节点池中随机选取不重叠的节点子集，每个子集大小≥3；
2. 对每个子集生成有向环（例如节点A→B→C→A），每生成一个环，对应节点的剩余度数减1；
3. 若循环数需求较大，可允许部分节点参与多个环，但需保证节点剩余度数≥0；
4. 剩余边填充阶段，禁止生成A→B且B→A的2-循环，优先生成单向边或更长的链，最终满足所有节点的目标度。

3. 完整Python实现（基于igraph） #

import igraph as ig
import random

def generate_custom_dcg(n_nodes, degree_dist, num_cycles):
    # 1. 分配节点目标度
    degree_counts = {}
    remaining_nodes = n_nodes
    for degree, ratio in degree_dist.items():
        count = int(n_nodes * ratio)
        degree_counts[degree] = count
        remaining_nodes -= count
    # 调整剩余节点（分配给占比最大的度）
    if remaining_nodes > 0:
        max_degree = max(degree_dist.keys())
        degree_counts[max_degree] += remaining_nodes
    
    # 创建节点目标度列表并打乱顺序
    nodes = []
    for degree, count in degree_counts.items():
        nodes.extend([degree]*count)
    random.shuffle(nodes)
    
    # 初始化图
    g = ig.Graph(directed=True)
    g.add_vertices(n_nodes)
    g.vs["target_degree"] = nodes
    g.vs["remaining_degree"] = nodes
    
    # 2. 生成优先多节点循环
    cycle_count = 0
    available_nodes = list(range(n_nodes))
    
    while cycle_count < num_cycles and len(available_nodes) >=3:
        # 随机选3-5个节点构建循环（可调整范围）
        cycle_size = random.randint(3, min(5, len(available_nodes)))
        cycle_nodes = random.sample(available_nodes, cycle_size)
        # 生成有向环
        for i in range(cycle_size):
            src = cycle_nodes[i]
            dst = cycle_nodes[(i+1)%cycle_size]
            if g.vs[src]["remaining_degree"] > 0 and g.vs[dst]["remaining_degree"] > 0:
                g.add_edge(src, dst)
                g.vs[src]["remaining_degree"] -=1
                g.vs[dst]["remaining_degree"] -=1
        cycle_count +=1
        # 更新可用节点（移除度数已用完的节点）
        available_nodes = [v for v in available_nodes if g.vs[v]["remaining_degree"] >0]
    
    # 3. 填充剩余边，避免2-循环
    all_nodes = list(range(n_nodes))
    for src in all_nodes:
        while g.vs[src]["remaining_degree"] >0:
            # 筛选候选节点：排除自身、已形成双向边的节点、度数已用完的节点
            candidates = [
                dst for dst in all_nodes 
                if dst != src 
                and not g.are_connected(dst, src)
                and g.vs[dst]["remaining_degree"] >0
            ]
            # 若无有效候选，放宽条件到非双向的已连接节点
            if not candidates:
                candidates = [
                    dst for dst in all_nodes 
                    if dst != src 
                    and g.vs[dst]["remaining_degree"] >0
                ]
            if not candidates:
                break  # 理论上不会出现，因初始设置无孤立节点
            dst = random.choice(candidates)
            g.add_edge(src, dst)
            g.vs[src]["remaining_degree"] -=1
            g.vs[dst]["remaining_degree"] -=1
    
    # 验证度分布（可选）
    assert all(deg == g.degree(v) for v, deg in enumerate(g.vs["target_degree"])), "度分布不匹配"
    actual_cycles = len(g.simple_cycles(mode="all"))
    print(f"生成完成：节点数{n_nodes}，目标循环数{num_cycles}，实际循环数{actual_cycles}")
    
    return g

# 示例调用
if __name__ == "__main__":
    dcg = generate_custom_dcg(
        n_nodes=100,
        degree_dist={3:0.8, 2:0.15, 1:0.05},
        num_cycles=15
    )
    # 查看节点度分布
    print("节点度分布：", dcg.degree())

代码说明 #

• 度分布控制：通过先分配目标度再填充边的方式，确保每个节点的度数严格符合设定比例；
• 多节点循环优先：优先从可用节点中选取3-5个节点生成环，从根源减少2-循环的出现；
• 剩余边填充：严格排除双向边生成，仅在无其他候选时允许单向重复边；
• 验证机制：加入断言检查度分布是否符合预期，同时输出实际循环数供参考。

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