dIRIEr: Distributed Influence Maximization In Social Network

In this paper, for the first time, we tackle the scalability problem of Influence Maximization (IM) via distributed computing. First, we propose a distributed IM algorithm based on IRIE, one of the most state-of-the-art IM algorithms. Then an incremental updating method is proposed to reduce the overhead of repeated computation. Furthermore, based on some new insights, we redesign our algorithm with a strategy, which we call reservoir, to accumulate increments and delay exchange between machines. Experiments on real-world and synthetic networks show our redesigned algorithm, i.e. dIRIEr (distributed IRIE with Reservoir), reduces communication traffic dramatically and speeds up continuously as more machines are added in. dIRIEr can handle giant networks with hundreds of millions of nodes where centralized algorithms become infeasible.