复杂网络作为解析与表征多类传播现象的关键工具, 在信息扩散、谣言传播及传染病防控等诸多领域得到广泛应用^[1-4]. 其中, 由病毒或其他病原体引发的传染病仍对公共健康与社会稳定构成持续威胁^[5]. 作为应对流行病暴发和网络结构破坏的重要策略, 网络免疫问题旨在有限预算下识别并免疫一小部分关键节点, 以最大程度削弱传播的规模与速度^[6,7].

在经典网络框架中, 节点间关系通常以二元连接建模, 并由此发展出多种免疫策略. 最简单的是随机免疫, 即为所有节点分配相同的免疫概率, 当覆盖率超过某一阈值时即可有效抑制传播^[8], 但其往往需要较高的免疫比例才能产生显著效果. 为了提升免疫效率, 研究者提出了多种目标式免疫策略. 例如, 度中心性(degree centrality, DC)通过优先免疫高度节点以削弱网络连通性^[9]; 介数中心性(betweenness centrality, BC)选取位于大量最短路径上的节点, 以阻断关键传播通路. 然而, 该方法对网络结构依赖较强, 容易在密集区域或社区边界附近重复选择节点, 对拓扑扰动敏感, 鲁棒性有限. 为获得更优的免疫节点选择结果, 研究者开始将元启发式优化方法引入网络免疫任务的求解过程中. 其中, 模拟退火(simulated annealing, SA)是典型代表, 它通过模拟物理退火过程在解空间中执行全局搜索, 并以一定概率接受次优解以避免陷入局部最优. 然而, SA的性能对温度初始化与退火策略高度敏感, 在大规模网络上往往表现出收敛缓慢、计算成本高等问题, 进而限制了其在实际免疫优化中的应用^[10].

此外, 研究者从爆炸渗流的视角提出了关系相关(relationship-related, RR)策略, 以新的方式刻画网络免疫问题^[11]. RR策略通过在候选节点集上进行多轮抽样, 并依据预设的关联规则度量节点间的相关性, 从而生成免疫节点的移除组合. 在仅免疫少量节点的情况下, 该方法即可显著削弱网络的最大连通分量(giant connected component, GCC). 然而, RR策略需要在大规模候选空间中反复评估和更新相关性, 计算成本高且难以应用于大规模网络. 为提升效率, 后续研究提出了边缘节点集重建方法(reconstruction method, RM)^[12], 通过提前剔除对连通性贡献较弱的边缘节点, 将优化域压缩至关键节点子集, 并以减少GCC规模为直接优化目标, 从而在保持接近RR策略的免疫效果的同时显著降低计算开销.

尽管前述方法在提升免疫效率方面取得了显著进展, 但它们大多仍基于成对交互的传统网络模型, 难以反映现实系统中普遍存在的多主体群体交互特征. 为刻画此类高阶关系, 研究者引入了超图模型. 相比仅连接两个节点的普通边, 超图中的超边能够同时关联多个节点, 从而自然地描述群体层面的交互过程. 大量实证研究表明, 高阶交互会显著改变传播动力学, 这意味着若仍采用基于成对网络设计的免疫策略, 在群体交互占主导的情形下往往难以取得理想效果. 因此, 有必要构建能够显式建模高阶交互的免疫策略, 以准确反映其对传播过程的影响. 基于这一动机, 本文在超图框架下提出了一种融合社区划分与自适应蚁群优化的免疫策略HACO. 该方法首先通过社区划分挖掘超图中的群体结构, 并依据社区规模与重要性进行免疫预算分配; 随后构建由多种中心性指标共同筛选的候选节点集, 确保搜索空间聚焦于关键区域. 在此基础上, 自适应蚁群算法在候选集上迭代搜索免疫节点组合, 并通过动态调整信息素权重及贪心选择概率, 实现更高效且稳定的优化过程. 最终, HACO能够在有限预算下识别最具影响力的免疫节点, 从而实现对高阶传播过程的精确控制.

本文组织结构如下: 第2节给出超图免疫问题的形式化描述, 并介绍本文采用的基于超图的SIR-CP传播模型; 第3节详细阐述所提出的社区划分驱动的自适应蚁群免疫算法HACO, 包括候选节点池构建、适应度函数设计以及信息素的动态更新机制; 第4节呈现实验设置与结果分析, 涵盖数据集说明、参数敏感性评估以及与多种基线方法的系统对比; 第5节对全文工作进行总结, 并讨论未来可能的改进方向和应用前景.

超图是一类能够刻画高阶交互关系的网络模型, 形式化表示为$ {\cal{H}} = (V, E) $, 其中V表示由N个节点组成的节点集合, E为包含M条超边的超边集合. 不同于传统图中每条边仅连接两个节点, 超图中的超边可同时关联多个节点, 从而能够直接描述多主体参与的群体交互过程. 得益于这一结构特性, 超图在建模社交互动、生物关联、学术合作等存在复杂群体行为的系统时具有显著优势, 能够更加全面地揭示高阶交互对系统结构与动力学的影响^[13-16].

