实验网络怎样分簇,才能少切断真实传播?图划分与边界泄漏
手算加权切边率,理解因果实验中的图分簇目标、规模约束和残余跨簇干扰。
上一篇把用户结果写成自己的分配与邻居暴露的函数。本篇接着回答设计前一个问题:已知一张关系图,如何把用户分成可随机化的簇,让强传播路径尽量留在簇内?下一篇再讲第一阶段如何给簇随机分配处理饱和度,第二阶段如何给簇内个人分配处理。
本篇只讲为因果实验划分网络簇。这和找出图里有趣的社区不是同一个目标:实验分簇要同时考虑传播边界、簇大小、处理前特征平衡,以及后续能随机化的独立簇数量;切边越少也不自动代表因果估计越准确。
01 为什么普通用户级随机化会让朋友分到两臂?#
设图 有 位用户。边 表示用户间可能的传播,权重 表示在实验前估计的互动强度或传播概率。用户级 A/B 逐人随机时,好友可能分别进入处理和对照;处理组的功能通过分享影响对照组,观测到的组间差便同时含有直接效果与串组影响。
一种设计是把用户先划为簇 ,再整簇随机。分簇目的不是声称簇间绝对没有影响,而是减少最可能造成污染的边跨越处理与对照簇的机会。分簇使用的图和权重必须在处理前冻结;若用实验结果反推“谁影响谁”,设计就被结果污染。
flowchart LR
A[处理前关系图与边权] --> B[候选图分区]
B --> C[检查切边率与簇规模]
C --> D[检查处理前特征与跨边界风险]
D --> E[固定簇 ID 与图版本]
E --> F[按簇随机化并保留足够独立簇]
F --> G[记录实际跨簇暴露并按设计分析]mermaid流程伪代码:
输入:处理前节点、加权边、簇数或允许规模区间、处理前平衡字段
冻结:节点集合、边方向/权重规则、去重和缺失边策略
枚举或运行候选划分:
计算切边总权、归一化边界比例、簇规模与协变量差异
排除:簇过大/过小、随机化簇数量不足、严重不平衡的方案
输出:分区、边界诊断、候选方案排序与冻结版本
随后:独立随机分配簇,而非把划分标签当作处理组text如果图很密,任何有限分区都会留下跨簇边。设计目标是降低关键传播路径的跨臂风险并量化残余边界,而不是把图画成互不相连的几个泡泡。
02 手算:六个人,切边率从 3% 变成 65%#
用 6 位用户构成两个三角形:1、2、3 之间各有权重为 1 的边;4、5、6 之间也一样;中间只有一条 3—4 边,权重为 0.2。总边权为 。
| 边 | 权重 | 解释 |
|---|---|---|
| 1—2、1—3、2—3 | 各 1.0 | 第一组内互动 |
| 4—5、4—6、5—6 | 各 1.0 | 第二组内互动 |
| 3—4 | 0.2 | 两组之间较弱互动 |
划分 A 为 与 ,只有 3—4 被切开,加权切边率为 。划分 B 为 与 ,1—3、2—3、4—5、4—6 四条单位边被切开,切边权为 4,切边率为 。两种方案都恰好三人一簇,规模平衡本身无法判断哪种更能保留传播路径。
这些权重是设计输入示例,不是从六个节点推断出的真实传播概率。线上可用处理前的转发、共用上下文、交互频率或经校准的传播概率构造权重,但必须说明口径和时间窗。
03 目标函数为什么不能只写“最小切边”?#
无向加权图的总边权记为 。给定分区 ,跨簇切边权是:
方便比较边界规模,但高节点度会主导它;**归一化切割(normalized cut)**按各簇的总连边量归一化,避免小簇被边权总和压住。两者都只是图结构代理,不会自动识别哪条边真的传播了处理。
单纯最小化 cut 会把整张连通图分成一个簇,切边为零,却只剩一个独立随机化单位,无法同时形成处理与对照。设计时要并列检查:
- 传播隔离:高权重、高概率传播边尽量留在簇内;方向性传播不能悄悄对称化。
- 簇规模:限制极小和极大簇,避免随机化单位失衡、一个簇支配加权估计。
- 处理前可比性:检查地域、活跃度和历史指标等协变量;分簇或后续配对只能用预处理字段。
- 独立簇数:簇过少会让随机化空间和推断自由度过小。几百万用户落在 8 个簇里,仍主要是 8 个独立分配单位。
最小 cut、归一化 cut、模块度和谱聚类都是可选目标,答案取决于后续随机设计与要估计的效果。谱聚类用图拉普拉斯嵌入找图结构;它不保证最小传播偏差,也不替实验者处理规模、平衡与簇数。前面的谱聚类文章讲几何结构;这里改问每种划分对因果设计有什么代价。
04 可手算的最小实现:枚举六人的平衡划分#
小图上可直接枚举固定大小的候选簇:固定节点 0 属于左簇以避免把互补分区计算两次。输入是节点、无向边 和左簇大小;输出切边权最低的平衡划分。这里只优化图边界,不包含生产所需的协变量平衡项或随机化推断。
from itertools import combinations
nodes = tuple(range(6))
edges = [
(0, 1, 1.0), (0, 2, 1.0), (1, 2, 1.0),
(3, 4, 1.0), (3, 5, 1.0), (4, 5, 1.0),
(2, 3, 0.2),
]
def balanced_partitions(nodes, left_size):
anchor, rest = nodes[0], nodes[1:]
for chosen in combinations(rest, left_size - 1):
left = frozenset((anchor, *chosen))
right = frozenset(nodes) - left
yield left, right
def cut_weight(partition, edges):
left, _ = partition
return sum(w for u, v, w in edges if (u in left) != (v in left))
candidates = list(balanced_partitions(nodes, left_size=3))
cut, (left, right) = min(
((cut_weight(p, edges), p) for p in candidates),
key=lambda row: row[0],
)
total_weight = sum(w for _, _, w in edges)
print(sorted(left), sorted(right), cut, cut / total_weight)
# [0, 1, 2] [3, 4, 5] 0.2 0.032258...pythoncombinations 枚举其余用户;frozenset 让成员判断明确;当一条边两个端点恰好一个在左簇时,它才跨越分区。六人三人一侧只需检查 个互补去重候选。
这段小程序只对这个小例子精确。真实图的候选分区数指数增长,常需多层图划分或局部搜索;算法输出仍须由边界、簇大小、特征平衡和设计模拟复核。不能把通用聚类器的 fit_predict 结果直接称作“最优实验设计”。
05 从候选分区到可审计的实验设计#
分区固定后,仍要单独随机化处理。若 20 个簇只形成两大组,用户级样本数再多也无法解决簇级自由度不足。检查每个候选的簇数、规模分布、处理前结果与协变量差异,再按真实方案随机分组;若使用配对簇随机化,预先保存 pair_id 和成对规则。
- 冻结图快照:记录入组规则、边方向、去重规则、权重定义与观测窗口。
- 比较候选目标:比较加权 cut、每簇规模、处理前特征,以及不同权重阈值的敏感性。
- 模拟随机化与干扰:在候选分区上反复执行计划的簇级分配,估算跨处理臂边权、实际暴露支持和估计量波动。
- 锁定方案:保存 graph_version、partition_version、算法参数、簇成员、随机种子和 allocation_version。
- 上线监控:记录实际跨边传播、跨簇转发与失联节点;主分析仍按分配方案做意向处理分析。
- 报告边界:公开簇数、切边口径、规模分布、重要边占比、图时间窗与未解决的干扰假设。
常见故障包括:以用户 ID 排序分簇却声称使用了关系图;把无向边存储两次又误算一倍总权;按处理后互动重构图;只报告总体切边率而遗漏跨簇高传播边;删掉低活跃对照用户却不更新目标总体。调试先手算十条边的切边,再检查边数量、总权重与节点度,然后对照原始快照重建分区。
键盘可展开:切边率低为什么还不能证明没有污染?
加权切边率只汇总选定图和边权。漏记的关系、方向性传播、处理后新关系、跨簇缓存共享都可能绕开这个数字。Tab 聚焦摘要后按 Enter 或 Space 展开;手机上也可点按。
即使方案做得很好,估计仍依赖边权代表实际传播、簇间干扰已控制或进入暴露模型、分配概率已知、簇数足够支持推断。若一个巨型组件把多数节点连在一起,不要硬切后声称隔离完成;可比较缓冲区、个体独立集、两阶段饱和度设计,或缩小估计目标。
与相近方法的边界#
| 方法 | 主要目标 | 不能单独保证 |
|---|---|---|
| 谱聚类 | 图拉普拉斯嵌入与切分几何 | 因果无偏、簇数充足、处理前平衡 |
| 传播加权图分区 | 降低估计的边界传播风险 | 边权测量正确、没有未知传播通路 |
| 配对簇随机化 | 平衡簇间处理前协变量 | 消除跨簇干扰 |
| 两阶段饱和度 | 随机簇级密度与个体分配 | 任意暴露映射都可识别 |
| 用户级 A/B | 简单个体分配 | 网络传播下的无污染对照 |
图划分是随机化之前的设计步骤。下一篇会在这些簇内先随机处理饱和度,再随机个人处理,讨论这种两阶段设计如何让直接效果和邻居溢出效果有可解释的对照。
思考练习#
- 总边权为 20,跨簇边权为 2.4。切边率是多少?若这 2.4 全来自一条高活跃节点的边,为什么总比例可能不够描述风险?
- 一个分区有 2 个簇、cut 为零;另一个有 12 个簇、cut 略高。若每臂需要多个独立簇进行推断,你会如何排除不可用候选?
- 若边权来自处理前 30 天分享频率,但功能会改变转发行为,哪些字段和敏感性分析应预注册?
延伸阅读#
- Ugander et al., Graph Cluster Randomization: Network Exposure to Multiple Universes (KDD 2013) ↗ — 图簇随机化与网络暴露概率。
- Eckles, Karrer & Ugander, Design and Analysis of Experiments in Networks: Reducing Bias from Interference ↗ — 网络分配如何降低干扰偏差。
- Fatemi & Zheleva, Network Experiment Designs for Inferring Causal Effects under Interference (2023) ↗ — 联合考虑干扰边界与选择偏差的网络设计。
- Viviano et al., Causal Clustering: Design of Cluster Experiments under Network Interference ↗ — 通过带惩罚的图割权衡干扰与实验误差。
上一篇说明暴露状态由关系图和随机方案共同定义;本文把关系图用于构造实验簇。下一篇进入两阶段随机化:先随机簇饱和度,再随机簇内个人,为预先指定的直接与溢出效果制造支持。