Event Type:

Applied Mathematics and Computation Seminar

Date/Time:

Friday, March 15, 2019 - 12:00 to 13:00

Location:

STAG 110

Event Link:

Guest Speaker:

Institution:

Portland State

Abstract:

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.

Host: