A Fast Relaxation Method for Computing a Column of the Matrix Exponential of Stochastic Matrices from Large, Sparse Networks

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. This updated version proves that the algorithm runs in sublinear time on graphs with a power law degree distribution with exponent $p=1$ and max degree bounded by $n^r$ for any $r <1$.