HotCSE Seminar
Computational Science & Engineering
Monday November 25, 12pm-1pm, 1116-E Klaus

Influence Estimation in Continuous-time Diffusion Networks

Nan Du
Advisor: Prof. Le Song


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 $|\Vcal|$ nodes and $|\Ecal|$ edges to an accuracy of $\epsilon$ using $n=O(1/\epsilon^2)$ randomizations and up to logarithmic factors $O(n|\Ecal|+n|\Vcal|)$ 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)\operatorname{OPT} - 2C\epsilon$, where $\operatorname{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.


Nan's research focuses on modeling diffusion of influence and information over large-scale social and information networks based on the confluence of the cutting-edge statistical machine learning and high-performance computing techniques, which has practical applications in many socialized online systems, including personalized advertising and recommendations.