Correcting for Granularity Bias in Modularity-Based Community Detection Methods

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

Abstract

Maximizing modularity is currently the most widely-used community detection method in applications. Modularity comes with a parameter that indirectly controls the granularity of the resulting clustering. Moreover, one can choose this parameter in such a way that modularity maximization becomes equivalent to maximizing the likelihood of a stochastic block model. Thus, this method is statistically justified, while at the same time, it is known to have a bias towards fine-grained clusterings. In this work, we introduce a heuristic to correct for this bias. This heuristic is based on prior work where modularity is described in geometric terms. This has led to a broad generalization of modularity-based community detection methods, and the heuristic presented in this paper applies to each of them. We justify the heuristic by describing a relation between several distances that we observe to hold in many instances. We prove that, assuming the validity of this relation, our heuristic leads to a clustering of the same granularity as the ground-truth clustering. We compare our heuristic to likelihood-based community detection methods on several synthetic graphs and show that our method indeed results in clusterings with granularity closer to the granularity of the ground-truth clustering. Moreover, our heuristic often outperforms likelihood maximization in terms of similarity to the ground-truth clustering.

Original languageEnglish
Title of host publicationAlgorithms and Models for the Web Graph - 18th International Workshop, WAW 2023, Proceedings
EditorsMegan Dewar, François Théberge, Paweł Prałat, Przemysław Szufel, Małgorzata Wrzosek
PublisherSpringer
Pages1-18
Number of pages18
ISBN (Print)9783031322952
DOIs
Publication statusPublished - 2023
Event18th International Workshop on Algorithms and Models for the Web Graph, WAW 2023 - Toronto, Canada
Duration: 23 May 202326 May 2023

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume13894 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference18th International Workshop on Algorithms and Models for the Web Graph, WAW 2023
Country/TerritoryCanada
CityToronto
Period23/05/2326/05/23

Bibliographical note

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

Funding

Supported by the Netherlands Organisation for Scientific Research (NWO) through the Gravitation NETWORKS grant no. 024.002.003.

FundersFunder number
Nederlandse Organisatie voor Wetenschappelijk Onderzoek024.002.003

    Keywords

    • Clustering
    • Community detection
    • Likelihood maximization
    • Modularity

    Fingerprint

    Dive into the research topics of 'Correcting for Granularity Bias in Modularity-Based Community Detection Methods'. Together they form a unique fingerprint.

    Cite this