EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Well-connectedness and community detection

Minhyuk Park, Yasamin Tabatabaee, Vikram Ramavarapu, Baqiao Liu, Vidya Kamath Pailodi, Rajiv Ramachandran, Dmitriy Korobskiy, Fabio Ayres, George Chacko, Tandy Warnow

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →