A vertex-similarity clustering algorithm for community detection
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. Depen...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Taylor & Francis Group
2020-01-01
|
| Series: | Journal of Information and Telecommunication |
| Subjects: | |
| Online Access: | http://dx.doi.org/10.1080/24751839.2019.1686683 |
| _version_ | 1828852604601368576 |
|---|---|
| author | Antonio Maria Fiscarelli Matthias R. Brust Grégoire Danoy Pascal Bouvry |
| author_facet | Antonio Maria Fiscarelli Matthias R. Brust Grégoire Danoy Pascal Bouvry |
| author_sort | Antonio Maria Fiscarelli |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-12-12T23:56:46Z |
| format | Article |
| id | doaj.art-c582803191e740dab307d38ea4bd5273 |
| institution | Directory Open Access Journal |
| issn | 2475-1839 2475-1847 |
| language | English |
| last_indexed | 2024-12-12T23:56:46Z |
| publishDate | 2020-01-01 |
| publisher | Taylor & Francis Group |
| record_format | Article |
| series | Journal of Information and Telecommunication |
| spelling | doaj.art-c582803191e740dab307d38ea4bd52732022-12-22T00:06:33ZengTaylor & Francis GroupJournal of Information and Telecommunication2475-18392475-18472020-01-0141365010.1080/24751839.2019.16866831686683A vertex-similarity clustering algorithm for community detectionAntonio Maria Fiscarelli0Matthias R. Brust1Grégoire Danoy2Pascal Bouvry3University of LuxembourgUniversity of LuxembourgUniversity of LuxembourgUniversity of LuxembourgCommunities 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.http://dx.doi.org/10.1080/24751839.2019.1686683community detectiongraph clusteringsocial network analysis |
| spellingShingle | Antonio Maria Fiscarelli Matthias R. Brust Grégoire Danoy Pascal Bouvry A vertex-similarity clustering algorithm for community detection Journal of Information and Telecommunication community detection graph clustering social network analysis |
| title | A vertex-similarity clustering algorithm for community detection |
| title_full | A vertex-similarity clustering algorithm for community detection |
| title_fullStr | A vertex-similarity clustering algorithm for community detection |
| title_full_unstemmed | A vertex-similarity clustering algorithm for community detection |
| title_short | A vertex-similarity clustering algorithm for community detection |
| title_sort | vertex similarity clustering algorithm for community detection |
| topic | community detection graph clustering social network analysis |
| url | http://dx.doi.org/10.1080/24751839.2019.1686683 |
| work_keys_str_mv | AT antoniomariafiscarelli avertexsimilarityclusteringalgorithmforcommunitydetection AT matthiasrbrust avertexsimilarityclusteringalgorithmforcommunitydetection AT gregoiredanoy avertexsimilarityclusteringalgorithmforcommunitydetection AT pascalbouvry avertexsimilarityclusteringalgorithmforcommunitydetection AT antoniomariafiscarelli vertexsimilarityclusteringalgorithmforcommunitydetection AT matthiasrbrust vertexsimilarityclusteringalgorithmforcommunitydetection AT gregoiredanoy vertexsimilarityclusteringalgorithmforcommunitydetection AT pascalbouvry vertexsimilarityclusteringalgorithmforcommunitydetection |