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

The concept of k-path Laplacian matrix of a graph is motivated and introduced. The path Laplacian 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-path Laplacian 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 path Laplacian matrices in a variety of other fields, e.g., synchronization, flocking, Markov chains, etc., will open a new avenue in algebraic graph theory.