Diffusion and consensus on weakly connected directed graphs

DOI10.1016/J.LAA.2019.05.014MaRDI QIDQ2321356zbMATH OpenOpenAlexFDO

Authors J. J. P. Veerman, Ewan Kummel

Publication date 29 August 2019

Published in Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1807.09846

zbMATH Keywords

diffusionconsensusdirected graphdynamics on networksasymmetric Laplacian

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Directed graphs (digraphs), tournaments (05C20) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Connectivity (05C40) Applications of graph theory to circuits and networks (94C15)

Abstract: Let $G$ be a weakly connected directed graph with asymmetric graph Laplacian $calL$. Consensus and diffusion are dual dynamical processes defined on $G$ by $dotx=-calLx$ for consensus and $dotp=-pcalL$ for diffusion. We consider both these processes as well their discrete time analogues. We define a basis of row vectors $$ of the left null-space of $calL$ and a basis of column vectors ${gamm{a}_i}_{i=1}^k$ of the right null-space of $calL$ 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.

Recommendations

• A primer on Laplacian dynamics in directed graphs
• Average consensus on general strongly connected digraphs
• Local weak convergence for PageRank
• Digraph Laplacian and the degree of asymmetry
• On algebraic connectivity of directed scale-free networks

Cites work

• scientific article; zbMATH DE number 53382 (Why is no real title available?)
• scientific article; zbMATH DE number 1179517 (Why is no real title available?)
• A graph-theoretical approach for the analysis and model reduction of complex-balanced chemical reaction networks
• A solution to the reversible embedding problem for finite Markov chains
• Digraphs
• Dynamical systems
• Flocks and formations
• Forest matrices around the Laplacian matrix
• Functions of Matrices
• Harmonic and analytic functions on graphs
• Infinitely divisible nonnegative matrices, M-matrices, and the embedding problem for finite state stationary Markov chains
• Kernels of directed graph Laplacians
• Laplacian dynamics on general graphs
• Laplacians and the Cheeger inequality for directed graphs
• Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
• Network information flow
• Networks
• On the Existence and Uniqueness of the Real Logarithm of a Matrix
• On the spectra of nonsymmetric Laplacian matrices
• Random walks and diffusion on networks
• The complexity of divisibility
• \texttt{PageRank} and random walks on graphs

Cited in

(8)

• Agreement dynamics on directed random graphs
• Nonlinear diffusion on networks: perturbations and consensus dynamics
• Embeddability of real and positive operators
• Degree-biased advection–diffusion on undirected graphs/networks
• Geometric and spectral analysis on weighted digraphs
• A primer on Laplacian dynamics in directed graphs
• Three conjectures of Ostrander on digraph Laplacian eigenvectors
• Effect of Adding Edges to Consensus Networks With Directed Acyclic Graphs

Describes a project that uses

Uses Software

• mftoolbox

This page was built for publication: Diffusion and consensus on weakly connected directed graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2321356)