超图的结构通常通过关联矩阵进行刻画, 其定义为$ {\boldsymbol{B}} \in \{0, 1\}^{N \times M} $, 矩阵元素如下:

该矩阵以二值形式明确表示节点与超边的隶属关系, 为分析超图的结构特性、构建中心性指标以及设计后续算法提供了基础性的数学工具.

在超图结构中, 传染病的扩散是通过多主体共同参与的群体性交互事件展开的, 每条超边代表一次潜在的传播场景. 对某个节点实施免疫不仅能够降低其自身的感染风险, 还会削弱其所参与超边的整体传播能力, 从而在源头上干扰多元交互引发的高阶传播链条. 然而, 随着网络规模扩大, 可能的免疫节点组合数量呈指数级增长, 使得在如此庞大的搜索空间中甄选最佳免疫策略成为一项具有典型NP-hard特征的组合优化任务. 因此, 在大规模超图中, 依赖精确算法求解往往不可行, 亟需采用启发式或学习驱动的方法来逼近最优解.

在形式化表达上, 超图免疫任务可定义为: 在给定超图$ {\cal{H}}=(V, E) $、免疫预算K以及初始感染节点集合$ I_0\subseteq V $的条件下, 寻找到规模为K的免疫节点集合S, 使得在指定传播模型下的感染峰值最小化:

其中$ \sigma(S, I_0) $表示在免疫集合S和初始感染集$ I_0 $的约束下, 传播过程中出现的最大感染规模.

为刻画超图环境下的传播动力学, 本文采用SIR-CP (susceptible-infected-recovered with contact process)模型^[17]. 在该模型中, 节点可处于三种状态: 易感(susceptible, S)、感染(infected, I)和恢复(recovered, R). 当易感节点与感染节点同时出现在某条超边内时, 存在被传染的可能性; 而感染节点在每个时间步会随机选择一条包含自身的超边, 并以概率β感染该超边中的每个易感节点. 同时, 感染节点以概率γ转化为恢复态, 并从传播过程中永久移除. 与依赖成对交互的传统SIR模型相比, SIR-CP通过引入感染节点随机选择超边的机制, 更准确地体现了超图中群体性交互的局部性、异质性和随机性特征, 从而能够更合理地描述现实中基于多人接触事件的高阶传播过程^[18].

图 1展示了SIR-CP模型的一个示例. 蓝色节点表示易感状态S, 红色节点表示感染状态I, 绿色节点表示恢复状态R. 在初始时刻$ t=0 $, 节点$ v_4 $处于感染态. 在第一个时间步$ t:0 \rightarrow 1 $中, 节点$ v_4 $激活其所属的超边$ e_3 $, 并以概率β沿该超边感染易感节点$ v_7 $. 因此, 在$ t=1 $时节点$ v_4 $与$ v_7 $均处于感染态. 在第二个时间步$ t:1 \rightarrow 2 $中, 节点$ v_7 $激活其关联的超边$ e_2 $, 并以概率β沿$ e_2 $感染易感节点$ v_5 $; 与此同时, 节点$ v_4 $以概率γ从感染态转变为恢复态. 最终, 在$ t=2 $时节点$ v_5 $和$ v_7 $处于感染态, 节点$ v_4 $进入恢复态, 其余节点保持易感状态.

蚁群优化(ant colony optimization, ACO)源于对蚂蚁觅食行为的抽象建模. 真实环境中, 蚂蚁在行进路径上释放信息素, 后续个体更倾向于沿信息素浓度较高的路径移动; 优质路径因被频繁访问而得到强化, 最终在群体层面的正反馈作用下收敛至近似最优解^[19,20]. 在算法实现上, ACO通过一群并行的“蚂蚁”在解空间中迭代构造候选解. 每只蚂蚁在构造过程中同时依赖记录历史经验的信息素浓度以及反映局部结构的启发式信息, 从而在搜索中实现经验利用与结构感知. 完成搜索后, 依据解的质量对相应路径进行信息素更新, 并通过全局信息素的挥发机制保持搜索多样性. 通过“解构造-适应度评估-信息素更新”的迭代框架, ACO在全局探索与局部开发之间取得动态平衡, 成为求解多类NP-hard组合优化问题的有效方法^[21].

