The identification of communities and the corresponding hierarchical structure in real-world networks has been an active research topic for decades [1]}, although a single, precise definition of a community does not seem to exist [2]}, [3]}. In network science, a community is defined as a set of nodes that share links dominantly between themselves, while a minority of links is shared with other nodes in the network.
Newman proposed in [4]} a spectral clustering algorithm that reveals hierarchical structure of a network, by optimising modularity, a commonly used quality function of a graph partition. A heuristic, modularity-based two-step clustering algorithm, proposed by Blondel et al. in [5]}, has proved to be computationally efficient and performed among the best in the comparative study conducted in [6]}. Recently, Peixoto proposed in [7]} a nested generative model, able to identify nested partitions at different resolutions, which thus overcomes an existing drawback of a majority of clustering algorithms, identifying small, but well-distinguished communities in a large network. Dannon et al. concluded in their comparative study [8]} that those clustering algorithms performing the best tend to be less computationally efficient.
We refer to [1]} for a detailed review on existing clustering algorithms.
