Finding compact communities in large graphs
arXiv:1410.2105
Abstract
This article presents an efficient hierarchical clustering algorithm that solves the problem of core community detection. It is a variant of the standard community detection problem in which we are particularly interested in the connected core of communities. To provide a solution to this problem, we question standard definitions on communities and provide alternatives. We also propose a function called compactness, designed to assess the quality of a solution to this problem. Our algorithm is based on a graph traversal algorithm, the LexDFS. The time complexity of our method is in . Experiments show that our algorithm creates highly compact clusters.
arXiv comment8 pages, 8 figures
References in corpus (9)
- Community structure in social and biological networks
- Finding and evaluating community structure in networks
- Community detection in graphs
- Finding community structure in very large networks
- Resolution limit in community detection
- CFinder: Locating cliques and overlapping modules in biological networks
- Community extraction for social networks
- Empirical Comparison of Algorithms for Network Community Detection
- Axioms for graph clustering quality functions