Fair Influence Maximization in Social Networks: A Community-Based Evolutionary Algorithm
Kaicong Ma, Xinxiang Xu, Haipeng Yang, Renzhi Cao, Lei Zhang
Abstract
Influence maximization (IM) has been extensively studied in network science, which attempts to find a subset of users to maximize the influence spread. A new variant of IM, fair IM (FIM), which primarily enhances the fair propagation of information, has attracted increasing attention in academia. However, existing algorithms for FIM suffer from a trade-off between fairness and running time, as it is difficult to ensure that users are fairly influenced in terms of sensitive attributes, such as race or gender, while maintaining a high influence spread. To tackle this problem, herein, we propose an effective and efficient community-based evolutionary algorithm for FIM (named CEAFIM). In CEA-FIM, a community-based node selection strategy is proposed to identify potential nodes, which not only considers the size of the community but also the attributes of the nodes in the community. Subsequently, we designed an evolutionary algorithm based on the proposed node selection strategy to hasten the solution search, including the novel initialization, crossover, and mutation strategies. We validated the proposed algorithm by performing experiments on real-world and synthetic networks. The experimental results show that the proposed CEA-FIM achieves a better balance between effectiveness and efficiency than state-of-the-art methods do.