Matrices of Forests and the Analysis of Digraphs
<|reference_start|>Matrices of Forests and the Analysis of Digraphs: The matrices of spanning rooted forests are studied as a tool for analysing the structure of digraphs and measuring their characteristics. The problems of revealing the basis bicomponents, measuring vertex proximity, and ranking from preference relations / sports competitions are considered. It is shown that the vertex accessibility measure based on spanning forests has a number of desirable properties. An interpretation for the normalized matrix of out-forests in terms of information dissemination is given.   Keywords: Laplacian matrix, spanning forest, matrix-forest theorem, proximity measure, bicomponent, ranking, incomplete tournament, paired comparisons<|reference_end|>
@article{chebotarev2005matrices,
    title={Matrices of Forests and the Analysis of Digraphs},
    author={Pavel Chebotarev and Rafig Agaev},
    journal={arXiv preprint arXiv:math/0508171},
    year={2005},
    archivePrefix={arXiv},
    eprint={math/0508171},
    primaryClass={math.CO cs.CV cs.NI}
}