Diffusion and consensus on weakly connected directed graphs

Let G be a weakly connected directed graph with asymmetric graph Laplacian cal L. Consensus and diffusion are dual dynamical processes defined on G by dot x=-cal Lx for consensus and dot p=-pcal L for diffusion. We consider both these processes as well their discrete time analogues. We define a basis of row vectors bar γii=1k of the left null-space of cal L and a basis of column vectors γii=1k of the right null-space of cal L in terms of the partition of G into strongly connected components. This allows for complete characterization of the asymptotic behavior of both diffusion and consensus --- discrete and continuous --- in terms of these eigenvectors. As an application of these ideas, we present a treatment of the pagerank algorithm that is dual to the usual one. We further show that the teleporting feature usually included in the algorithm is not strictly necessary. This is a complete and self-contained treatment of the asymptotics of consensus and diffusion on digraphs. Many of the ideas presented here can be found scattered in the literature, though mostly outside mainstream mathematics and not always with complete proofs. This paper seeks to remedy this by providing a compact and accessible survey.