Improving the accuracy of community detection methods using connectivity modifier

Community detection algorithms are commonly used to recover the community structure of complex networks. To evaluate the accuracy of these algorithms and compare them against each other, one would need to apply them to networks with known community structure. However, the community structure of real-world networks is usually not known, and hence synthetic networks with ground-truth communities are used for benchmarking these algorithms. The most widely adopted synthetic networks for the evaluation of community detection methods are the Lancichinetti-Fortunato-Radicchi (LFR) benchmark graphs. Here we develop a pipeline for creating LFR graphs that emulate the characteristics of given real-world networks and their clusterings. While our study shows that these LFR graphs almost perfectly match some characteristics of the real-world networks they attempt to emulate, there are striking differences among their other properties. We also evaluate the recently introduced Connectivity Modifier (CM) algorithm, a meta-method for ensuring well-connectedness of clusters outputted by community detection methods, on these empirical networks and LFR graphs. Our results show that while CM reduces node coverage, it improves the accuracy of Leiden algorithm optimizing modularity or the Constant Potts model (CPM) in many model conditions.

Name thesis:degree_name

M.S.

Level thesis:degree_level

Thesis

Discipline thesis:degree_discipline

Computer Science

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2023

Author dc:creator

• Tabatabaee, Seyedeh Yasamin

Contributors dc:contributor

• Warnow, Tandy

• Community Detection
• Clustering
• Connectivity
• Leiden
• Lfr Graphs

Statement dc:rights

• Copyright 2023 Seyedeh Yasamin Tabatabaee

Language dc:language

en, eng

Handle dc:identifier

https://hdl.handle.net/2142/122154

OAI record oai:identifier

https://www.ideals.illinois.edu/oai-pmh?verb=GetRecord&metadataPrefix=etdms&identifier=oai%3Awww.ideals.illinois.edu%3A2142%2F122154