本文提出的HACO算法将免疫节点集合视为路径, 将信息素解释为节点被选为免疫对象的偏好强度, 并在超图结构与SIR-CP传播模型的基础上定义相应的启发式信息与适应度函数. 如图2所示, 整体流程由候选集合降维与迭代优化两个阶段构成. 在候选集合降维阶段, 首先通过谱聚类对超图进行社区划分, 并根据社区规模对免疫预算进行分配; 随后结合多种中心性指标筛选潜在关键节点, 构建规模更精简、质量更高的候选节点集合, 从而有效降低搜索维度并提高初始解空间的可行性. 在迭代优化阶段, 每只蚂蚁依据信息素分布在候选池中逐步构造免疫解, 随后基于SIR-CP仿真获得传播峰值并计算综合适应度. 为避免参数固定导致的搜索偏好僵化, HACO在迭代过程中使用自适应机制, 通过动态调节信息素挥发系数、贪婪选择概率及扰动策略等关键控制因素, 使搜索行为能够随迭代进程在全局探索与局部开发之间自适应切换. 根据信息素更新规则, 对表现优异的解进行强化, 并通过挥发机制抑制过度收敛. 同时, 结合随机扰动与贪婪策略维持种群多样性并引导搜索方向, 从而在探索与利用之间实现动态平衡. 经过多轮迭代后, 算法最终收敛至高质量的免疫节点集合$ S^* $. 具体算法步骤如算法1所示.

为降低计算复杂度并充分利用超图的高阶结构特性, 算法在正式搜索前设置了候选集合降维环节. 该环节由三部分组成: 首先, 通过谱聚类对超图$ {\cal{H}} $进行社区划分, 以识别结构上紧密关联的区域; 其次, 根据各社区的规模对总免疫预算K进行比例分配, 使资源配置更贴合超图的结构差异; 最后, 结合多类中心性指标筛选潜在关键节点, 构建质量更高的候选节点池, 为后续蚁群搜索提供更具代表性的初始解空间. 以下将依次介绍这三个步骤.

在高阶网络中, 由超边刻画的群体交互使传播呈现明显的结构异质性, 社区内部高阶接触更为密集, 更易形成快速扩散, 而跨社区传播往往依赖少量跨社区超边或关键连接节点. 因此, 若在全局范围内直接选择免疫节点, 免疫资源可能集中于局部高密区域, 难以同时覆盖多个潜在传播簇并有效抑制跨社区扩散^[22-24]. 为提升免疫效率, 首先对超图$ {\cal{H}} = (V, E) $进行社区划分, 将结构上联系紧密的节点聚合到同一社区中, 并在社区层面分配免疫预算以指导后续优化过程. 社区划分采用基于归一化超图拉普拉斯矩阵的谱聚类方法^[25]. 节点$ v_i $的超度与超边$ e_j $的规模分别定义为$ k^{\mathrm{H}}_{i} = \displaystyle\sum\nolimits_{j=1}^{M} {{B}}_{ij} $, $ k^{\mathrm{E}}_{j} = \displaystyle\sum\nolimits_{i=1}^{N} {{B}}_{ij} $. 将所有节点的超度与所有超边的规模分别构成节点度矩阵$ {\boldsymbol{D}}_v = {\rm{diag}}\left(k^{\mathrm{H}}_{1}, \cdots, k^{\mathrm{H}}_{N}\right) $和超边度矩阵$ {\boldsymbol{D}}_e = {\rm{diag}}\left(k^{\mathrm{E}}_{1}, \cdots, k^{\mathrm{E}}_{M}\right) $. 在此基础上, 定义归一化超图拉普拉斯矩阵为^[25]

其中$ {\boldsymbol{I}} $为维度为$ N\times N $的单位矩阵. 对$ {\cal{L}} $计算特征值并按升序排列为$ 0 = \lambda_1 \leqslant \lambda_2 \leqslant \cdots \leqslant \lambda_{N} $, 选取最小的L个特征值对应的特征向量$ {\boldsymbol{u}}_1, \cdots, {\boldsymbol{u}}_L $, 组成特征矩阵:

将$ {\boldsymbol{U}} $的第i行视为节点$ v_i $在L维特征空间中的嵌入表示, 在这些嵌入向量上执行k-means聚类^[26], 最终将节点集合V划分为L个互不相交的子集, 从而得到社区划分

其中$ {\cal{C}} $表示社区集合, L为社区数量. 谱聚类方法能够通过特征向量空间的划分有效识别超图中的密集连接区域, 从而在保证结构合理性的同时缩小后续搜索空间.

在获得社区划分结果后, 需要依据各社区的规模对总免疫预算K进行分配, 以保证不同结构区域之间的资源配置保持一致与合理. 首先, 根据社区$ C_i $在整体节点集合中的占比计算其理论应分配的预算:

其中, $ \tilde{K}_i $为分配给社区$ C_i $的理论免疫预算, $ |C_i| $为社区规模.

由于实际选择的免疫节点数量必须为整数, 实施时首先对每个$ \tilde{K}_i $向下取整, 得到一组初始的整数预算, 使其总和不超过K. 随后计算剩余的未分配名额, 并根据各社区对应理论预算$ \tilde{K}_i $的小数部分大小进行排序: 小数部分越大的社区优先获得额外的1个名额. 按照该顺序依次补齐, 直至所有剩余名额分配完毕. 最终, 社区$ C_i $获得的实际免疫预算记为$ K_i $, 其中$ i=1, 2, \cdots, L $.

