Algorithmic Aspects in Information and Management

Significance-Driven Graph Clustering (p. 11-12)

Marco Gaertler, Robert G¨orke, and Dorothea Wagner
Faculty of Informatics, Universit¨at Karlsruhe (TH)

Abstract. Modularity, the recently defined quality measure for clusterings, has attained instant popularity in the fields of social and natural sciences. We revisit the rationale behind the definition of modularity and explore the founding paradigm. This paradigm is based on the trade-off between the achieved quality and the expected quality of a clustering with respect to networks with similar intrinsic structure. We experimentally evaluate realizations of this paradigm systematically, including modularity, and describe efficient algorithms for their optimization. We confirm the feasibility of the resulting generality by a first systematic analysis of the behavior of these realizations on both artificial and on real-world data, arriving at remarkably good results of community detection.

1 Introduction

Discovering natural groups and large scale inhomogeneities is a crucial task in the exploration and analysis of large and complex networks. This task is usually realized with clustering methods. The majority of algorithms for graph clustering are based on the paradigm of intra-cluster density versus inter-cluster sparsity. Several formalizations have been proposed and evaluated, an overview of such techniques is given in [1]. Recently, Girvan and Newman [2] proposed the objective function modularity, which indirectly incorporates this paradigm. Modularity evaluates a clustering based on the fraction of intra-cluster edges compared to the expected value of this number. Modularity was .rst introduced as a quality measure of a clustering, however, a simple greedy algorithm, solely based on modularity, has been proposed shortly after by Newman [3]. The definition of modularity and this algorithm evoked a surge of interest, yielding many studies concerning different applications, such as protein interaction dependencies, recommendation systems or social network analysis, and possible adjustments (see e.g. [4,5,6,7]). Moreover, a range of alternative algorithmic approaches has been proposed, based on a greedy agglomeration [8,9], on spectral division [10,11], simulated annealing [12,13] and extremal optimization [14]. Recently, it has been proven, that it is NP-hard to optimize modularity [15], which justi.es the need for heuristics and approximations. Note that little is known on the approximability of modularity.

However, to our knowledge, no systematic evaluation of modularity-based clustering has been performed, yet. In this work, we conduct such an evaluation and, additionally, we advance towards a profound understanding of the rationales modularity is based upon. We formally state and investigate the generalized founding paradigm for the signi.cance of a clustering as the trade-off between the achieved quality and the expected quality for random networks incorporating the intrinsic properties of the original network. We experimentally evaluate realizations of this paradigm (including modularity itself) and extensively evaluate algorithms that each optimize a realization, followed by a partial discussion of their behavior. Furthermore, we present an algorithm that efficiently optimizes the particularly promising realization relative performance signi.cance in O(n2 log n) time. We compare the performance of these algorithms in terms of clustering quality to that of other clustering algorithms, on a set of random pre-clustered graphs and complement our findings with results on real data. Our results indicate the feasibility of the paradigm in that, on the whole, our algorithms surpass the benchmark algorithms, and in that the generality of the approach is justified by specific realizations excelling on real-world data.

This paper is organized as follows: After introducing the necessary preliminaries for graph clustering and some quality measures (Sec. 2), we give the formal definition of our significance paradigm and present some realizations (Sec. 3). Section 4 scrutinizes the greedy algorithms which are employed to obtain clusterings with high signi.cance score, including an e.cient implementation for a quick divisive merge. The setup and the results of the experimental evaluation are described in Section 5 which are followed by a conclusion.