Premium
On the modularity of 3‐regular random graphs and random graphs with given degree sequences
Author(s) -
Lichev Lyuben,
Mitsche Dieter
Publication year - 2022
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.21080
Subject(s) - mathematics , random graph , combinatorics , bounded function , degree (music) , discrete mathematics , conjecture , graph , giant component , modularity (biology) , mathematical analysis , physics , biology , acoustics , genetics
The modularity of a graph is a parameter that measures its community structure; the higher its value (between 0 and 1), the more clustered the graph is. In this paper we show that the modularity of a random 3‐regular graph is at least 0.667026 asymptotically almost surely (a.a.s.), thereby proving a conjecture of McDiarmid and Skerman. We also improve the a.a.s. upper bound given therein to 0.789998. For a uniformly chosen graphG nover a given bounded degree sequence with average degree d ( G n ) and with | C C ( G n ) | many connected components, we distinguish two regimes with respect to the existence of a giant component. In the subcritical regime, we compute the second term of the modularity. In the supercritical regime, we prove that there is ε > 0 , for which the modularity is a.a.s. at least2 1 − μd ( G n )+ ε , where μ is the asymptotically almost sure limit of| C C ( G n ) | n.