在完成预算分配后, 需要进一步识别各社区内部对传播具有较高影响力的节点. 为此, 综合引入三类中心性指标, 从多维结构特征出发刻画节点的重要性, 为后续候选池构建提供可靠依据.

1) 度中心性(degree centrality, DC)用于衡量节点的潜在传播覆盖范围, 定义为该节点在超图中所连接的邻居节点数量. 邻居越多, 节点在传播早期能够触及的对象越广, 其潜在影响力也随之增加.

2) 超度中心性(hyper degree centrality, HDC)用于衡量节点在超图中的参与活跃度. 节点$ v_i $的超度可写为

超度越高, 意味着节点出现在更多的群体交互事件中, 从而在传播过程中具有更高的被激活概率.

3) 介数中心性(betweenness centrality, BC)用于刻画节点在超图最短路径结构中的桥接作用, 其定义为

其中, $ \sigma_{st}^{{\cal{H}}} $表示从节点$ v_s $到节点$ v_t $的最短路径条数, $ \sigma_{st}^{{\cal{H}}}(v_i) $表示其中经过节点$ v_i $的最短路径条数. 介数中心性较高的节点通常在跨社区或长程传播链路中发挥重要的中介作用^[27].

基于上述三类中心性指标, 算法分别从对应的排序结果中提取排名前P的节点作为候选节点. 在实际实现中, P的取值需严格大于等于免疫节点数K, 以确保候选池规模充分并在社区划分及预算分配后为各社区保留足够的可选节点. 记$ {\cal{N}}_{{\mathrm{DC}}} $, $ {\cal{N}}_{{\mathrm{HDC}}} $与$ {\cal{N}}_{{\mathrm{BC}}} $分别表示依据度中心性、超度中心性和介数中心性选出的前P个节点集合, 则全局候选集可定义为

为了支持社区级别的精细化免疫节点选取, 对每个社区$ C_i $构造其局部候选集:

随后, 蚁群在生成免疫解的过程中, 将依据各社区的预算配额$ K_i $, 在对应的局部候选集$ {\cal{N}}_i $中选择节点, 以满足社区内部的资源约束并提升解的结构均衡性.

HACO的核心机制是基于蚁群算法的迭代式优化循环. 设最大迭代轮数为T, 在每一代中, 蚂蚁根据当前的信息素分布构建候选免疫解, 并在SIR-CP传播模型下执行模拟以评估其适应度. 随后, 算法依据解的优劣对节点级信息素进行强化或削弱, 同时施加挥发与随机扰动, 以实现全局探索能力与局部开发能力之间的动态权衡. 围绕该迭代框架, 算法依次完成四个关键环节: 1)免疫解初始化, 通过随机化生成初始解以覆盖多样化搜索空间; 2)适应度评估, 基于传播模拟结果和综合性能指标定量衡量免疫策略的有效性; 3)信息素更新, 按照免疫解表现对关键节点进行差异化强化, 引导搜索收敛方向; 4)优化调节机制, 结合信息素挥发与扰动, 在更新后的分布上重构候选解, 促使算法逐渐趋向最优免疫策略$ S^* $.

在初始化阶段, 每只蚂蚁均对应一个完整的免疫方案. 为保持解的多样性, 设置总的蚂蚁数量为n, 其中第j只蚂蚁的免疫解表示为节点集合

在初始迭代中, 所有候选节点的信息素均被赋予统一的初始值$ \tau_0 = 0.001 $. 随后, 为构建每个蚂蚁的初始解, 在每个社区$ C_i $内从其节点集$ {\cal{N}}_i $中随机抽取$ K_i $个节点, 并将来自所有社区的抽取结果合并, 从而形成规模为K的免疫集合$ S_j $.

在评估阶段, 免疫策略$ S_j $的有效性通过SIR-CP模型进行仿真检验. 具体流程如下: 首先, 将所有未被免疫的节点逐一作为初始感染源; 随后在设定的感染率β和恢复率γ下运行传播过程. 为降低随机波动的影响, 每个初始感染源独立重复仿真$ R=50 $次, 并对结果取平均. 依据所有可能的初始感染源, 可得到该免疫策略的平均传播峰值:

其中, $ I_{{\rm{peak}}, r}(v, S_j) $表示在第r次独立仿真中, 以节点v为初始感染源、并采用免疫策略$ S_j $时所产生的传播峰值. 较小的$ I_{{\mathrm{peak}}}(S_j) $表明该免疫方案能够更有效地抑制传播规模. 在此基础上, 为更全面地衡量免疫解的优劣, 进一步构建了由三项指标组成的综合适应度函数, 用于反映传播抑制能力、结构覆盖特性与策略稳健性等方面的表现.

首先, 引入免疫效率$ \eta_{{\rm{im}}} $用于衡量在给定免疫预算下策略对传播过程的绝对抑制能力, 其定义为

该指标取值越接近1, 表示在理论可感染节点范围内实现的传播峰值越低, 即免疫方案在绝对意义上的抑制效果越强.

