The Sum-over-Forests density index: identifying dense regions in a graph
Authors:
- Mathieu SenelleMSMathieu Senelle
- Silvia Garcia-DiezSGSilvia Garcia-Diez
- Amin MantrachAMAmin Mantrach
- Masashi ShimboMSMasashi Shimbo
- Marco SaerensMSMarco Saerens
- François FoussFFFrançois Fouss
Preprint
Abstract
This work introduces a novel nonparametric density index defined on graphs, the Sum-over-Forests (SoF) density index. It is based on a clear and intuitive idea: high-density regions in a graph are characterized by the fact that they contain a large amount of low-cost trees with high outdegrees while low-density regions contain few ones. Therefore, a Boltzmann probability distribution on the countable set of forests in the graph is defined so that large (high-cost) forests occur with a low probability while short (low-cost) forests occur with a high probability. Then, the SoF density index of a node is defined as the expected outdegree of this node in a non-trivial tree of the forest, thus providing a measure of density around that node. Following the matrix-forest theorem, and a statistical physics framework, it is shown that the SoF density index can be easily computed in closed form through a simple matrix inversion. Experiments on artificial and real data sets show that the proposed index performs well on finding dense regions, for graphs of various origins.Keywords
All Related Versions
This publication has 19 references indexed in Scilit:
- A probing method for computing the diagonal of a matrix inverseNumerical Linear Algebra with Applications, 2011
- Semi-supervised classification and betweenness computation on large, sparse, directed graphsPattern Recognition, 2010
- Graph nodes clustering with the sigmoid commute-time kernel: A comparative studyData & Knowledge Engineering, 2009
- Iterative shrinking method for clustering problemsPattern Recognition, 2006
- The architecture of complex weighted networksProceedings of the National Academy of Sciences of the United States of America, 2004
- Forest matrices around the Laplacian matrixLinear Algebra and its Applications, 2002
- A Modern Course in Statistical PhysicsPhysics Today, 1999
- Collective dynamics of ‘small-world’ networksNature, 1998
- Cyclic flows, Markov process and stochastic traffic assignmentTransportation Research Part B: Methodological, 1996
- A graph‐theoretic generalization of the clique conceptThe Journal of Mathematical Sociology, 1978