You need to enable JavaScript to run this app. 如何将Facebook定向广告投放问题建模为Maximum Flow问题
优惠活动
大模型
产品
解决方案
定价
更多

如何将Facebook定向广告投放问题建模为Maximum Flow问题

现有思路的核心偏差
  • 不要把源点直接连接用户:如果源点直连用户,会把“单用户最多展示1条广告”的约束提前放到流量入口,没有剩余空间承载广告主的最低投放要求、人群定向的过滤逻辑。
  • 节点流向不要搞反:人群组是广告主和用户之间的定向过滤层,逻辑链路是“广告主定向某个人群组→该群组覆盖的用户可被该广告主触达”,不是“用户归属某个人群组→匹配对应广告”。你之前想到基于二分图做匹配的方向是对的,但这不是简单的两方二分图,是带中间过滤层的多段流网络。
完整最大流图结构定义

整个图为单向有向图,流量从靠近源点的一侧流向靠近汇点的一侧,所有节点、边、容量设置严格对应业务约束:

节点清单

共分为5层节点:

  • 超级源点S:全网络的流量起点,无入边
  • 广告主节点层:共m个节点,依次对应m家签约广告主A₁、A₂、…、Aₘ
  • 人群组节点层:共k个节点,依次对应预先划分好的k个可重叠人群组G₁、G₂、…、Gₖ
  • 用户节点层:共n个节点,依次对应当前单分钟内所有在线用户U₁、U₂、…、Uₙ
  • 超级汇点T:全网络的流量终点,无出边

边与容量设置

每一条边都对应一个明确的业务约束:

  • 从超级源点S到每个广告主节点A_i:边容量设置为该广告主的最低投放要求r_i。代表广告主的最低投放硬约束——广告主最多能从源点获取r_i个单位的流量,当这条边被流满时,就代表该广告主完成了最低投放量要求。
  • 从每个广告主节点A_i到其定向人群集合X_i内的所有人群组节点G_g:边容量设置为不小于n的足够大值(比如直接取n,即全平台在线用户总数)。代表广告主的定向规则:广告主的流量只能流到自己指定的人群组节点,完全无法连通未纳入X_i的人群组,自然不可能触达对应人群组外的用户;这里不设置容量上限,是因为人群组本身没有投放人数限制。
  • 从每个人群组节点G_g到所有属于该人群组的用户节点U_j:边容量同样设置为不小于n的足够大值。代表人群组的覆盖规则:某个人群组的流量只能传递给组内的用户,组外用户和该人群组没有连通路径,自然收不到对应广告。
  • 从每个用户节点U_j到超级汇点T:边容量设置为1。代表单用户的展示约束:从该用户节点能流出的最大流量只有1,不管前面有多少广告主、多少人群组连通到这个用户,最多只能有1个单位的流量经过该用户流向汇点,也就是最多给这个用户展示1条广告。

这个结构充分利用了预先划分的人群组压缩图规模:如果跳过人群组层直接在广告主和用户之间连边,边数会随用户数、广告主数线性膨胀;加入人群组的中间层后,只需要把广告主和它定向的少数几个人群组连边,就能实现同等的定向过滤效果,计算效率会高很多。

单分钟投放可行性判定
  • 先计算所有广告主的最低投放量总和:R = sum(r_i, i=1到m)
  • 在上述构建的图上运行最大流算法,得到的最大流值记为F
  • 判定规则:
    • 如果F == R:说明可以通过流量的传导,给每个广告主分配到刚好r_i个符合定向要求的用户,同时满足每个用户最多展示1条广告的约束,所有合同要求可被覆盖。
    • 如果F < R:说明存在流量缺口,无法同时满足所有广告主的最低投放要求。
投放匹配结果提取方法

当判定可行时,不需要额外的匹配计算,直接从流网络的残留边信息就能得到完整的投放方案:

  • 遍历所有人群组G_g到用户U_j的边,只要某条边的实际流量大于0(即初始容量减去剩余容量的差值),就说明有1个单位的流量沿着某条广告主路径传送到了这个用户。
  • 顺着流量方向反向回溯到对应的广告主节点A_i,就代表“将广告主i的广告投放给用户j”。
  • 由于用户节点到汇点的边容量为1,每个用户最多只会承接1个单位的流量,自然不会出现多个广告主抢占同一用户的问题;由于源点到广告主的边容量为r_i,且最大流刚好等于总要求量R,每个广告主的路径上刚好累计流过r_i个单位的流量,自然满足最低投放要求。

内容的提问来源于stack exchange,提问作者Max Jones

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.10.31 12:54:05