時間制約付き敵対的影響遮断最大化

arXiv:2511.16068v2 Announce Type: replace-cross 要旨：敵対的影響遮断最大化 (AIBM) は、既知の負のセードノードとの同期伝播を行うために、正のセードノードの集合を選択することを目的とする。多くの AIBM の応用シナリオにおいて時間因子は特に重要な役割を果たす。しかし、時間制約を持つ AIBM 問題は未解決となっている。さらに、既存の AIBM 研究は目的関数の準凸性を十分に調査しておらず、理論的な近似的保証を確立していなかった。これらの課題に対処するために、まず、時間制約を明示的に考慮する時間制約付き敵対的影響遮断最大化 (TC-AIBM) を確立した。次に、3 つ異なる引き分けルールの下で TC-AIBM の目的関数の準凸性について理論的な証明を提供した。最後に、TC-AIBM 問題を解決する双方向影響サンプリング (BIS) アルゴリズムを提案した。目的関数の単調性と準凸性を活用して、BIS は近似的保証 $(1-1/e-\epsilon)(1-\psi)$ を達成する。4 つのリアルワールドデータセットにおける包括的な実験では、提案された BIS アルゴリズムは、さまざまな負のセード、時間制約、および引き分けルールにおいて卓越する頑健性を示し、最先端のベースラインを優越することが示された。また、BIS は貪欲アルゴリズムに比べて最大 3 桁の高速性を持つことが確認された。

arXiv:2511.16068v2 Announce Type: replace-cross Abstract: Adversarial Influence Blocking Maximization (AIBM) aims to select a set of positive seed nodes that propagate synchronously with the known negative seed nodes to counteract their negative influence. Time factor plays a particularly vital role for many AIBM application scenarios. However, the AIBM problem with time constraint remains unexplored. More importantly, existing AIBM studies have not thoroughly investigated the submodularity of the objective function, thereby failing to establish a theoretical approximation guarantee. To address these challenges, firstly, we establish the Time-Critical Adversarial Influence Blocking Maximization (TC-AIBM), which explicitly incorporates time constraint. Then, we provide a theoretical proof of the submodularity of the TC-AIBM objective function under three different tie-breaking rules. Finally, a Bidirectional Influence Sampling (BIS) algorithm is proposed to solve the TC-AIBM problem. Leveraging the monotonicity and submodularity of the objective function, BIS achieves an approximation guarantee of $(1-1/e-\epsilon)(1-\psi)$. Comprehensive experiments on four real-world datasets demonstrate that the proposed BIS algorithm exhibits excellent robustness across various negative seeds, time constraint, and tie-breaking rules, outperforming state-of-the-art baselines. In addition, BIS is up to three orders of magnitude faster than the Greedy algorithm.