Modularity of Erdős‐Rényi random graphs. Issue 1 (20th March 2020)

• Record Type: Journal Article
• Authors: McDiarmid, Colin; Skerman, Fiona
• Is Part Of: Random structures & algorithms. Volume 57:Issue 1(2020)
• Page Start: 211
• Page End: 243
• Publication Date: 2020-03-20
• Subjects: modularity -- community detection -- random graphs -- robustness; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20910
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract : For a given graph G, each partition of the vertices has a modularity score, with higher values indicating that the partition better captures community structure in G . The modularity q ∗ ( G ) of the graph G is defined to be the maximum over all vertex partitions of the modularity score, and satisfies 0 ≤ q ∗ ( G )<1. Modularity is at the heart of the most popular algorithms for community detection. We investigate the behaviour of the modularity of the Erdős‐Rényi random graph G n, p with n vertices and edge‐probability p . Two key findings are that the modularity is 1+ o (1) with high probability (whp) for np up to 1+ o (1) and no further; and when np ≥ 1 and p is bounded below 1, it has order ( np ) −1/2 whp, in accord with a conjecture by Reichardt and Bornholdt in 2006. We also show that the modularity of a graph is robust to changes in a few edges, in contrast to the sensitivity of optimal vertex partitions.