技术摘要：超越预期覆盖：公平影响力最大化中的下尾风险管理

1. 问题定义

影响力最大化 (Influence Maximization, IM) 是在社交网络中启动信息级联的基础框架，传统上被表述为选择一个种子集 $S$（受预算 $k$ 限制），以最大化在随机扩散模型（如独立级联模型）下的预期总覆盖范围。

本文识别了经典 IM 以及近期公平影响力最大化 (Fair Influence Maximization) 方法中的一个关键局限性：

• 经典 IM 优化的是聚合预期传播量，忽略了不同人口统计群体之间的分布差异。
• 公平 IM 方法（例如 Max-Min 预期覆盖、凹性社会福利）优化的是各群体的预期公平性。

核心脆弱性： 仅针对预期值进行优化，无法保护结构性弱势群体（例如具有微弱随机桥接能力的边缘群体）免受在不利扩散实现情况下的严重覆盖失败。一个群体可能拥有可接受的平均覆盖率，因为一个随机桥接偶尔会成功；但在该桥接失效时，该群体可能会遭受近乎零覆盖的情况。这种“下尾”风险在公共卫生或紧急警报等关键应用领域构成了真实的分配伤害，因为在这些领域，可靠性与平均覆盖范围同样重要。

本文将下尾风险感知的影响力最大化 (Lower-Tail Risk-Aware Influence Maximization) 问题形式化，该问题明确考虑了特定群体在随机扩散下覆盖不足的概率和严重程度。

2. 方法论

2.1 风险度量指标

作者引入了两个互补的、针对特定群体的风险度量指标，用以量化下尾暴露情况：

1. 下尾群体覆盖率 ($\ell_\alpha(S)$):

   • 通过对每个群体覆盖率分布的左尾进行条件风险价值 (Conditional Value-at-Risk, CVaR) 来定义。
   • 它代表了最不利的 $\alpha$-比例扩散实现情况下，各群体的平均覆盖率。
   • 目的： 量化不利结果的严重程度。

2. 最差群体缺口概率 ($r_\tau(S)$):

   • 定义为所有群体中，覆盖率低于平台设定的充足性阈值 $\tau$ 的最大概率。
   • 目的： 量化不可接受结果发生的频率。

2.2 目标函数

这些度量指标被整合到一个标量化的目标函数 $F_{\lambda, \beta}(S)$ 中：
$$F_{\lambda, \beta}(S) = \lambda \sigma(S) + (1 - \lambda) \ell_\alpha(S) - \beta r_\tau(S)$$
其中：

• $\sigma(S)$: 标准化预期总传播量。
• $\lambda \in [0, 1]$: 总覆盖范围与下尾公平性之间的权衡参数。
• $\beta \ge 0$: 缺口概率的风险惩罚权重。

2.3 算法框架：LTR-Greedy

该优化问题是 NP-hard 且非子模 (non-submodular) 的（由于存在群体最小值算子和阈值指示函数），因此无法获得标准的 $(1-1/e)$ 近似保证。

作者提出了 LTR-Greedy (下尾风险贪婪算法)，这是一个基于样本平均近似 (Sample-Average Approximation, SAA) 的算法框架：

1. 采样： 生成 $M$ 个独立的“活跃边 (live-edge)”场景（即扩散实现）。
2. 经验估计： 在这些场景中计算总传播量、下尾覆盖率（使用排序样本）以及缺口概率（使用指示函数）的经验估计量。
3. 贪婪选择： 迭代选择使经验目标 $\hat{F}_{\lambda, \beta}(S)$ 最大化的种子。
4. 评估： 使用一组独立的“留出 (held-out)”场景来评估性能，以防止对风险估计产生系统性的过度乐观。

理论特性：

• 该目标函数关于 $S$ 是单调不减的。
• 文中建立了估计器的一致收敛性，表明只需 $O(\frac{1}{\alpha^2 \epsilon^2} \log(\dots))$ 个样本即可实现跨所有可行种子集的准确估计。

3. 核心贡献

本文概述了四项具体贡献：

1. 重构问题： 将群体公平种子选择从纯粹的预期值分配任务转向分布风险管理任务，明确建模了覆盖缺口的概率和严重程度。
2. 新指标： 引入下尾群体覆盖率（严重程度）和最差群体缺口概率（频率）作为公平资源分配的不同设计维度。
3. 算法开发： 开发了针对非子模风险目标的样本平均贪婪框架 LTR-Greedy，并提供了关于单调性、硬度和估计器收敛性的理论分析支持。
4. 实证验证： 通过综合实验量化了总覆盖范围与群体层面暴露可靠性之间的权衡。

4. 实验结果

该方法在合成网络（测试同质性、群体规模不平衡和桥接瓶颈）和真实拓扑结构（Epinions, Slashdot, Facebook ego networks, 和 Pokec）上进行了评估。

主要发现：

• 缺口差距： 标准的传播贪婪算法 (Spread-Greedy) 会导致最差群体的缺口概率（覆盖率 < $\tau$）在合成基准测试中超过 60%，在真实网络中约为 12%。
• 基于期望的公平性的局限性： Max-Min Greedy 和 Log-Welfare Greedy 等方法虽然改善了预期覆盖的平衡性，但未能显著控制阈值失效（缺口概率仍然很高，例如在合成测试中约为 37-41%）。
• LTR-Greedy 的表现：
  • 缺口减少： 与标准传播最大化相比，LTR-Greedy 将最差群体的缺口降低了超过 50%（例如，在合成基准测试中从 63.13% 降至 31.27%；在真实拓扑中从 12.43% 降至 2.89%）。
  • 代价： 这种减少仅带来了微小的预期总传播量损失（在合成网络中通常 < 6%，在真实网络中约 5%）。
  • 鲁棒性： 结果在高样本协议以及变化的阈值 ($\tau$) 和参数 ($\lambda, \beta$) 下依然成立。
• 项归因： “缺口惩罚”项 ($-\beta r_\tau$) 被确定为降低失效频率的主要驱动力，而“下尾覆盖率”项 ($\ell_\alpha$) 则提升了失效发生时的结果严重程度。

5. 重要性与主张

本文主张，下尾风险是公平影响力最大化中一个本质且独特的设计维度，它独立于基于预期值的公平性。

• 区别性： 优化预期群体福利并不保证在不利条件下能获得可靠的暴露。一个群体可以拥有高预期覆盖率，却面临频繁且接近于零覆盖的事件。
• 实际效用： 所提出的框架使平台设计者能够实现对总覆盖范围与脆弱群体暴露可靠性之间可衡量的、受控的权衡。
• 方法论转变： 这项工作推动了该领域从“分布盲目”或“预期盲目”的优化转向风险感知型分配，为在随机扩散环境下评估和缓解群体层面的暴露失败提供了实用方法。

作者总结道，尽管基于预期水平的公平性基准方法在正确的方向上迈出了步伐，但它们仍未解决实质性的下尾风险问题，而在失败会导致严重后果的应用场景中，这一点至关重要。