A Correlation Clustering Framework for Community Detection
| Autor: | David F. Gleich, Anthony Wirth, Nate Veldt |
|---|---|
| Rok vydání: | 2018 |
| Předmět: |
Modularity (networks)
Optimization problem Theoretical computer science Computer science Correlation clustering Approximation algorithm Context (language use) 0102 computer and information sciences 02 engineering and technology 01 natural sciences Graph 010201 computation theory & mathematics 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing Cluster analysis Clustering coefficient |
| Zdroj: | WWW |
| DOI: | 10.1145/3178876.3186110 |
| Popis: | Graph clustering, or community detection, is the task of identifying groups of closely related objects in a large network. In this paper we introduce a new community detection framework called LambdaCC that is based on a specially weighted version of correlation clustering. A key component in our methodology is a clustering resolution parameter, lambda, which implicitly controls the size and structure of clusters formed by our framework. We show that, by increasing this parameter, our objective effectively interpolates between two different strategies in graph clustering: finding a sparse cut and forming dense subgraphs. Our methodology unifies and generalizes a number of other important clustering quality functions including modularity, sparsest cut, and cluster deletion, and places them all within the context of an optimization problem that has been well studied from the perspective of approximation algorithms. Our approach to clustering is particularly relevant in the regime of finding dense clusters, as it leads to a 2-approximation for the cluster deletion problem. We use our approach to cluster several graphs, including large collaboration networks and social networks. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|