Computational Aspects of Lucidity-Driven Graph Clustering
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.
Submitted: March 2009.
Reviewed: September 2009.
Revised: October 2009.
Accepted: December 2009.
Final: December 2009.
Published: January 2010.
Communicated by Ulrik Brandes
article (PDF)