其次, 引入相对竞争表现$ \eta_{{\rm{re}}} $, 用于刻画当前免疫策略在当代蚂蚁种群中的相对表现水平:

其中$ k \in \{1, 2, \cdots, n\} $为蚂蚁的索引, $ \max\nolimits_{k} I_{{\mathrm{peak}}}(S_k) $和$ \min\nolimits_{k} I_{{\mathrm{peak}}}(S_k) $分别表示本轮迭代中所有免疫策略的最大与最小传播峰值. 该指标通过归一化区分策略之间的性能差异, 使表现优异的解获得更高得分, 从而推动搜索过程逐步向传播峰值更低的策略收敛^[28].

最后, 考虑到蚁群算法的迭代特性, 引入历史进步奖励$ \eta_{{\rm{pr}}} $用于衡量当前解相较于历史最优解的改进幅度, 其定义为

其中, $ \Delta I_j = I_{{\mathrm{peak}}}^{{\rm{best}}} - I_{{\mathrm{peak}}}(S_j) $表示当前免疫策略在传播峰值方面相对于历史最优策略的改进量, $ I_{{\mathrm{peak}}}^{{\rm{best}}} $为截至当前迭代已获得的最小传播峰值. 在每轮迭代结束后, 若当代出现更小的$ I_{{\mathrm{peak}}}(S_j) $, 则相应更新$ I_{{\mathrm{peak}}}^{{\rm{best}}}=I_{{\mathrm{peak}}}(S_j) $. 该奖励项能够在取得改进时提供额外增益, 同时动态调整历史最优基准, 从而促进算法持续探索潜在更优解并提升收敛效率.

综合上述三项指标, 可将免疫策略的最终适应度定义为

其中$ w_1 = 0.5,\; w_2 = 0.25,\; w_3 = 0.25 $^[29]. 该权重设置突出免疫效率在抑制传播中的主导作用, 同时兼顾群体内部的相对竞争表现和迭代过程中取得的动态改进, 使适应度评估在绝对有效性、相对排名和历史进步三方面实现合理平衡.

在学习阶段, 算法根据适应度结果对各节点的信息素水平进行更新. 首先计算节点v的信息素增量$ \Delta \tau_v(t) $, 其由所有包含该节点的蚂蚁解的适应度值累计得到:

其中, $ F(S_j^{(t)}) $表示在第t次迭代中由蚂蚁j构造的解$ S_j^{(t)} $的适应度值. 该累计方式意味着: 节点v越频繁地出现在高质量解中, 则其获得的增量越大, 从而在后续迭代中被选中的概率更高.

随后, 对节点v的信息素进行更新:

其中, $ \tau_v(t) $为第$ t-1 $次迭代结束时节点v的信息素水平, $ \tau_v'(t) $为根据信息素增量更新后的中间值.

在优化阶段, 信息素在增量更新后进一步通过挥发与扰动机制进行动态调节. 首先施加时变挥发操作:

其中$ \tau_v''(t) $表示挥发后的信息素水平, 挥发系数$ \rho(t) $定义为

其值随迭代次数增加逐渐减小. 较大的初期挥发率有助于降低过早收敛至局部最优的风险, 而较小的后期挥发率能够强化优质路径并加速整体收敛^[21].

随后, 在每轮迭代中以概率$ p_{{\rm{perturb}}} = 0.1 $对部分节点施加随机扰动:

其中$ U(-0.1, 0.1) $为区间$ [-0.1, 0.1] $上的均匀分布. 该扰动机制在保留优质解的基础上引入轻微随机变化, 有助于维持搜索多样性、避免陷入局部最优并提升全局探索能力.

在完成信息素的更新、挥发与扰动操作后, 算法依据新的信息素分布为下一代蚂蚁构造解. 设社区集合为$ {\cal{C}} $, 其中每个社区$ C_i \in {\cal{C}} $对应局部候选集$ {\cal{N}}_i $及免疫预算$ K_i $. 在第t轮迭代中, 对于种群中任意一只蚂蚁j, 算法按社区顺序依次选取免疫节点: 在社区$ C_i $内, 每次选点以概率$ p_{{\rm{greedy}}}(t) $执行贪婪策略, 即从候选集$ {\cal{N}}_i $中选择当前信息素强度最大的节点$ v_i^*(t) $; 若不采用贪婪策略, 则以概率$ 1 - p_{{\rm{greedy}}}(t) $按信息素权重在候选集中随机选择节点. 具体而言, 对于任意候选节点$ v \in {\cal{N}}_i $, 其在第t轮被选为$ v \in {\cal{N}}_i $的概率定义为

其中$ p\left(v_i^*(t) = v\right) $表示节点v在迭代t时刻被选中的概率.

贪婪概率$ p_{{\rm{greedy}}}(t) $随迭代过程逐步提升, 其分段定义如下:

