Forest matrices around the Laplacian matrix

By Pavel Yu. Chebotarev, Rafig P. Agaev. 2002

129 citations recorded by the source corpus.

Abstract We study the matrices Q k of in-forests of a weighted digraph Γ and their connections with the Laplacian matrix L of Γ . The ( i , j ) entry of Q k is the total weight of spanning converging forests ( in-forests ) with k arcs such that i belongs to a tree rooted at j . The forest matrices, Q k , can be calculated recursively and expressed by polynomials in the Laplacian matrix; they provide representations for the generalized inverses, the powers, and some eigenvectors of L . The normalized in-forest matrices are row stochastic; the normalized matrix of maximum in-forests is the eigenprojection of the Laplacian matrix, which provides an immediate proof of the Markov chain tree theorem. A source of these results is the fact that matrices Q k are the matrix coefficients in the polynomial expansion of adj( λI + L ). Thereby they are precisely Faddeev’s matrices for − L .

Subfields: Computational Theory and Mathematics, Geometry and Topology, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/84a1b677c035ae44678fe1850e0150ed0ea71244

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Geometry and Topology

In Statistics and Probability

Citations in the corpus

Centrality measure in graphs (2010, background): “Indeed “betweenness” centrality has already been often framed in terms of the shortest-path distance, but as there are [56–59] different fundamental distance functions definable on a graph, this naturally indicates the possibility of different centrality definitions.”
A tutorial on modeling and analysis of dynamic social networks. Part I (2017, background): “Nodes of a graph without directed spanning tree are covered by several directed trees, or spanning forest [67].”
Commute Times for a Directed Graph using an Asymmetric Laplacian (2011, background): “[7].”
Coordination in multiagent systems and Laplacian spectra of digraphs (2009, methodology): “To compute the matrix J̄ , one can use the algorithm proposed in [19, 20], which reduces to min{n − d − 1, 0} multiplications of matrices of order n.”