A Sample Reuse Strategy for Dynamic Influence Maximization Problem

Dynamic influence maximization problem (DIMP) aims to maintain a group of influential users within an evolving social network to maximize the influence scope at any given moment. A primary category of DIMP algorithms focuses on updating reverse reachable (RR) sets designed for static social network scenarios to accelerate the estimation of influence spread. The generation time of RR sets plays a crucial role in algorithm efficiency. However, their update approaches require sequential updates for each edge change, leading to considerable computational costs. In this paper, we propose a strategy for batch updating the changes in network edge weights to maintain RR sets efficiently. We retain those with a high probability by calculating the probability that previous RR sets can be regenerated at the current moment. This method can effectively avoid the computational cost of updating and sampling these RR sets. Besides, we propose a resampling strategy that generates high-probability RR sets to make the final distribution of RR sets approximate to the sampling probability distribution under the current social network. The experimental results indicate that our strategy is both scalable and efficient. On the one hand, compared to the previous update strategies, the running time of our approach is insensitive to the number of changes in network weight; on the other hand, for various RR set-based algorithms, our strategy can reduce the running time while maintaining the solution quality that is essentially consistent with the static algorithms.