其中, T为最大迭代次数. 此设置使算法在早期阶段保持更强的探索性, 避免陷入局部最优; 随着迭代推进, 逐渐增加对高质量节点的利用, 从而提升搜索效率并加速收敛^[21].

上述选点过程在社区$ C_i $内重复执行, 直至选出$ K_i $个互不重复的节点. 最终, 将所有社区所选节点的并集作为蚂蚁j在下一代的免疫解$ S_j^{(t+1)} $. 种群中全部蚂蚁完成构造后, 即可形成本轮迭代的解集合, 用于随后的适应度评估与信息素更新.

本节从四个方面开展实验评估: 数据集、基线方法、参数敏感性分析与免疫效果比较. 所有实验均基于真实超图数据集进行, 并与多类具有代表性的基线方法进行系统对比, 以全面验证所提策略的有效性与稳健性.

实验选取四个公开的真实超图数据集用于验证所提方法的有效性, 分别为Algebra, Restaurants-Rev, Geometry和Bars-Rev. 上述数据集来源于实际复杂系统, 能够真实地反映多主体之间的高阶交互特性. 表 1汇总了主要统计信息, 其中N为节点数量, M为超边数量, $ \langle k^{\mathrm{E}} \rangle $表示平均超边规模, $ k^{\mathrm{E}}_{{\mathrm{m}}} $表示最大超边规模, $ \langle k^{\mathrm{H}} \rangle $为平均节点超度, $ k^{\mathrm{H}}_{{\mathrm{m}}} $为最大节点超度.

Algebra　该数据集源于MathOverflow平台, 包含与代数主题相关的问答交互. 节点表示用户, 超边由在同一时间窗口内回答同类型代数问题的用户构成^[30].

Restaurants-Rev　该数据集来自Yelp平台, 反映用户在餐饮场景下的评论行为. 节点对应用户, 超边由在给定时间窗口内评价同类别餐厅的用户组成^[30].

Geometry　同样采集自MathOverflow平台, 涵盖几何主题的问答互动. 节点表示用户, 超边代表在相同时间窗口内回答同类型几何问题的用户集合^[30].

Bars-Rev　该数据集同样来自Yelp平台, 记录用户在酒吧场景中的评论活动. 节点表示用户, 超边由在同一时间窗口内点评同类别酒吧的用户形成^[30].

为了验证HACO的有效性, 将其与六个基线方法进行对比, 其中度中心性(DC)、超度中心性(HDC)以及介数中心性(BC)的介绍见3.2.3节, 本节将介绍其他几种基线算法, 具体如下.

接近中心性(closeness centrality, CC)^[31]: 反映节点与其他节点的平均距离, 定义为

其中$ d_{ij} $表示节点$ v_i $与$ v_j $之间的最短路径距离. 算法选择$ {\mathrm{CC}} $值最大的前K个节点进行免疫.

模拟退火(simulated annealing, SA)^[10]: 该方法通过构造能量函数来刻画免疫策略的效果, 可定义为感染峰值:

其中S表示免疫节点集合. 若新解$ S' $的能量更低($ \Delta E = E(S') - E(S) \lt 0 $), 则接受该解, 若能量更高, 则以如下概率接受该解,

其中$\varTheta $为温度参数. 随着迭代过程推进, 温度逐渐降低, 从而实现对解空间的全局搜索与局部收敛. 整个退火过程中记录出现的能量最小的解$ S^* $, 并将其作为最终的免疫节点集合.

重建方法(reconstruction method, RM)^[12]: 该方法首先从渗流视角出发, 识别并剔除对最大连通分量规模影响有限的边缘节点, 从而获得精简后的候选节点集合$ {\cal{N}}_{\mathrm{C}} $. 在此基础上, RM方法在每轮迭代中选择$ {\cal{N}}_{\mathrm{C}} $中最能显著缩减最大连通分量规模的节点. 设$ {\rm{GCC}}_{{\rm{before}}} $为当前网络的最大连通分量规模, $ {\rm{GCC}}_{{\rm{after}}}(v) $表示移除候选节点v及其相关超边后得到的最大连通分量规模, 则对每个$ v \in {\cal{N}}_{\mathrm{C}} $定义:

在每一轮迭代中, 选取使$ \varDelta(v) $达到最大值的节点并将其加入免疫集合, 同时更新网络结构与候选节点集. 上述过程循环执行, 直至免疫节点数达到预设的预算上限.

为确保评估过程的一致性与可复现性, 四个真实超图数据集均采用统一的实验设置. 免疫节点数量K依次取5, 10, 15, 20, 25, 30六组不同取值. 对于任一免疫策略及其对应的免疫集合S, 将网络中所有非免疫节点逐一视作独立的初始感染源, 并基于SIR-CP模型进行传播仿真. 参考SIR-CP模型相关研究中的典型参数配置, 传播参数设定为固定恢复率$ \gamma = 0.10 $, 感染率取$ \beta \in \{0.06, 0.08, 0.10\} $^[17]. 在每个$ (\beta, \gamma, K) $组合下, 对每个初始感染节点独立运行$ R = 50 $次仿真并取平均值; 随后对所有初始感染节点的结果再次求平均, 以获得该免疫策略在当前参数配置下的平均感染峰值.

