  The heat kernel is a particular type of graph diffusion that, like the
much-used personalized PageRank diffusion, is useful in identifying a community
nearby a starting seed node. We present the first deterministic, local
algorithm to compute this diffusion and use that algorithm to study the
communities that it produces. Our algorithm is formally a relaxation method for
solving a linear system to estimate the matrix exponential in a degree-weighted
norm. We prove that this algorithm stays localized in a large graph and has a
worst-case constant runtime that depends only on the parameters of the
diffusion, not the size of the graph. Our experiments on real-world networks
indicate that the communities produced by this method have better conductance
than those produced by PageRank, although they take slightly longer to compute
on large graphs. On a real-world community identification task, the heat kernel
communities perform better than those from the PageRank diffusion.
