Published In

Linear Algebra and its Applications

Document Type

Post-Print

Publication Date

10-2019

Subjects

Topological graph theory, Set theory

Abstract

Let G be a weakly connected directed graph with asymmetric graph Laplacian L. Consensus and diffusion are dual dynamical processes defined on G by x˙=−Lx for consensus and p˙=−pL for diffusion. We consider both these processes as well their discrete time analogues. We define a basis of row vectors {γ¯i}ki=1 of the left null-space of L and a basis of column vectors {γi}ki=1 of the right null-space of 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.

Description

This is the peer reviewed version of the following article: J.J.P. Veerman and Ewan Kummel. 2019. "Diffusion and Consensus on Weakly Connected Directed Graphs" which has been published in final form at :https://doi.org/10.1016/j.laa.2019.05.014 This article may be used for non-commercial purposes in accordance with Elsevier Terms and Conditions for Use of Self-Archived Versions.

© 2019 Elsevier Inc. All rights reserved.

DOI

10.1016/j.laa.2019.05.014

Persistent Identifier

https://archives.pdx.edu/ds/psu/29670

Download

Share

COinS