在HACO算法及候选集降维方面, 如不特别说明, 社区数量固定为$ L = 4 $, 候选池规模设为$ P = 1.3 K $, 蚂蚁数量设置为$ n = \lceil 1.5 K \rceil $, 信息素初始浓度$ \tau_0 = 0.001 $. 上述参数设置在所有数据集及不同感染率条件下保持一致, 并据此对HACO及全部基线方法进行系统评测.

在本节中, 参数分析部分将重点评估社区数量L与候选池规模P的敏感性, 展示不同参数配置下算法性能的变化趋势. 免疫效果分析部分则对HACO与各基线方法在不同数据集上的表现进行系统比较, 以检验算法在多场景下的稳健性与优势. 其中平均感染峰值作为主要评价指标, 数值越低表示传播抑制越充分, 免疫效果越好.

为系统评估HACO对关键超参数的敏感性, 分别考察社区数量L与候选池规模P对算法性能的影响. 所有实验均在四个真实超图数据集上开展, 本部分所有实验固定感染率$ \beta=0.10 $和恢复率$ \gamma=0.10 $.

为系统评估社区划分数量L对HACO算法性能的影响, 本文针对不同免疫预算$ K \in \{10, 20, 30\} $, 系统考察$ L \in \{3, 4, 5, 6, 7, 8\} $情况下平均感染峰值的变化, 实验结果如图 3所示. 结果表明, Algebra数据集在$ L=5 $时取得最优免疫效果, 而Restaurants-Rev, Geometry及Bars-Rev三个数据集则在$ L=4 $时表现最为稳定且感染峰值最低. 进一步观察发现, 当社区数量超过其对应的最优取值后, 各数据集的平均感染峰值均出现不同程度的增长. 这一现象表明, 过度细化的社区划分可能破坏超图中原有的紧密结构特征, 使有限的免疫资源被分散配置到多个子社区中, 从而削弱算法对关键传播区域的针对性防御能力. 鉴于上述四个真实超图数据集均未提供可供参考的真实社区标签规模, 为在保证算法鲁棒性与参数一致性的前提下开展后续实验, 本文统一采用$ L=4 $作为默认的社区划分数量配置.

为系统评估候选池规模P对HACO算法性能的影响, 本文针对不同免疫预算水平$ K \in \{10, 20, 30\} $, 将候选池规模设置为$ P \in \{K, 1.3 K, 1.5 K, 1.8 K, 2 K\} $, 并分析其对平均感染峰值的影响, 实验结果如图 4所示. 从结果可以观察到, 四个数据集在不同P取值下呈现出高度一致的变化规律: 当P由K增加到$ 1.3 K $时, 平均感染峰值显著降低, 免疫效果整体得到明显改善. 这表明在保持搜索空间可控的前提下, 适度扩展候选池有助于提升算法的探索能力, 使潜在优质节点更容易被纳入搜索过程并获得强化. 然而, 当P进一步增大至$ 1.5 K $及以上时, 免疫效果开始逐步减弱, 且在$ P=1.8 K $和$ P=2 K $时性能下降尤为明显. 这一现象主要源于候选节点数量过多会削弱信息素分布的判别性, 使搜索过程在有限迭代次数内趋于分散, 难以集中强化关键节点, 从而降低算法逼近高质量免疫解的效率. 综合上述分析可知, $ P=1.3 K $在四个数据集和不同免疫预算条件下均表现出稳定且优越的免疫效果. 因此, 后续实验中统一采用$ P=1.3 K $作为默认参数配置.

本文在四个真实超图数据集上对HACO与多种基线方法的免疫性能进行了系统对比, 实验结果如图 5所示. 所有实验均采用默认参数设置$ L=4, P=1.3 K $, 并在不同传播强度条件下进行评估, 其中感染率取$ \beta \in \{0.06, 0.08, 0.10\} $, 恢复率固定为$ \gamma=0.10 $.

实验结果表明, 在四个数据集及三种感染率设置下, HACO始终能够实现最低的平均感染峰值比例, 整体性能稳定优于所有对比方法. 相较于表现最优的基准方法, HACO在Restaurants-Rev, Algebral Geometry和Bars-Rev数据集上的平均感染峰值分别进一步降低了5.25%, 4.12%, 3.86%和2.41%. 从算法的内在机制来看, 传统中心性方法多依赖节点的拓扑指标, 在具有社团结构的网络中易因候选节点空间分布较为聚集而产生免疫冗余; 重建方法(RM)侧重于破坏静态连通性, 对超图动态传播过程的刻画较为有限; 模拟退火(SA)算法在处理超图免疫这类高维组合优化问题时, 通常面临搜索效率与解质量之间的平衡挑战. 相比之下, HACO通过社区划分引入结构约束并结合自适应启发式搜索, 降低了搜索空间的盲目性, 使其能够兼顾社区内部核心节点与跨社区的连接节点, 从而在相同的免疫预算下实现了更有效的传播阻断.

