On the modularity of 3‐regular random graphs and random graphs with given degree sequences. Issue 4 (23rd February 2022)

• Record Type: Journal Article
• Authors: Lichev, Lyuben; Mitsche, Dieter
• Is Part Of: Random structures & algorithms. Volume 61:Issue 4(2022)
• Page Start: 754
• Page End: 802
• Publication Date: 2022-02-23
• Subjects: modularity -- random graphs with given degree sequence -- random regular graphs; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.21080
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract: 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 graph G n over 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 least 2 1 − μ d ( G n ) + ε, where μ is the asymptotically almost sure limit of | C C ( G n ) | n .