基于网络的HIV预防干预：通过级联感知传播抑制

# 基于网络的HIV预防干预：级联感知的传播抑制策略
来源：https://arxiv.org/html/2605.20218
Akseli Kangaslahti 哈佛大学 akselikangaslahti@g\.harvard\.edu & Davin Choo 哈佛大学 davinchoo@seas\.harvard\.edu & Milind Tambe 哈佛大学 tambe@seas\.harvard\.edu & Alastair van Heerden 威特沃特斯兰德大学 威特健康联盟 alastair\.vanheerden@wits\.ac\.za & Cheryl Johnson 世界卫生组织 johnsonc@who\.int

###### 摘要

治疗和预防人类免疫缺陷病毒（HIV）仍然是一项关键的全球卫生挑战。虽然抗逆转录病毒疗法为实现病毒抑制——从而有效消除个体传播风险——提供了途径，但系统性的资源限制制约了干预措施的覆盖范围。本文研究了在病毒未抑制个体中战略性地分配密集型资源，以最小化传播网络内预期的新感染级联。我们将这一挑战形式化为一个新颖的约束优化问题：我们有一定资源来“治疗”k个来自病毒未抑制集合P的个体，并建立了其与现有计算文献的理论联系。随后，我们提出了级联感知的传播抑制（CAST）算法，这是一种多项式时间的(δ,ε)-近似算法，通过利用与最小k-并集（MkU）问题的联系以及Hoeffding型集中不等式，实现了2√|P|的近似比。在真实世界的HIV网络上的广泛评估表明，CAST优于标准的公共卫生和计算机科学基线方法。此外，我们证明CAST在不同传染病网络、不同的边概率初始化以及包含不完美网络数据的设定下，均表现出经验上的鲁棒性。

## 1 引言

全球范围内有超过4000万人感染，人类免疫缺陷病毒（HIV）仍然是一项关键的全球卫生挑战。虽然目前尚无治愈方法，但适当的医学治疗可以将病毒抑制到有效消除进一步传播风险的水平。与联合国可持续发展目标3.3一致，UNAIDS提出了HIV 95-95-95目标，旨在到2030年实现95%的HIV感染者了解自身状况，95%了解自身阳性状况的人接受治疗，以及95%接受治疗的人达到病毒抑制。然而，公共卫生机构长期面临资源限制，因此优化HIV治疗和预防的资源分配至关重要。这尤其是一个紧迫的问题，因为已经受限的公共卫生机构目前正面临HIV预防工作的额外预算削减。世界卫生组织（WHO）已推荐基于网络的策略来帮助应对这些资源限制。

在这项工作中，我们处理这样一个资源分配挑战，以支持基于网络的HIV预防工作。临床研究已证实，病毒抑制的个体不会传播病毒，这一发现支撑了“检测不到等于无法传播”（U = U）运动，并构成了称为“治疗即预防”（TasP）的公共卫生策略的基础，该策略利用个体治疗作为结构性工具来降低人群层面的发病率。然而，病毒抑制可能因多种因素受到阻碍，包括药物依从性差和医疗可及性有限，这反过来又会导致更广泛的耐药性挑战。尽管公共卫生机构可以提供一些支持，如依从性咨询、病毒载量监测或高效治疗方法，但资源有限。因此，当公共卫生机构识别出一组未接受HIV治疗和/或病毒未抑制的个体时，他们必须选择如何战略性地分配这些资源，以优先对有限数量的个体进行密集型干预，目标是最大限度地减少社区传播网络中预期的新感染级联。例如，这种情况可能出现在试图扩大服务以覆盖服务不足的人群时。此外，由于收集信息以了解完整网络可能成本高昂且耗时，干预策略应理想地适应成本更低、收集更快的不完美网络。我们专注于开发一种能够帮助解决这一问题的算法方法。我们与一所南非大型大学以及一个全球非营利卫生组织的领域专家密切合作开展这项研究，最终目标是在实地环境中部署我们的方法。图1展示了我们的合作者在南非开展的HIV预防实地工作。

[图1说明]

图1：我们的合作者在南非开展HIV预防实地工作的图像。

贡献。我们的理论和模拟表明，我们提出的CAST算法在提高HIV预防资源效率方面具有强大的实际应用潜力，即使在更现实的不完美网络问题实例下也是如此。具体来说：

