Identifying Well-Connected Communities in Real-World and Synthetic Networks

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

doi:10.1007/978-3-031-53499-7_1

Identifying Well-Connected Communities in Real-World and Synthetic Networks

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

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

Integral to the problem of detecting communities through graph clustering is the expectation that they are “well-connected”. Surprisingly, we find that the output of multiple clustering approaches–the Leiden algorithm with either the Constant Potts Model or modularity as quality function, Iterative K-Core Clustering, Infomap, and Markov Clustering–include communities that fail even a mild requirement for well-connectedness. As a remediation strategy, we have developed the “Connectivity Modifier” (CM), which iteratively removes small edge cuts and re-clusters until all communities detected are well-connected. Results from real-world networks with up to 75,025,194 nodes illustrate how CM enables additional insights into community structure within networks, while results on synthetic networks show that the CM algorithm improves accuracy in recovering true communities. Our study also raises questions about the “clusterability” of networks and mathematical models of community structure.

Original language	English (US)
Title of host publication	Complex Networks and Their Applications XII - Proceedings of The 12th International Conference on Complex Networks and their Applications
Subtitle of host publication	COMPLEX NETWORKS 2023
Editors	Hocine Cherifi, Luis M. Rocha, Chantal Cherifi, Murat Donduran
Publisher	Springer
Pages	3-14
Number of pages	12
ISBN (Print)	9783031534980
DOIs	https://doi.org/10.1007/978-3-031-53499-7_1
State	Published - 2024
Event	12th International Conference on Complex Networks and their Applications, COMPLEX NETWORKS 2023 - Menton, France Duration: Nov 28 2023 → Nov 30 2023

Publication series

Name	Studies in Computational Intelligence
Volume	1142 SCI
ISSN (Print)	1860-949X
ISSN (Electronic)	1860-9503

Conference

Conference	12th International Conference on Complex Networks and their Applications, COMPLEX NETWORKS 2023
Country/Territory	France
City	Menton
Period	11/28/23 → 11/30/23

Keywords

citation networks
community detection
connectivity

ASJC Scopus subject areas

Artificial Intelligence

Online availability

10.1007/978-3-031-53499-7_1

Library availability

Discover UIUC Full Text

Cite this

Park, M., Tabatabaee, Y., Ramavarapu, V., Liu, B., Pailodi, V. K., Ramachandran, R., Korobskiy, D., Ayres, F., Chacko, G., & Warnow, T. (2024). Identifying Well-Connected Communities in Real-World and Synthetic Networks. In H. Cherifi, L. M. Rocha, C. Cherifi, & M. Donduran (Eds.), Complex Networks and Their Applications XII - Proceedings of The 12th International Conference on Complex Networks and their Applications: COMPLEX NETWORKS 2023 (pp. 3-14). (Studies in Computational Intelligence; Vol. 1142 SCI). Springer. https://doi.org/10.1007/978-3-031-53499-7_1

Identifying Well-Connected Communities in Real-World and Synthetic Networks. / Park, Minhyuk; Tabatabaee, Yasamin; Ramavarapu, Vikram et al.
Complex Networks and Their Applications XII - Proceedings of The 12th International Conference on Complex Networks and their Applications: COMPLEX NETWORKS 2023. ed. / Hocine Cherifi; Luis M. Rocha; Chantal Cherifi; Murat Donduran. Springer, 2024. p. 3-14 (Studies in Computational Intelligence; Vol. 1142 SCI).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Park, M, Tabatabaee, Y, Ramavarapu, V, Liu, B, Pailodi, VK, Ramachandran, R, Korobskiy, D, Ayres, F, Chacko, G & Warnow, T 2024, Identifying Well-Connected Communities in Real-World and Synthetic Networks. in H Cherifi, LM Rocha, C Cherifi & M Donduran (eds), Complex Networks and Their Applications XII - Proceedings of The 12th International Conference on Complex Networks and their Applications: COMPLEX NETWORKS 2023. Studies in Computational Intelligence, vol. 1142 SCI, Springer, pp. 3-14, 12th International Conference on Complex Networks and their Applications, COMPLEX NETWORKS 2023, Menton, France, 11/28/23. https://doi.org/10.1007/978-3-031-53499-7_1

Park M, Tabatabaee Y, Ramavarapu V, Liu B, Pailodi VK, Ramachandran R et al. Identifying Well-Connected Communities in Real-World and Synthetic Networks. In Cherifi H, Rocha LM, Cherifi C, Donduran M, editors, Complex Networks and Their Applications XII - Proceedings of The 12th International Conference on Complex Networks and their Applications: COMPLEX NETWORKS 2023. Springer. 2024. p. 3-14. (Studies in Computational Intelligence). doi: 10.1007/978-3-031-53499-7_1

Park, Minhyuk ; Tabatabaee, Yasamin ; Ramavarapu, Vikram et al. / Identifying Well-Connected Communities in Real-World and Synthetic Networks. Complex Networks and Their Applications XII - Proceedings of The 12th International Conference on Complex Networks and their Applications: COMPLEX NETWORKS 2023. editor / Hocine Cherifi ; Luis M. Rocha ; Chantal Cherifi ; Murat Donduran. Springer, 2024. pp. 3-14 (Studies in Computational Intelligence).

