Event Detail

Event Type: 
Applied Mathematics and Computation Seminar
Friday, March 15, 2019 - 12:00 to 13:00
STAG 110

Speaker Info

Portland State

We outline a complete and self-contained treatment of the asymptotics of (discrete and continuous)
consensus and diffusion on directed graphs. Let G be a weakly connected directed graph with directed
graph Laplacian L. In many or most applications involving digraphs, it is possible to identify a
direction of the flow of information. We fix that direction as the direction of the edges. With this
convention, consensus (and its discrete-time analogue) and diffusion (and its discrete-time analogue)
are dual to one another in the sense that \dot x = -Lx for consensus, and \dot p = -pL for diffusion.
As a result, their asymptotic states can be described as duals.

We give a precise characterization of a basis of row vectors {c_i} of the left null-space of L
and of a basis of column vectors {d_i} of the right null-space of L. This characterization is given
in terms of the partition of G into strongly connected components and how these are connected to
each other. In turn, this allows us to give a complete characterization of the asymptotic behavior of
both diffusion and consensus 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, and give a new result that shows that the teleporting (see below) feature usually
included in the algorithm actually does not add information.