Influence maximization based on reachability sketches in dynamic graphs

Influence maximization is the problem of selecting the most influential nodes in a given graph. The problem is applicable to viral marketing and is actively researched as social networks become the media of information propagation. To solve the challenges of influence maximization, previous works approximate the influence evaluations to reduce the running time and to simultaneously guarantee the quality of those evaluations. We propose a new influence maximization algorithm that overcomes the limitations of the state of the art algorithms. We also devise our algorithm to process update operations of dynamic graphs. Our algorithm outperforms the state of the art algorithms TIM+ and SKIM in running time, and its influence spread is also comparable to the others. Our experiments show that processing update operations is faster than executing baselines each time. Additional experiments with synthetic graphs show that the process preserves the quality of influence spread.