进一步观察发现, 随着免疫节点数量的增加, HACO的免疫效果提升速度明显快于其他方法, 体现出其在免疫资源受限场景下更为突出的传播控制效率. 从机制上看, 在具有显著社团结构的超图中, 社区划分能够将全局免疫优化问题分解为多个社区内并行的抑制子任务, 并依据社区规模合理分配免疫预算, 从而避免在高密度区域对同类节点的冗余免疫. 同时, 自适应蚁群搜索策略在候选池中优先覆盖社区内部的关键传播节点, 使得算法在不同传播强度与网络形态下均能保持稳定的抑制效果, 并更快推动系统接近群体免疫状态, 从而有效降低大规模传播发生的风险.

本文进一步对HACO的时间复杂度进行分析. 算法的计算开销主要由预处理阶段和迭代优化阶段两部分构成. 在预处理阶段, 需要基于团扩张策略计算介数中心性, 其时间复杂度为$ O(N M \langle k^{\mathrm{E}} \rangle^2) $, 其中$ \langle k^{\mathrm{E}} \rangle $表示平均超边规模. 迭代优化阶段的计算开销主要在于适应度评估过程. 如果蚁群规模为n, 最大迭代次数为T, 由于每次评估需要遍历网络中所有的非免疫节点作为初始感染源进行SIR-CP仿真, 该阶段的时间复杂度为$ O(T n N M \langle k^{\mathrm{E}} \rangle) $. 综上所述, HACO算法的总体时间复杂度为$ O(NM \langle k^{\mathrm{E}} \rangle^2 + T n N M \langle k^{\mathrm{E}} \rangle) $.

针对高阶交互在真实传播过程中所起的主导作用, 本文在超图建模框架下提出了一种结合社区划分与自适应蚁群优化的免疫策略HACO. 与直接在全局空间进行优化不同, HACO首先从整体结构层面识别超图中的社区, 并依据社区规模对免疫资源进行初始配置, 从而在问题建模阶段引入结构约束, 降低搜索的无效性. 随后, 通过多指标联合筛选构建候选节点集合, 将优化过程聚焦于潜在传播影响力较高的节点子空间, 使后续搜索能够在保持覆盖性的同时显著压缩计算复杂度. 在此基础上, 自适应蚁群算法通过信息素积累、挥发与扰动机制不断修正搜索偏好, 使免疫解在探索与利用之间实现动态平衡, 并逐步收敛至高质量方案^[32,33].

实验结果表明, 在四个真实超图数据集及不同感染率设定下, HACO均能够稳定地将平均感染峰值压制至最低水平, 整体性能显著优于对比方法. 尤其是在免疫资源逐步增加的过程中, HACO所对应的感染峰值下降幅度更为显著. 这一优势并非仅来源于优化策略本身, 而是与超图中普遍存在的社团传播机制密切相关. 具有明显社区结构的高阶网络通常表现为社区内部传播迅速而跨社区扩散相对滞后的特征, 若忽略这一结构特性, 免疫节点往往集中于少数高密区域, 难以同步抑制多个潜在爆发点. HACO通过在社区尺度上分配预算, 并在候选池内执行自适应搜索, 使免疫策略能够同时覆盖不同社区内的关键传播核心, 并逐步触及跨社区的关键连接位置, 从而在不同传播强度与网络形态下保持一致且稳健的抑制效果.

在此基础上, 本文也明确了当前工作的适用范围与后续拓展方向. 首先, 现有模型以静态超图为研究对象, 而现实中的高阶交互关系往往随时间演化, 未来可将HACO推广至时序超图框架, 研究在结构动态变化条件下免疫策略的在线更新与自适应调整问题^[34]. 其次, 候选节点筛选阶段目前仍依赖人工设计的中心性指标, 尽管具有良好的可解释性, 但在复杂场景中可能受限于表达能力, 后续可结合图神经网络或强化学习方法, 学习数据驱动的节点影响力表征, 以进一步提升搜索效率与免疫效果. 最后, 考虑到HACO的主要计算开销集中在候选免疫解的传播仿真评估环节, 且该类仿真在现有高性能计算与分布式框架下已广泛采用并行加速, 未来可将HACO进一步适配至相应并行环境, 并对传播仿真等关键耗时模块开展系统级优化, 以支撑其在大规模公共卫生防控和网络安全治理等实际场景中的应用^[35].

总体而言, HACO在超图免疫优化任务中展示了稳定且显著的性能优势, 表明将网络结构信息与自适应群体搜索机制相结合, 是应对高阶传播控制问题的一条有效路径. 本文提出的方法框架不仅为复杂系统中的传播抑制提供了可推广的技术方案, 也为理解结构感知干预策略在高阶网络中的作用机理提供了新的视角.