Modularity of Erdős-Rényi random graphs

F Skerman, Colin McDiarmid

Research output: Contribution to journalArticle (Academic Journal)peer-review

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
Original languageEnglish
Number of pages33
JournalRandom Structures and Algorithms
Early online dateMar 2020
DOIs
Publication statusE-pub ahead of print - Mar 2020

Keywords

  • modularity
  • community detection
  • robustness
  • random graphs

Fingerprint Dive into the research topics of 'Modularity of Erdős-Rényi random graphs'. Together they form a unique fingerprint.

Cite this