Workshop on Algorithms and Models for the Web Graph (WAW) 2013
December 14, 2013 at Harvard University.
Talk on joint work with David F. Gleich:
We consider random-walk transition matrices from large social and information networks. For these matrices, we describe and evaluate a fast method to estimate one column of the matrix exponential. Our method runs in sublinear time on networks where the maximum degree grows doubly logarithmic with respect to the number of nodes. For collaboration networks with over 5 million edges, we find it runs in less than a second on a standard desktop machine.