title: Scalable Influence Estimation in Continuous-Time Diffusion Networks.
abstract: If a piece of information is released from a media site, can we predict whether it may spread to one million web pages, in a month ? This influence estimation problem is very challenging since both the time-sensitive nature of the task and the requirement of scalability need to be addressed simultaneously. In this paper, we propose a randomized algorithm for influence estimation in continuous-time diffusion networks. Our algorithm can estimate the influence of every node in a network with |V| nodes and |ε| edges to an accuracy ofεusingn=O(1/ε2) randomizations and up to logarithmic factorsO(n|ε|+n|V|) computations. When used as a subroutine in a greedy influence maximization approach, our proposed algorithm is guaranteed to find a set ofCnodes with the influence of at least (1 - 1/e) OPT - 2Cε, where OPT is the optimal value. Experiments on both synthetic and real-world data show that the proposed algorithm can easily scale up to networks of millions of nodes while significantly improves over previous state-of-the-arts in terms of the accuracy of the estimated influence and the quality of the selected nodes in maximizing the influence.
authors.affiliation: Georgia Institute of Technology.
authors.forename: Nan
authors.initials: N
authors.lastname: Du
authors.affiliation: Georgia Institute of Technology.
authors.forename: Le
authors.initials: L
authors.lastname: Song
authors.affiliation: MPI for Intelligent Systems.
authors.forename: Manuel
authors.initials: M
authors.lastname: Gomez-Rodriguez
authors.affiliation: Georgia Institute of Technology.
authors.forename: Hongyuan
authors.initials: H
authors.lastname: Zha