Robust Fair Influence Maximization under Multiple Community Partitions

Fair Influence Maximization (FIM) is an important extension of the Influence Maximization (IM) problem that incorporates community-level fairness constraints. Most existing FIM formulations assume a given community partition P and a fairness parameter α , which governs the trade-off between influence spread and fairness. However, real-world social networks seldom admit a unique, ideal partition that captures community structures accurately. To handle the diversity of community partitions and fairness parameter settings in FIM, we propose the Robust Fair Influence Maximization (RFIM) problem. Given a set of partitions 𝒫 and corresponding fairness parameters, RFIM aims to maximize the worst-case ratio between the achieved fair influence objective and the optimal value attainable under each individual partition. We show that RFIM is hard to approximate within any constant factor, even when the seed budget is allowed to exceed the original limit by up to a logarithmic threshold. Fortunately, further surpassing this threshold enables a (1 - 1/e, ln|𝒫 | + 𝒪 (1)) bicriteria approximation via the Submodular Saturation framework proposed by Krause et al. Combining this framework with the Hit-and-Stop (HIST) algorithm, we propose Saturate-HIST (S-HIST), a tailored algorithm for RFIM that achieves a (1 - 1/e - ε/𝒪PT)-approximation with high probability in a bicriteria sense. To improve the efficiency of S-HIST, we further develop a subroutine algorithm, Saturated Generalized HIST (SG-HIST), tailored for its core procedure of maximizing a truncated fair influence objective under a saturated seed budget. We extensively evaluate the performance and scalability of S-HIST on both real-world and synthetic datasets. The experimental results demonstrate that our algorithm consistently achieves robust and competitive performance across diverse datasets and community partitions compared to baseline methods.