Geodesic
Computational Aspects of Lucidity-Driven Graph Clustering
Journal of Graph Algorithms and Applications, Tome 14 (2010) no. 2, pp. 165-197.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

We formally state and investigate the lucidity paradigm for graph clusterings. The rationale that substantiates this concept is the trade-off between the achieved quality and the expected quality of a graph clustering. A recently defined quality measure for graph clusterings, modularity, is one specific realization of this paradigm, in fact the pioneering one. On a theoretical side, we state a sound probability space for lucidityand thus for modularity and prove that in this paradigm of lucidity, using a subtractive trade-off and either the index coverage (yields modularity) or performance leads to equivalent indices. Furthermore, we show that the NP-hardness of optimizing these indices yields the NP-hardness of the problem MINMIXEDMULTIPARTITION. Moreover, we describe an efficient maximization algorithm for a divisive trade-off between quality and expectation. We experimentally evaluate four realizations of this paradigm systematically and confirm their feasibility in a first methodic analysis of the behavior of these realizations on both artificial and on real-world data, arriving at good results of community assessment and detection.
DOI : 10.7155/jgaa.00203
Keywords: graph clustering, algorithms, modularity, probability space, experimental evaluation, clustering quality 
@article{JGAA_2010_14_2_a2,
     author = {Robert G\"orke and Marco Gaertler and Florian H\"ubner and Dorothea Wagner},
     title = {Computational {Aspects} of {Lucidity-Driven} {Graph} {Clustering}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {165--197},
     publisher = {mathdoc},
     volume = {14},
     number = {2},
     year = {2010},
     doi = {10.7155/jgaa.00203},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00203/}
}
TY  - JOUR
AU  - Robert Görke
AU  - Marco Gaertler
AU  - Florian Hübner
AU  - Dorothea Wagner
TI  - Computational Aspects of Lucidity-Driven Graph Clustering
JO  - Journal of Graph Algorithms and Applications
PY  - 2010
SP  - 165
EP  - 197
VL  - 14
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00203/
DO  - 10.7155/jgaa.00203
LA  - en
ID  - JGAA_2010_14_2_a2
ER  - 
%0 Journal Article
%A Robert Görke
%A Marco Gaertler
%A Florian Hübner
%A Dorothea Wagner
%T Computational Aspects of Lucidity-Driven Graph Clustering
%J Journal of Graph Algorithms and Applications
%D 2010
%P 165-197
%V 14
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00203/
%R 10.7155/jgaa.00203
%G en
%F JGAA_2010_14_2_a2
Robert Görke; Marco Gaertler; Florian Hübner; Dorothea Wagner. Computational Aspects of Lucidity-Driven Graph Clustering. Journal of Graph Algorithms and Applications, Tome 14 (2010) no. 2, pp. 165-197. doi : 10.7155/jgaa.00203. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00203/

Cité par Sources :