  Complex networks constitute the backbones of many complex systems such as
social networks. Detecting the community structure in a complex network is both
a challenging and a computationally expensive task. In this paper, we present
the HAMUHI-CODE, a novel fast heuristic algorithm for multi-scale hierarchical
community detection inspired on an agglomerative hierarchical clustering
technique. We define a new structural similarity of vertices based on the
classical cosine similarity by removing some vertices in order to increase the
probability of identifying inter-cluster edges. Then we use the proposed
structural similarity in a new agglomerative hierarchical algorithm that does
not merge only clusters with maximal similarity as in the classical approach,
but merges any cluster that does not meet a parameterized community definition
with its most similar adjacent cluster. The algorithm computes all the similar
clusters at the same time is checking if each cluster meets the parameterized
community definition. It is done in linear time complexity in terms of the
number of cluster in the iteration. Since a complex network is a sparse graph,
our approach HAMUHI-CODE has a super-linear time complexity with respect to the
size of the input in the worst-case scenario (if the clusters merge in pairs),
making it suitable to be applied on large-scale complex networks. To test the
properties and the efficiency of our algorithm we have conducted extensive
experiments on real world and synthetic benchmark networks by comparing it to
several baseline state-of-the-art algorithms.
