Computational Aspects of Lucidity-Driven Graph Clustering
| Autor: | Marco Gaertler, Robert Görke, Florian Hübner, Dorothea Wagner |
|---|---|
| Rok vydání: | 2010 |
| Předmět: |
Theoretical computer science
General Computer Science Maximization computer.software_genre Computer Science Applications Theoretical Computer Science Probability space Computational Theory and Mathematics Graph (abstract data type) Geometry and Topology Data mining computer Clustering coefficient Mathematics |
| Zdroj: | Journal of Graph Algorithms and Applications. 14:165-197 |
| ISSN: | 1526-1719 |
| DOI: | 10.7155/jgaa.00203 |
| Popis: | 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 lucidity and 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. Submitted: March 2009 Reviewed: September 2009 Revised: October 2009 Accepted: December 2009 Final: December 2009 Published: January 2010 Article type: Regular paper Communicated by: U. Brandes This work was partially supported by the DFG under grants WA 654/14-3 and WA 654/15-1 and by the EU under grant DELIS (contract no. 001907) and grant CREEN (contract no. 012684). E-mail addresses: robert.goerke@kit.edu (Robert Gorke) marco.gaertler@kit.edu (Marco Gaertler) florian.h@gmail.com (Florian Hubner) dorothea.wagner@kit.edu (Dorothea Wagner) 166 Gorke et al. Comp. Aspects of Lucidity-Driven Graph Clustering |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|