Matrices of forests, analysis of networks, and ranking problems
This work addresses network analysis and ranking problems, but it appears incremental as it builds on existing forest-based methods without introducing a major breakthrough.
The authors tackled the problem of analyzing network structure and measuring properties like vertex proximity and ranking from preference relations, using matrices of spanning rooted forests, and showed that the vertex accessibility measure based on spanning forests has desirable properties.
The matrices of spanning rooted forests are studied as a tool for analysing the structure of networks and measuring their properties. The problems of revealing the basic 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 stochastic matrix of out-forests in terms of information dissemination is given.