Path Laplacian matrices: introduction and application to the analysis of consensus in networks

Ernesto Estrada

Research output: Contribution to journalArticle

16 Citations (Scopus)

Abstract

The concept of k-pathLaplacian matrix of a graph is motivated and introduced. The pathLaplacian matrices are a natural generalization of the combinatorial Laplacian of a graph. They are defined by using path matrices accounting for the existence of shortest paths of length k between two nodes. This new concept is motivated by the problem of determining whether every node of a graph can be visited by means of a process consisting of hopping from one node to another separated at distance k from it. The problem is solved by using the multiplicity of the trivial eigenvalue of the corresponding k-pathLaplacian matrix. We apply these matrices to the analysis of the consensus among agents in a networked system. We show how the consensus in different types of network topologies is accelerated by considering not only nearest neighbors but also the influence of long-range interacting ones. Further applications of pathLaplacian matrices in a variety of other fields, e.g., synchronization, flocking, Markov chains, etc., will open a new avenue in algebraic graph theory.

Original languageEnglish
Pages (from-to)3373-3391
Number of pages19
JournalLinear Algebra and its Applications
Volume436
Issue number9
DOIs
Publication statusPublished - 1 May 2012

    Fingerprint

Keywords

  • graph theory
  • path matrices
  • laplacian matrix
  • consensusanalysis
  • synchronization

Cite this