Influence Maximization with Fairness Cost on Groups in Online Social Networks
摘要
Motivated by applications in social influence and viral marketing, this work introduces the Influence Maximization with Cost Fairness on Groups ( \({\textsf{IMFC}}\) ) problem in social networks. Given a social network, a total budget, and a set of user groups, the goal is to identify a subset of users that maximizes influence spread while ensuring that the total cost within each group does not exceed its allocated budget. However, existing algorithms for influence maximization problems may not adapt to the problem or do not give any theoretical guarantees. To address the challenge, in this work we propose an efficient and scalable approximation algorithm that returns an approximation ratio of \(\frac{\alpha }{\alpha +2}-\epsilon \) and takes \(O((m+\log (\frac{n}{\epsilon }))\frac{n}{\epsilon ^2}(n \log n+\log (\frac{1}{\delta })))\) time complexity, where \(\alpha \) is the fairness ratio of cost, \(\epsilon , \delta \) are constants, n is the number of uses, and m is the number of links. Beyond theoretical guarantees, we conduct extensive experiments on real-world social networks. Our results demonstrate that the proposed algorithm not only achieves better influence spread but also runs faster than state-of-the-art methods.