Improving the accuracy of community detection methods using connectivity modifier

Tabatabaee, Seyedeh Yasamin

Permalink

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

Description

Title

Improving the accuracy of community detection methods using connectivity modifier

Author(s)

Tabatabaee, Seyedeh Yasamin

Issue Date

2023-12-04

Director of Research (if dissertation) or Advisor (if thesis)

Warnow, Tandy

Department of Study

Computer Science

Discipline

Computer Science

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

M.S.

Degree Level

Thesis

Keyword(s)

• Community detection
• Clustering
• Connectivity
• Leiden
• LFR graphs

Abstract

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.

Graduation Semester

2023-12

Type of Resource

Thesis

Copyright and License Information

Copyright 2023 Seyedeh Yasamin Tabatabaee

Owning Collections