Scalable Influence Estimation in Continuous-Time Diffusion Networks
This addresses the challenge of predicting information spread in large networks for applications like viral marketing or news dissemination, representing a strong specific gain rather than a foundational breakthrough.
The paper tackles the problem of scalable influence estimation in continuous-time diffusion networks, proposing a randomized algorithm that achieves an accuracy of ε with O(1/ε²) randomizations and O(n|E|+n|V|) computations, and when used in greedy influence maximization, it guarantees a set of nodes with influence at least (1-1/e)OPT-2ε, scaling to millions of nodes in experiments.
If a piece of information is released from a media site, can it spread, in 1 month, to a million web pages? This influence estimation problem is very challenging since both the time-sensitive nature of the problem and the issue 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 |E| edges to an accuracy of $\varepsilon$ using $n=O(1/\varepsilon^2)$ randomizations and up to logarithmic factors O(n|E|+n|V|) computations. When used as a subroutine in a greedy influence maximization algorithm, our proposed method is guaranteed to find a set of nodes with an influence of at least (1-1/e)OPT-2$\varepsilon$, where OPT is the optimal value. Experiments on both synthetic and real-world data show that the proposed method 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.