Diffusion and consensus on weakly connected directed graphs

DOI10.1016/J.LAA.2019.05.014zbMATH Open1419.05093arXiv1807.09846OpenAlexW2883699556MaRDI QIDQ2321356FDOQ2321356

Ewan Kummel, J. J. P. Veerman

Publication date: 29 August 2019

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

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.

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

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

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)

Cites Work

• Functions of Matrices
• Title not available (Why is that?)
• Title not available (Why is that?)
• Network information flow
• Digraphs
• Laplacians and the Cheeger inequality for directed graphs
• Forest matrices around the Laplacian matrix
• The complexity of divisibility
• On the spectra of nonsymmetric Laplacian matrices
• A solution to the reversible embedding problem for finite Markov chains
• On the Existence and Uniqueness of the Real Logarithm of a Matrix
• Title not available (Why is that?)
• Laplacian dynamics on general graphs
• \texttt{PageRank} and random walks on graphs
• Kernels of directed graph Laplacians
• A graph-theoretical approach for the analysis and model reduction of complex-balanced chemical reaction networks
• Title not available (Why is that?)
• Harmonic and analytic functions on graphs
• Flocks and formations
• Random walks and diffusion on networks
• Networks
• Infinitely divisible nonnegative matrices, \(M\)-matrices, and the embedding problem for finite state stationary Markov chains

Cited In (6)

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

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)