
This Article  
 
Share  
Bibliographic References  
Add to:  
Digg Furl Spurl Blink Simpy Del.icio.us Y!MyWeb  
Search  
 
ASCII Text  x  
Mathieu Senelle, Silvia GarciaDiez, Amin Mantrach, Masashi Shimbo, Marco Saerens, François Fouss, "The SumoverForests Density Index: Identifying Dense Regions in a Graph," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 99, no. 1, pp. 1, , 5555.  
BibTex  x  
@article{ 10.1109/TPAMI.2013.227, author = {Mathieu Senelle and Silvia GarciaDiez and Amin Mantrach and Masashi Shimbo and Marco Saerens and François Fouss}, title = {The SumoverForests Density Index: Identifying Dense Regions in a Graph}, journal ={IEEE Transactions on Pattern Analysis and Machine Intelligence}, volume = {99}, number = {1}, issn = {01628828}, year = {5555}, pages = {1}, doi = {http://doi.ieeecomputersociety.org/10.1109/TPAMI.2013.227}, publisher = {IEEE Computer Society}, address = {Los Alamitos, CA, USA}, }  
RefWorks Procite/RefMan/Endnote  x  
TY  JOUR JO  IEEE Transactions on Pattern Analysis and Machine Intelligence TI  The SumoverForests Density Index: Identifying Dense Regions in a Graph IS  1 SN  01628828 SP EP EPD  1 A1  Mathieu Senelle, A1  Silvia GarciaDiez, A1  Amin Mantrach, A1  Masashi Shimbo, A1  Marco Saerens, A1  François Fouss, PY  5555 KW  Indexes KW  Equations KW  Vegetation KW  Probability distribution KW  Physics KW  Correlation KW  Mining methods and algorithms KW  Trees KW  Graph Theory KW  Discrete Mathematics KW  Mathematics of Computing KW  Data mining VL  99 JA  IEEE Transactions on Pattern Analysis and Machine Intelligence ER   
Web Extra: View Supplemental Material(PDF)
This work introduces a novel nonparametric density index defined on graphs, the SumoverForests (SoF) density index. It is based on a clear and intuitive idea: highdensity regions in a graph are characterized by the fact that they contain a large amount of lowcost trees with high outdegrees while lowdensity regions contain few ones. Therefore, a Boltzmann probability distribution on the countable set of forests in the graph is defined so that large (highcost) forests occur with a low probability while short (lowcost) forests occur with a high probability. Then, the SoF density index of a node is defined as the expected outdegree of this node on the set of forests, thus providing a measure of density around that node. Following the matrixforest 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.
Index Terms:
Indexes,Equations,Vegetation,Probability distribution,Physics,Correlation,Mining methods and algorithms,Trees,Graph Theory,Discrete Mathematics,Mathematics of Computing,Data mining
Citation:
Mathieu Senelle, Silvia GarciaDiez, Amin Mantrach, Masashi Shimbo, Marco Saerens, François Fouss, "The SumoverForests Density Index: Identifying Dense Regions in a Graph," IEEE Transactions on Pattern Analysis and Machine Intelligence, 21 Nov. 2013. IEEE computer Society Digital Library. IEEE Computer Society, <http://doi.ieeecomputersociety.org/10.1109/TPAMI.2013.227>
Usage of this product signifies your acceptance of the Terms of Use.