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 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 O(n × log (n)). Experiments show that our algorithm creates highly compact clusters.
['Jean Creusefond', 'Thomas Largillier', 'Sylvain Peyronnet']
Finding compact communities in large graphs