@inproceedings{bd6f2391ed7b4a39aff329fa1ee52958,

title = "Identifying Well-Connected Communities in Real-World and Synthetic Networks",

abstract = "Integral to the problem of detecting communities through graph clustering is the expectation that they are “well-connected”. Surprisingly, we find that the output of multiple clustering approaches–the Leiden algorithm with either the Constant Potts Model or modularity as quality function, Iterative K-Core Clustering, Infomap, and Markov Clustering–include communities that fail even a mild requirement for well-connectedness. As a remediation strategy, we have developed the “Connectivity Modifier” (CM), which iteratively removes small edge cuts and re-clusters until all communities detected are well-connected. Results from real-world networks with up to 75,025,194 nodes illustrate how CM enables additional insights into community structure within networks, while results on synthetic networks show that the CM algorithm improves accuracy in recovering true communities. Our study also raises questions about the “clusterability” of networks and mathematical models of community structure.",

keywords = "citation networks, community detection, connectivity",

author = "Minhyuk Park and Yasamin Tabatabaee and Vikram Ramavarapu and Baqiao Liu and Pailodi, {Vidya Kamath} and Rajiv Ramachandran and Dmitriy Korobskiy and Fabio Ayres and George Chacko and Tandy Warnow",

note = "Publisher Copyright: {\textcopyright} The Author(s), under exclusive license to Springer Nature Switzerland AG 2024.; 12th International Conference on Complex Networks and their Applications, COMPLEX NETWORKS 2023 ; Conference date: 28-11-2023 Through 30-11-2023",

year = "2024",

doi = "10.1007/978-3-031-53499-7_1",

language = "English (US)",

isbn = "9783031534980",

series = "Studies in Computational Intelligence",

publisher = "Springer",

pages = "3--14",

editor = "Hocine Cherifi and Rocha, {Luis M.} and Chantal Cherifi and Murat Donduran",

booktitle = "Complex Networks and Their Applications XII - Proceedings of The 12th International Conference on Complex Networks and their Applications",

address = "Germany",

}

TY - GEN

T1 - Identifying Well-Connected Communities in Real-World and Synthetic Networks

AU - Park, Minhyuk

AU - Tabatabaee, Yasamin

AU - Ramavarapu, Vikram

AU - Liu, Baqiao

AU - Pailodi, Vidya Kamath

AU - Ramachandran, Rajiv

AU - Korobskiy, Dmitriy

AU - Ayres, Fabio

AU - Chacko, George

AU - Warnow, Tandy

N1 - Publisher Copyright: © The Author(s), under exclusive license to Springer Nature Switzerland AG 2024.

PY - 2024

Y1 - 2024

N2 - Integral to the problem of detecting communities through graph clustering is the expectation that they are “well-connected”. Surprisingly, we find that the output of multiple clustering approaches–the Leiden algorithm with either the Constant Potts Model or modularity as quality function, Iterative K-Core Clustering, Infomap, and Markov Clustering–include communities that fail even a mild requirement for well-connectedness. As a remediation strategy, we have developed the “Connectivity Modifier” (CM), which iteratively removes small edge cuts and re-clusters until all communities detected are well-connected. Results from real-world networks with up to 75,025,194 nodes illustrate how CM enables additional insights into community structure within networks, while results on synthetic networks show that the CM algorithm improves accuracy in recovering true communities. Our study also raises questions about the “clusterability” of networks and mathematical models of community structure.

AB - Integral to the problem of detecting communities through graph clustering is the expectation that they are “well-connected”. Surprisingly, we find that the output of multiple clustering approaches–the Leiden algorithm with either the Constant Potts Model or modularity as quality function, Iterative K-Core Clustering, Infomap, and Markov Clustering–include communities that fail even a mild requirement for well-connectedness. As a remediation strategy, we have developed the “Connectivity Modifier” (CM), which iteratively removes small edge cuts and re-clusters until all communities detected are well-connected. Results from real-world networks with up to 75,025,194 nodes illustrate how CM enables additional insights into community structure within networks, while results on synthetic networks show that the CM algorithm improves accuracy in recovering true communities. Our study also raises questions about the “clusterability” of networks and mathematical models of community structure.

KW - citation networks

KW - community detection

KW - connectivity

UR - http://www.scopus.com/inward/record.url?scp=85187684836&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85187684836&partnerID=8YFLogxK

U2 - 10.1007/978-3-031-53499-7_1

DO - 10.1007/978-3-031-53499-7_1

M3 - Conference contribution

AN - SCOPUS:85187684836

SN - 9783031534980

T3 - Studies in Computational Intelligence

SP - 3

EP - 14

BT - Complex Networks and Their Applications XII - Proceedings of The 12th International Conference on Complex Networks and their Applications

A2 - Cherifi, Hocine

A2 - Rocha, Luis M.

A2 - Cherifi, Chantal

A2 - Donduran, Murat

PB - Springer

T2 - 12th International Conference on Complex Networks and their Applications, COMPLEX NETWORKS 2023

Y2 - 28 November 2023 through 30 November 2023

ER -

Identifying Well-Connected Communities in Real-World and Synthetic Networks

Abstract

Publication series

Conference

Keywords

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Data for Well-Connectedness and Community Detection

Cite this

Identifying Well-Connected Communities in Real-World and Synthetic Networks

Abstract

Publication series

Conference

Keywords

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Datasets

Data for Well-Connectedness and Community Detection

Cite this