图网络A/B/C节点类分配：保留邻居全局概率分布的实现方法

先统一符号避免你原描述中的冲突：

• 总节点数为N，预先选好的A类节点共x个，记A类节点集合为S_A
• 非A类节点总数为M = N - x
• 全局约束：固定选出y个非A节点作为B类，剩余M-y个为C类
• 局部约束：任意A类节点的邻居，被分配为B类的概率为p（你原描述中"y概率"为笔误，此处用p指代单节点独立概率）

核心问题原理 #

你遇到的共同邻居概率偏高问题的本质是：如果一个非A节点是k个A类节点的共同邻居，直接对每个A的邻居独立采样p的话，该节点最终被设为B的概率为1 - (1-p)^k，k越大偏差越明显，同时还可能超出全局y个B类的总量限制。

方案1：严格满足局部概率约束（允许B类总数小幅波动） #

如果仅要求局部概率符合要求，允许B类总数在y附近小幅波动，可使用概率校正法：

1. 遍历所有非A节点，统计每个节点u的A类邻居数量k_u，无A类邻居则k_u=0
2. 对每个非A节点u：
   • 若k_u = 0：默认分配为C类（若允许无A邻居的节点为B，可按全局平均概率y/M采样）
   • 若k_u > 0：生成0-1区间的随机数r，若r < 1 - (1-p)^(1/k_u)，则将u设为B类，否则设为C类
     该方法的数学逻辑是：校正后的采样概率q_u会抵消多A邻居的重复影响，最终u被选中为B的概率刚好等于要求的p。

方案2：严格满足全局B类总数为y，同时逼近局部概率约束 #

如果要求B类总数严格等于y，建议使用加权随机采样法，这是实际工程中最常用的方案：

1. 遍历所有非A节点，统计每个节点u的A类邻居数量k_u，无A类邻居则k_u=0
2. 为每个非A节点u计算采样权重w_u：
   • 若k_u > 0：w_u = 1 - (1-p)^(1/k_u)（和方案1的校正概率一致）
   • 若k_u = 0：w_u = y/M（全局平均概率，可根据业务需求调整权重）
3. 对所有非A节点按权重w_u做无放回加权采样，取出y个节点设为B类，其余设为C类
   该方案既保证全局总量符合要求，也让有k个A邻居的节点被选中的概率尽可能逼近预设的p。

伪代码实现（方案2） #

# 输入参数
graph: 图对象，支持调用get_neighbors(node)获取对应节点的邻居列表
S_A: 已确定的A类节点集合
y: B类节点总配额
p: A类邻居被分配为B的目标概率

# 步骤1：统计所有非A节点的A类邻居数
k_counter = {}
non_A_nodes = [node for node in 全量节点 if node not in S_A]
for a in S_A:
    for neighbor in get_neighbors(a):
        if neighbor not in S_A:
            k_counter[neighbor] = k_counter.get(neighbor, 0) + 1

# 步骤2：计算每个非A节点的采样权重
weight_map = {}
for u in non_A_nodes:
    k_u = k_counter.get(u, 0)
    if k_u == 0:
        # 无A邻居的节点权重可自定义，此处取全局平均概率
        weight_map[u] = y / len(non_A_nodes)
    else:
        # 概率校正抵消多A邻居影响
        weight_map[u] = 1 - (1 - p) ** (1 / k_u)

# 步骤3：加权无放回采样y个B类节点
weights = [weight_map[u] for u in non_A_nodes]
B_nodes = 加权无放回采样函数(population=non_A_nodes, weights=weights, n=y)
C_nodes = [u for u in non_A_nodes if u not in B_nodes]

# 输出最终分类结果
final_classes = {node: 'A' for node in S_A}
final_classes.update({node: 'B' for node in B_nodes})
final_classes.update({node: 'C' for node in C_nodes})

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