Scalable Influence Estimation in Continuous-Time Diffusion Networks
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 |E| edges to an accuracy of using n = O(1/ 2 ) randomizations and up to logarithmic factors O(n|E|+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.
Problem: Given a directed graph G compute the subset 
      of k vertices whose infections leads to the maximum number of nodes being 
      infected before time T, under the independent cascade model. The 
      paper builds heavily on top of the original paper on influence 
      maximization in continuous-time diffusion networks (Gomez-Rodriguez & 
      Scholkopf, ICML 2012). There are two pieces of cleverness that appear to 
      be unique to this paper: I. Reformulate continuous-time diffusion 
      networks in terms of independent variates on the edges. The basic 
      contribution of this paper seems to stem from the observation that a 
      continuous-time diffusion network can be converted from a distribution 
      over the contagion times for nodes (t_i) to a distribution over 
      transmission times between nodes (\tau_{ji}). Under the independent 
      cascade model, the transmission times between nodes are independent. 
      The independent cascade model is a strong assumption in practice, 
      but one the authors acknowledge freely. Have the authors considered 
      whether there are natural relaxations of the independent cascade model 
      which do not violate the independence of transmission times too much: 
      e.g., allow a node to be more receptive to contagion if a large number of 
      nodes, not necessarily direct parents, are contaminated. Such a relaxation 
      might help capture the effects of mass advertising in the viral marketing 
      problem. II. Estimating the objective using Cohen's algorithm 
      The second contribution of this paper is to show that the 
      objective can be reformulated as a neighborhood size estimation problem, 
      and that Cohen's randomized algorithm can be directly applied to estimate 
      the objective given sample data (Section 5). I was surprised that 
      the authors did not mention that Cohen's algorithm has been used before 
      for influence maximization, in a different setting (Chen et al, KDD 2009 : 
      Section 2). The authors cite the Chen paper in a laundry list of papers 
      which consider influence maximization, but neglect to mention how Chen et 
      al. use Cohen's algorithm to compute the transitive closure of a directed 
      graph to speed up a submodular influence maximization problem under a 
      weighted cascade model. I'll point out that Cohen's algorithm handles both 
      transitive closure and neighborhood counting on a directed graph. 
      I understand that continuous-time diffusion networks are a 
      different model from that of Chen et al., but its use in this paper is so 
      similar to that of Chen et al., it begs the question---is Section 5 a 
      totally novel use of Cohen's algorithm; or is it a novel reworking of an 
      idea used previously for influence maximization, to continuous-time 
      diffusion networks? General Comments: The paper does not 
      assume too much in the way of prior knowledge: the continuous-time 
      independent cascade model is explained (Section 2) as is submodular 
      influence maximization (Section 6). The material should be accessible to a 
      broad audience. The experimental results are quite compelling: 
      ConTinEst is vastly faster than the alternatives, and handles more general 
      models of transition time. Minor comments: L671: Typo 
      "Berstein's"