A vertex-similarity clustering algorithm for community detection. Issue 1 (2nd January 2020)

• Record Type: Journal Article
• Authors: Maria Fiscarelli, Antonio; Brust, Matthias R.; Danoy, Grégoire; Bouvry, Pascal
• Is Part Of: Journal of information and telecommunication. Volume 4:Issue 1(2020)
• Page Start: 36
• Page End: 50
• Publication Date: 2020-01-02
• Subjects: Community detection -- Graph clustering -- Social network analysis; Telecommunication -- Periodicals; Information technology -- Periodicals; 621.382
• DOI: 10.1080/24751839.2019.1686683
• Languages: English
• ISSNs: 2475-1839

Abstract

ABSTRACT: Communities in networks are considered to be groups of vertices with higher probability of being connected to each other than to members of other groups. Community detection, then, is a method to identify these communities based on the higher intra-cluster and lower inter-cluster connectivity. Depending on the type and size of the network, detecting such communities can be a challenging task. The method we propose is a degenerate agglomerative hierarchical clustering algorithm (DAHCA) that makes use of the reachability matrix to find a community structure in networks. We tested DAHCA using common classes of network benchmarks as well as real-world networks and compared it to state-of-the-art community detection algorithms. Our results show that it can effectively identify hierarchies of communities, and outperform some of the algorithms for more complex networks. In particular, when communities start to exhibit very low intra-community connectivity, it is the only method that is still able to identify communities.