Efficient Algorithm for Budgeted Adaptive Influence Maximization: An Incremental RR-set Update Approach
Open Access
- 13 November 2023
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Management of Data
- Vol. 1 (3) , 1-26
Abstract
Given a graph G, a cost associated with each node, and a budget B, the budgeted influence maximization (BIM) aims to find the optimal set S of seed nodes that maximizes the influence among all possible sets such that the total cost of nodes in S is no larger than B. Existing solutions mainly follow the non-adaptive idea, i.e., determining all the seeds before observing any actual diffusion. Due to the absence of actual diffusion information, they may result in unsatisfactory influence spread. Motivated by the limitation of existing solutions, in this paper, we make the first attempt to solve the BIM problem under the adaptive setting, where seed nodes are iteratively selected after observing the diffusion result of the previous seeds. We design the first practical algorithm which achieves an expected approximation guarantee by probabilistically adopting a cost-aware greedy idea or a single influential node. Further, we develop an optimized version to improve its practical performance in terms of influence spread. Besides, the scalability issues of the adaptive IM-related problems still remain open. It is because they usually involve multiple rounds (e.g., equal to the number of seeds) and in each round, they have to construct sufficient new reverse-reachable set (RR-set) samples such that the claimed approximation guarantee can actually hold. However, this incurs prohibitive computation, imposing limitations on real applications. To solve this dilemma, we propose an incremental update approach. Specifically, it maintains extra construction information when building RR-sets, and then it can quickly correct a problematic RR-set from the very step where it is first affected. As a result, we recycle the RR-sets at a small computational cost, while still providing correctness guarantee. Finally, extensive experiments on large-scale real graphs demonstrate the superiority of our algorithms over baselines in terms of both influence spread and running time.Keywords
Funding Information
- National Natural Science Foundation of China (No. U1936205)
- Hong Kong RGC CRF grant (No. C4158-20G)
- Hong Kong RGC GRF grant (No. 14217322)
- Hong Kong RGC ECS Grant (No. 24203419)
- Hong Kong ITC ITF grant (No. MRP/071/20X)
- Hong Kong ITC RTH Grant (No. PiH/012/22)
This publication has 37 references indexed in Scilit:
- Influence Maximization in Near-Linear Time2015
- Influence maximization2014
- Balanced Seed Selection for Budgeted Influence Maximization in Social Networks2014
- Maximizing Social Influence in Nearly Optimal Time2013
- Fast algorithms for maximizing submodular functions2013
- Scalable influence maximization for prevalent viral marketing in large-scale social networks2010
- Competitive Influence Maximization in Social Networks2007
- Maximizing the spread of influence through a social network2003
- Mining the network value of customers2001
- The budgeted maximum coverage problemInformation Processing Letters, 1999