Scalable Influence Estimation in Continuous-Time Diffusion Networks

By Nan Du, Le Song, Manuel Gomez-Rodriguez, Hongyuan Zha. 2013

271 citations recorded by the source corpus.

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 ε using n = O(1/ε2) randomizations and up to logarithmic factors O(n|ε|+n|V|) computations. When used as a subroutine in a greedy influence maximization approach, our proposed algorithm is guaranteed to find a set of C nodes 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.

Subfields: Computational Mathematics, Statistical and Nonlinear Physics, Graph Learning, Network Science & Complex Systems

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mathematics

  1. Eliav Buchnik
  2. Edith Cohen
  3. Bistra N. Dilkina
  4. Elias Boutros Khalil
  5. Le Song
  6. Bernhard Schölkopf
  7. Krishna P. Gummadi

In Statistical and Nonlinear Physics

  1. Bernhard Schölkopf
  2. Edith Cohen
  3. Eliav Buchnik
  4. Le Song
  5. Kian-Lee Tan
  6. Ju Fan
  7. Yuchen Li
  8. Yanhao Wang

In Graph Learning

  1. Eliav Buchnik
  2. Edith Cohen
  3. Bistra N. Dilkina
  4. Elias Boutros Khalil
  5. Le Song
  6. Manuel Gomez-Rodriguez
  7. My T. Thai
  8. Bernhard Schölkopf

In Network Science & Complex Systems

  1. Eliav Buchnik
  2. Edith Cohen
  3. Bernhard Schölkopf
  4. Bistra N. Dilkina
  5. Elias Boutros Khalil
  6. Le Song
  7. Nan Du
  8. Hanjun Dai

Citations in the corpus