Reachability-aware fair influence maximization

• Main Authors: MA, Wenyue, EGGER, Maximilian K., PAVLOGIANNIS, Andreas, LI, Yuchen, KARRAS, Panagiotis
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2024
• Subjects: Reachability-aware algorithm; Information dissemination; Artificial Intelligence and Robotics
• Online Access: https://ink.library.smu.edu.sg/sis_research/9723
• Institution: Singapore Management University

How can we ensure that an information dissemination campaign reaches every corner of society and also achieves high overall reach? The problem of maximizing the spread of influence over a social network has commonly been considered with an aggregate objective. Less attention has been paid to achieving equality of opportunity, reducing information barriers, and ensuring that everyone in the network has a fair chance to be reached. To that end, the fairness objective aims to maximize the minimum probability of reaching an individual. To address this inapproximable problem, past research has proposed heuristics, which, however, perform less well when the promotion budget is low and achieve fairness at the expense of overall welfare. In this paper, we propose novel reachability-aware algorithms for the fairness-oriented IM problem. Our experimental study shows that our algorithms outperform past work in challenging real-world problem instances by up to a factor of 4 in terms of the fairness objective and strike a balance between fairness and total welfare, even while no solution is universally superior across data, influence probability models, and propagation models.