Well-connectedness and community detection
PLOS Complex Systems · 05.11.2024 · 1 (3) · e0000009
DOI: 10.1371/journal.pcsy.0000009 ↗Kurz gefasst
Fachartikel in der Zeitschrift PLOS Complex Systems, online erschienen am 05.11.2024. Verfasst von Minhyuk Park und 9 weiteren Autor:innen. Die Arbeit wurde bisher 14-mal zitiert (Crossref) und nennt 66 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: insper-illinois, Oracle, National Science Foundation.
Abstract (Originalsprache)
Community detection methods help reveal the meso-scale structure of complex networks. Integral to detecting communities is the expectation that communities in a network are edge-dense and “well-connected”. Surprisingly, we find that five different community detection methods–the Leiden algorithm optimizing the Constant Potts Model, the Leiden algorithm optimizing modularity, Infomap, Markov Cluster (MCL), and Iterative k-core (IKC)–identify communities that fail even a mild requirement for well-connectedness. To address this issue, we have developed the Connectivity Modifier (CM), which iteratively removes small edge cuts and re-clusters until communities are well-connected according to a user-specified criterion. We tested CM on real-world networks ranging in size from approximately 35,000 to 75,000,000 nodes. Post-processing of the output of community detection methods by CM resulted in a reduction in node coverage. Results on synthetic networks show that the CM algorithm generally maintains or improves accuracy in recovering true communities. This study underscores the importance of network clusterability–the fraction of a network that exhibits community structure–and the need for more models of community structure where networks contain nodes that are not assigned to communities. In summary, we address well-connectedness as an important aspect of clustering and present a scalable open-source tool for well-connected clusters.
Förderung
- insper-illinois
- Oracle
- National Science Foundation
Zitieren
APA
Park, M., Tabatabaee, Y., Ramavarapu, V., Liu, B., Pailodi, V. K., Ramachandran, R., Korobskiy, D., Ayres, F., Chacko, G., & Warnow, T. (2024). Well-connectedness and community detection. PLOS Complex Systems, 1(3), e0000009. https://doi.org/10.1371/journal.pcsy.0000009
Vancouver
Park M, Tabatabaee Y, Ramavarapu V, Liu B, Pailodi VK, Ramachandran R, et al. Well-connectedness and community detection. PLOS Complex Systems. 2024;1(3):e0000009. doi:10.1371/journal.pcsy.0000009
BibTeX
@article{Park2024,
author = {Park, Minhyuk and Tabatabaee, Yasamin and Ramavarapu, Vikram and Liu, Baqiao and Pailodi, Vidya Kamath and Ramachandran, Rajiv and Korobskiy, Dmitriy and Ayres, Fabio and Chacko, George and Warnow, Tandy},
title = {Well-connectedness and community detection},
journal = {PLOS Complex Systems},
year = {2024},
volume = {1},
number = {3},
pages = {e0000009},
doi = {10.1371/journal.pcsy.0000009}
}
EUVIMED