Journal of Graph Algorithms and Applications
http://jgaa.info ISSN: 1526-1719
DOI: 10.7155/jgaa.00203 Computational Aspects of Lucidity-Driven Graph Clustering Robert Görke , Marco Gaertler , Florian Hübner , and Dorothea Wagner Vol. 14, no. 2, pp. 165-197, 2010. Regular paper Abstract 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.
|
Revised: October 2009. Published: January 2010. Reviewed: September 2009. Final: December 2009. Submitted: March 2009. Accepted: December 2009. Communicated by Ulrik Brandes |
Journal of Graph Algorithms and Applications |