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
- Eliav Buchnik
- Edith Cohen
- Bistra N. Dilkina
- Elias Boutros Khalil
- Le Song
- Bernhard Schölkopf
- Krishna P. Gummadi
In Statistical and Nonlinear Physics
In Graph Learning
- Eliav Buchnik
- Edith Cohen
- Bistra N. Dilkina
- Elias Boutros Khalil
- Le Song
- Manuel Gomez-Rodriguez
- My T. Thai
- Bernhard Schölkopf
In Network Science & Complex Systems
- Eliav Buchnik
- Edith Cohen
- Bernhard Schölkopf
- Bistra N. Dilkina
- Elias Boutros Khalil
- Le Song
- Nan Du
- Hanjun Dai
Citations in the corpus
- Learning Combinatorial Optimization Algorithms over Graphs (2017, methodology): “[10] Du, Nan, Song, Le, Gomez-Rodriguez, Manuel, and Zha, Hongyuan.”
- Influence Maximization in Near-Linear Time: A Martingale Approach (2015, methodology): “[15] provide an analysis of ConTinEst’s accuracy guarantee, but do not formally discuss its time complexity.”
- Stop-and-Stare: Optimal Sampling Algorithms for Viral Marketing in Billion-scale Networks (2016, background): “Each edge (u, v) ∈ E is associated with a weight w(u, v) ∈ [0, 1] which indicates the probability that u influences v.”
- Quantifying Information Overload in Social Media and Its Impact on Social Contagions (2014, background): “While a large number of previous studies have focused on social contagions in on-line media (Du et al. 2013; Goel, Watts, and Goldstein 2012; Gomez-Rodriguez, Leskovec, and Krause 2010; Leskovec, Backstrom, and Kleinberg 2009), most ignore the impact of information overload on users’ forwarding…”
- Scalable diffusion-aware optimization of network topology (2014, methodology): “Can we compute the number of reachable nodes, r(v, T a X), efficiently, for all v in T a X? Fortunately, this problem has been extensively studied in the theoretical computer science literature as the neighborhood size-estimation problem [5], and was recently applied in the context of influence esti”
- Bootstrapped Graph Diffusions (2018, methodology): “Another class of graph diffusions, which we refer to here as social , were used for social and economic models of centrality [3, 4, 14, 18, 30, 34], influence [13, 17, 19, 23], and similarity [12] of nodes.”
- Influence Maximization on Social Graphs: A Survey (2018, methodology): “Then, [85], [86] introduce a FI-S KETCH based method adapting from SKIM [68] to efficiently evaluate the influence function with a provable guarantee.”
- Bootstrapped Graph Diffusions: Exposing the Power of Nonlinearity (2018, methodology): “reach diffusion) or the length (with distance diffusion) of edges [12, 13, 17, 19, 23] and then works with respective expectations.”
- Recurrent Marked Temporal Point Processes: Embedding Event History to Vector (2016, background): “More recently, the self-excitation point process [20], has become an ongoing hot topic for modeling the latent dynamics of information diffusion [16, 9, 10, 8, 40, 14, 22], online-user engagement [13], news-feed streams [7], and context-aware recommendations [11].”