The Matrix of Maximum Out Forests of a Digraph and Its Applications

Abstract

We study the maximum out forests of a (weighted) digraph and the matrix of maximum out forests. A maximum out forest of a digraph G is a spanning subgraph of G that consists of disjoint diverging trees and has the maximum possible number of arcs. If a digraph contains any out arborescences, then maximum out forests coincide with them. We provide a new proof to the Markov chain tree theorem saying that the matrix of Ces`aro limiting probabilities of an arbitrary stationary finite Markov chain coincides with the normalized matrix of maximum out forests of the weighted digraph that corresponds to the Markov chain. We discuss the applications of the matrix of maximum out forests and its transposition, the matrix of limiting accessibilities of a digraph, to the problems of preference aggregation, measuring the vertex proximity, and uncovering the structure of a digraph.

arXiv comment27 pages, 3 figures

Cited by in corpus (15)

• Structure of Cell Networks Critically Determines Oscillation Regularity
• Comments on "Consensus and Cooperation in Networked Multi-Agent Systems"
• On graph theoretic results underlying the analysis of consensus in multi-agent systems
• The Projection Method for Reaching Consensus and the Regularized Power Limit of a Stochastic Matrix
• Phase synchronization between collective rhythms of fully locked oscillator groups
• Which Digraphs with Ring Structure are Essentially Cyclic?
• Incremental Computation of Pseudo-Inverse of Laplacian: Theory and Applications
• State-dependent effective interactions in oscillator networks through coupling functions with dead zones
• On the Poisson equation for nonreversible Markov jump processes
• Models of latent consensus
• Matrices of Forests and the Analysis of Digraphs
• Matrices of forests, analysis of networks, and ranking problems
• Distributed Learning of Distributions via Social Sampling
• Static consensus in passifiable linear networks
• The Effects of Structural Perturbations on the Synchronizability of Diffusive Networks