Scalable Influence Estimation in Continuous-Time Diffusion NetworksScalable Influence Estimation in Continuous-Time Diffusion NetworksDu, Nan and Song, Le and Gomez-Rodriguez, Manuel and Zha, Hongyuan2013
Paper summarynipsreviewsThe paper addresses how to estimate and maximize influence in large networks, where influence of node (or set of nodes) A is the expected number of nodes that will eventually adopt a certain idea following the initial adoption by A. The authors develop an algorithm for estimating influence within a given time frame, then use it as the basis of a greedy algorithm to find a given number of nodes to (approximately) maximize influence within the given time frame. They present theoretical bounds and an experimental evaluation of the algorithm.
The authors build on an extensive list of existing work, which is appropriately cited. The most relevant is the work by Gomez-Rodriguez & Scholkopf (2012) \cite{conf/icml/Gomez-RodriguezS12}, which provides an exact analytical solution to the identical formulation of the influence estimation problem. The main innovation in the present paper is a fast randomized algorithm for estimating influence, which is based on the algorithm for estimating neighborhood size by Cohen (1997) \cite{journals/jcss/Cohen97}. This approximation allows more flexibility in modeling the flows through the edges, is substantially faster than the analytical solution, and scales well with network size. Overall, this is a solid paper on an important topic of practical relevance.
The paper addresses how to estimate and maximize influence in large networks, where influence of node (or set of nodes) A is the expected number of nodes that will eventually adopt a certain idea following the initial adoption by A. The authors develop an algorithm for estimating influence within a given time frame, then use it as the basis of a greedy algorithm to find a given number of nodes to (approximately) maximize influence within the given time frame. They present theoretical bounds and an experimental evaluation of the algorithm.
The authors build on an extensive list of existing work, which is appropriately cited. The most relevant is the work by Gomez-Rodriguez & Scholkopf (2012) \cite{conf/icml/Gomez-RodriguezS12}, which provides an exact analytical solution to the identical formulation of the influence estimation problem. The main innovation in the present paper is a fast randomized algorithm for estimating influence, which is based on the algorithm for estimating neighborhood size by Cohen (1997) \cite{journals/jcss/Cohen97}. This approximation allows more flexibility in modeling the flows through the edges, is substantially faster than the analytical solution, and scales well with network size. Overall, this is a solid paper on an important topic of practical relevance.