Fairness-Aware Influence Maximization with Randomized Strategies: A Stochastic Frank-Wolfe Framework

The influence maximization problem seeks to identify a set of influential users in a social network to maximize the spread of information. While prior research has focused extensively on improving computational efficiency, it has largely overlooked fairness in information dissemination across different social groups. A widely adopted fairness criterion is the maximin objective, which aims to maximize the minimum influence received by any group. However, under this objective, the fairness-aware influence maximization problem is NP-hard even to approximate well. In this work, we consider randomized seed selection strategies for fairness-aware influence maximization to address this challenge. We introduce a noise-based smoothing technique to tackle the non-smoothness of the objective function, and develop an approximate solution based on the stochastic Frank-Wolfe algorithm. For efficient and theoretically grounded gradient estimation, we leverage the reverse influence sampling method, which enables provable gradient approximation. To obtain a discrete solution, we apply swap rounding to the fractional output, resulting in a randomized seed set that achieves a \ ( (1-1/e, 2) \) -approximation for monotone functions and a \ ( (1/e, 2) \) -approximation for non-monotone functions, with probability at least \ (1-\), where \ (\) and \ (\) are user-defined accuracy parameters. Although accurate gradient estimation typically requires a large number of samples and may incur a high computational cost, we further derive upper and lower bounds on the gradient estimates, and demonstrate that under certain conditions, using fewer samples still preserves the theoretical approximation guarantee. We validate our approach on six real-world social network datasets, and the results demonstrate that our algorithm effectively balances fairness and influence spread while maintaining strong performance.