1.  **干预模型**：我们引入并形式化了通过节点治疗最小化感染（MINT）问题，其中我们有资源来“治疗”k个来自病毒未抑制集合P的个体。这是一个新颖的优化问题，捕捉了上述现实世界中有限资源分配问题的目标和约束。我们分析并证明了该问题的重要数学性质，表明其最小化目标是非负、单调且子模的，并且MINT可以简化为更常研究的“影响最小化”（IMIN）问题的一个特例，但仍与“影响最大化”（IM）问题不同。
2.  **级联感知的传播抑制（CAST）**：对于随机传播网络的任意固定实现，我们证明MINT等价于最小k-并集（MkU）问题。通过将MkU近似算法与基于样本的结构化集合构造以及Hoeffding型集中不等式相结合，我们为一般MINT问题提供了CAST，这是一种多项式时间的(δ,ε)-近似算法，其预期新增感染数的近似比为2√|P|。
3.  **实证评估**：我们在模拟中使用公开的真实世界HIV网络数据集评估CAST，并将其性能与来自相关公共卫生和计算机科学文献的几种基线算法进行比较。我们表明，在各种MINT实例中以及超越HIV的疾病网络上，CAST始终优于这些基线方法。
4.  **向不完美网络的扩展**：为了解决网络收集和可观测性方面的实际部署挑战，我们研究了在成本更低、记录更快的完整网络上进行治疗决策的有效性，并辅以学习的链路预测。由于边概率也可能难以且昂贵地估计，我们进一步评估了CAST如何适应不匹配的边概率初始化。我们的实证模拟表明，CAST在这些不完美网络设定下仍然保持鲁棒性。

## 2 预备知识与相关工作

### 记号。

我们用粗体字母（例如，**S**）表示集合，用书法字母（例如，\(\mathcal{G}, \mathcal{H}\)）表示图和随机实现。

**集中不等式。** 我们将使用标准集中不等式将经验估计与期望联系起来。特别地，我们使用以下形式的Hoeffding不等式。

###### 定理1 (Hoeffding不等式).
设 \(X_1, \ldots, X_n\) 是独立的随机变量，满足 \(a_i \le X_i \le b_i\)。那么，对于任意 \(\varepsilon > 0\)，
\[
\Pr\left( \left| \sum_{i=1}^n X_i - \mathbb{E}\left[\sum_{i=1}^n X_i\right] \right| > \varepsilon \right) \le 2\exp\left( -\frac{2\varepsilon^2}{\sum_{i=1}^n (b_i - a_i)^2} \right)
\]

**概率传播模型。** 在像我们这样的一次性干预设定中，我们感兴趣的是最终的终身传播结果，而非逐步的、细粒度的时态动态。我们还需要概率性地考虑传播：对于像HIV这样的性传播感染，可能存在永远不发生传播的网络边。为此，我们采用独立级联（IC）模型来描述感染在网络 \(\mathcal{G}\) 上的扩散。在IC模型中，当一个节点 \(v\) 变为活跃状态时，它有一次离散的机会以概率 \(w_{(v,u)}\) 激活每个后继节点 \(u\)。两个个体之间这种共享行为的类型和频率带有特定的风险，这使得IC模型的“概率抛硬币”成为我们场景的自然表示，其中边的激活可以被视为累积的终身感染机会。像易感-感染（SI）模型这样的相关模型可以捕捉更细粒度的瞬态和时态动态，但不能提供对终身传播结果的自然度量，而这正是我们在这项工作中最终关心的。为了使这些模型适应一次性问题，我们需要设定一个任意的界限（在此之后我们不再关心传播），或者考虑无限边界，在这种情况下SI退化为从源节点出发的简单可达性。从数学角度来看，IC模型有一个“活边”解释：每条边独立地以概率 \(w_{(v,u)}\) 保留，从而生成一个随机图实现 \(\mathcal{H} \sim \mathcal{G}\)。在活边视角下，扩散过程等价于在 \(\mathcal{H}\) 中的可达性，因此期望是在随机图实现的分布上计算的。

**影响最大化。** 影响最大化旨在随机影响模型（如独立级联（IC）模型和线性阈值（LT）模型）下，选择能够最大化预期传播范围的种子集。与IC模型相比，LT模型捕捉累积影响，即当来自其邻居的总影响超过某个阈值时，节点被激活。这不太适合我们的设定。这两个模型的一个关键特征是预期传播是单调子模的，从而允许通过贪心算法实现 \((1-1/e)\) 近似。除了IC和LT之外，其他影响模型和相应的算法也被提出和研究，包括触发模型、竞争影响模型和时延扩散模型，尽管IC显然仍是我们的最佳选择。

