Computational Aspects of Lucidity-Driven Graph Clustering

We formally state and investigate the lucidity paradigm for graph clusterings. The rationale that substantiates this concept is the trade-o between the achieved quality and the expected quality of a graph clustering. A recently dened quality measure for graph clusterings, modularity, is one specic 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-o 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 ecient maximization algorithm for a divisive trade-o between quality and expectation. We experimentally evaluate four realizations of this paradigm systematically and conrm their feasibility in a rst methodic analysis of the behavior of these realizations on both articial and on real-world data, arriving at good results of community assessment and detection.