Well-Connected Communities in Real-World and Synthetic Networks
N/D
Autores
Park, Minhyuk
Tabatabaee, Yasamin
Ramavarapu, Vikram
Liu, Baqiao
Pailodi, Vidya Kamath
Ramachandran, Rajiv
Korobskiy, Dmitriy
Chacko, George
Warnow, Tandy
Orientador
Co-orientadores
Citações na Scopus
Tipo de documento
Artigo Científico
Data
2023
Título da Revista
ISSN da Revista
Título do Volume
Resumo
Integral to the problem of detecting communities through graph clustering is the expectation that they are "well connected". In this respect, we examine five different community detection approaches optimizing different criteria: the Leiden algorithm optimizing the Constant Potts Model, the Leiden algorithm optimizing modularity, Iterative K-Core Clustering (IKC), Infomap, and Markov Clustering (MCL). Surprisingly, all these methods produce, to varying extents, communities that fail even a mild requirement for well connectedness. To remediate clusters that are not well connected, we have developed the "Connectivity Modifier" (CM), which, at the cost of coverage, iteratively removes small edge cuts and re-clusters until all communities produced are well connected. Results from real-world and synthetic networks illustrate a tradeoff users make between well connected clusters and coverage, and raise questions about the "clusterability" of networks and models of community structure.
Titulo de periódico
URL da fonte
Título de Livro
URL na Scopus
Idioma
Inglês