Modularity with a more accurate baseline model

Brian L. Chang; Piet Van Mieghem

doi:10.1103/PhysRevE.111.044317

Modularity with a more accurate baseline model

Brian L. Chang^*, Piet Van Mieghem

^*Corresponding author for this work

Network Architectures and Services

Research output: Contribution to journal › Article › Scientific › peer-review

Abstract

We derive an expression for the exact probability Pr[i∼j] of a link between a node i with degree di and a node j with degree dj in a graph belonging to the class of Erdos-Rényi G(N,L) random graphs with N nodes and L links. The probability Pr[i∼j] is commonly approximated as didj2L and appears in the formula of Newman's modularity, which plays a crucial rule in community detection in networks. We show that, when applied to graphs not belonging to the class of Erdos-Rényi random graphs, our formula for Pr[i∼j] is considerably more accurate than didj2L and leads to the detection of different clusters or partitions than the original modularity formula.

Original language	English
Article number	044317
Number of pages	11
Journal	Physical Review E
Volume	111
Issue number	4
DOIs	https://doi.org/10.1103/PhysRevE.111.044317
Publication status	Published - 2025

Bibliographical note

Green Open Access added to TU Delft Institutional Repository ‘You share, we take care!’ – Taverne project https://www.openaccess.nl/en/you-share-we-take-care
Otherwise as indicated in the copyright section: the publisher is the copyright holder of this work and the author uses the Dutch legislation to make this work public.

Access to Document

10.1103/PhysRevE.111.044317

Cite this

@article{4d6cb8ea0f734b3c954d60483909f73e,

title = "Modularity with a more accurate baseline model",

abstract = "We derive an expression for the exact probability Pr[i∼j] of a link between a node i with degree di and a node j with degree dj in a graph belonging to the class of Erdos-R{\'e}nyi G(N,L) random graphs with N nodes and L links. The probability Pr[i∼j] is commonly approximated as didj2L and appears in the formula of Newman's modularity, which plays a crucial rule in community detection in networks. We show that, when applied to graphs not belonging to the class of Erdos-R{\'e}nyi random graphs, our formula for Pr[i∼j] is considerably more accurate than didj2L and leads to the detection of different clusters or partitions than the original modularity formula.",

author = "Chang, {Brian L.} and {Van Mieghem}, Piet",

note = "Green Open Access added to TU Delft Institutional Repository {\textquoteleft}You share, we take care!{\textquoteright} – Taverne project https://www.openaccess.nl/en/you-share-we-take-care Otherwise as indicated in the copyright section: the publisher is the copyright holder of this work and the author uses the Dutch legislation to make this work public.",

year = "2025",

doi = "10.1103/PhysRevE.111.044317",

language = "English",

volume = "111",

journal = "Physical Review E",

issn = "2470-0045",

publisher = "American Physical Society",

number = "4",

}

TY - JOUR

T1 - Modularity with a more accurate baseline model

AU - Chang, Brian L.

AU - Van Mieghem, Piet

N1 - Green Open Access added to TU Delft Institutional Repository ‘You share, we take care!’ – Taverne project https://www.openaccess.nl/en/you-share-we-take-care Otherwise as indicated in the copyright section: the publisher is the copyright holder of this work and the author uses the Dutch legislation to make this work public.

PY - 2025

Y1 - 2025

N2 - We derive an expression for the exact probability Pr[i∼j] of a link between a node i with degree di and a node j with degree dj in a graph belonging to the class of Erdos-Rényi G(N,L) random graphs with N nodes and L links. The probability Pr[i∼j] is commonly approximated as didj2L and appears in the formula of Newman's modularity, which plays a crucial rule in community detection in networks. We show that, when applied to graphs not belonging to the class of Erdos-Rényi random graphs, our formula for Pr[i∼j] is considerably more accurate than didj2L and leads to the detection of different clusters or partitions than the original modularity formula.

AB - We derive an expression for the exact probability Pr[i∼j] of a link between a node i with degree di and a node j with degree dj in a graph belonging to the class of Erdos-Rényi G(N,L) random graphs with N nodes and L links. The probability Pr[i∼j] is commonly approximated as didj2L and appears in the formula of Newman's modularity, which plays a crucial rule in community detection in networks. We show that, when applied to graphs not belonging to the class of Erdos-Rényi random graphs, our formula for Pr[i∼j] is considerably more accurate than didj2L and leads to the detection of different clusters or partitions than the original modularity formula.

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

U2 - 10.1103/PhysRevE.111.044317

DO - 10.1103/PhysRevE.111.044317

M3 - Article

AN - SCOPUS:105004221006

SN - 2470-0045

VL - 111

JO - Physical Review E

JF - Physical Review E

IS - 4

M1 - 044317

ER -

Modularity with a more accurate baseline model

Abstract

Bibliographical note

Access to Document

Other files and links

Embargoed Document

Fingerprint

Cite this