A more scalable algorithm for Fair Influence Maximization with Concave Functions

The Influence Maximization (IM) problem seeks a set of seed nodes that maximizes information spread in a social network. While IM has found applications in several domains, such as viral marketing, advertisement, public health and political campaigns, its solutions often concentrate influence among a subset of demographic groups, raising fairness concerns. Fair Influence Maximization (FIM) addresses this issue by requiring that influence is spread equitably across all groups. In particular, the Concave Fairness Framework (CFF), based on the poverty-reward principle of prioritizing under-reached groups, provides a general approach to FIM. However, greedy algorithms needed for its realization require a large number of Monte Carlo simulations per step, making it impractical on large networks. We here focus on a continuous relaxation of CFF, and propose a scalable algorithm for it, called FIM-SPACE. Our method works with any concave fairness function admissible in the CFF, and its runtime scales independently of the number of Monte Carlo samples required by greedy methods. We provide theoretical guarantees on the approximation quality of our approach and experimentally show that pipage rounding of its fractional solution produces a discrete seed set whose fairness and influence are competitive with those returned by the greedy baseline. Our experiments show that FIM-SPACE achieves solution quality comparable to the greedy baseline on real-world social networks, while running up to $70\times$ faster. This means that on larger networks, where greedy methods become intractable, our approach remains able to return high-quality fair seed sets within reasonable time.