TY - GEN
T1 - Reachability-Aware Fair Influence Maximization
AU - Ma, Wenyue
AU - Egger, Maximilian K.
AU - Pavlogiannis, Andreas
AU - Li, Yuchen
AU - Karras, Panagiotis
PY - 2024/8/28
Y1 - 2024/8/28
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=85203159586&partnerID=8YFLogxK
U2 - 10.1007/978-981-97-7238-4_22
DO - 10.1007/978-981-97-7238-4_22
M3 - Article in proceedings
SN - 978-981-97-7237-7
T3 - Lecture Notes in Computer Science
SP - 342
EP - 359
BT - Web and Big Data - 8th International Joint Conference, APWeb-WAIM 2024, Proceedings
A2 - Zhang, Wenjie
A2 - Yang, Zhengyi
A2 - Wang, Xiaoyang
A2 - Tung, Anthony
A2 - Zheng, Zhonglong
A2 - Guo, Hongjie
PB - BMJ, Springer Nature
CY - Singapore
ER -