###### 定义2 (IC下的影响最大化 (IM)).
给定一个有向概率图 \(\mathcal{G} = (\mathbf{V}, \mathbf{E}, w)\) 和一个预算 \(k \in \mathbb{N}\)，IM问题是选择一个种子集 \(\mathbf{S} \subseteq \mathbf{V}\)，满足 \(|\mathbf{S}| \le k\)，以最大化 \(\mathbb{E}_{\mathcal{H} \sim \mathcal{G}}[f_{\mathcal{H}}^{\texttt{IM}}(\mathbf{S})]\)，其中 \(f_{\mathcal{H}}^{\texttt{IM}}(\mathbf{S}) = |\{ u \in \mathbf{V} : u \text{ 在 } \mathcal{H} \text{ 中可从 } \mathbf{S} \text{ 到达} \}|\)。

**影响最小化与节点阻断。** 我们的工作与通过节点阻断进行影响最小化的研究最为相关。该领域的典型做法是固定初始活跃集合 \(\mathbf{Q}\)，专注于从 \(\mathbf{V} \setminus \mathbf{Q}\) 中阻断一组节点，以最小化影响通过网络扩散后的总活跃节点数。在活边解释下，IMIN等价于从每个实现 \(\mathcal{H}\) 中移除节点，并最大化从 \(\mathbf{Q}\) 可达的节点数量的减少量。IMIN的一个关键挑战是其目标**不是子模的**，这排除了标准贪心近似的可能性，并需要启发式或基于松弛的方法。我们稍后将证明，MINT的目标可以简化为IMIN的一个特例，而该特例是一个更容易解决的问题：我们的目标是子模的，因此我们可以利用子模**最小化**的已知结果。

###### 定义3 (IC下的影响最小化 (IMIN)).
设 \(\mathcal{G} = (\mathbf{V}, \mathbf{E}, w)\) 是一个有向概率图，初始活跃节点集为 \(\mathbf{Q} \subseteq \mathbf{V}\)。给定一个预算 \(k \in \mathbb{N}\)，IMIN问题是选择 \(\mathbf{S} \subseteq \mathbf{V} \setminus \mathbf{Q}\)，满足 \(|\mathbf{S}| \le k\)，以最小化 \(\mathbb{E}_{\mathcal{H} \sim \mathcal{G}}[ f_{\mathcal{H}}^{\texttt{IMIN}}(\mathbf{S}) ]\)，其中 \(f_{\mathcal{H}}^{\texttt{IMIN}}(\mathbf{S}) = |\{ u \in \mathbf{V} : u \text{ 在 } \mathcal{H}[\mathbf{V} \setminus \mathbf{S}] \text{ 中可从 } \mathbf{Q} \text{ 到达} \}|\)。

**最小k-并集 (MkU) 与子模最小化。** 最小k-并集 (MkU) 问题是组合优化中的一个核心挑战，与最大覆盖问题密切相关，两者已知是NP难的。这两个问题都涉及子模目标，但最大覆盖问题允许 \((1-1/e)\) 近似（已知是紧的），而MkU只有多项式时间算法实现 \(O(n^{\frac{1}{4}-\varepsilon})\) 和 \(2\sqrt{m}\) 近似（在某些复杂性猜想下大致是紧的）。

我们在定义4中正式定义MkU，并将利用chlamtac2018densest中的 \(2\sqrt{m}\) 近似作为我们工作中的一个子程序。该近似算法也有扩展，可以有效地近似一般的子模最小化问题。

###### 定义4 (MkU).
考虑在包含 \(n\) 个元素的全集 \(\mathbf{U}\) 上的 \(m\) 个集合 \(\mathbf{S}_1, \ldots, \mathbf{S}_m \subseteq \mathbf{U}\)。给定 \(k \in \mathbb{N}\)，目标是找到 \(k\) 个具有最小并集大小的子集。

**战略性网络干预。** 已有一些研究针对基于网络的干预措施来预防疾病传播。一个特别相关的研究领域是针对暴露前预防（PrEP）的目标分配，PrEP用于保护**未**感染HIV但有感染风险的个体。一种常见的方法是使用学习模型预测个体风险评分，以确定哪些个体面临最大的感染风险，而不是考虑潜在的下游网络影响。除了HIV PrEP，先前的工作还研究了一般的疫苗分配，以最小化预期的新感染，既有一次性设定...

（注意：翻译时保留了所有数学符号、引用标记、链接和格式，如列表、强调、段落等。由于原文长度限制，最后一个句子未完整，但保留原样。）