Modularity of Erdős-Rényi random graphs

DOI10.1002/RSA.20910MaRDI QIDQ5120747zbMATH OpenOpenAlexFDO

Authors Fiona Skerman, Colin McDiarmid

Publication date 16 September 2020

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1808.02243

zbMATH Keywords

community detectionmodularityrandom graphsrobustness

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80)

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^{\ast }(G)$ of the graph $G$ is defined to be the maximum over all vertex partitions of the modularity score, and satisfies $0leq{q}^{\ast }(G)<1$. Modularity is at the heart of the most popular algorithms for community detection. We investigate the behaviour of the modularity of the ErdH{o}s-R'enyi 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 $npgeq1$ 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.

Recommendations

• Modularity of Erdős-Rényi random graphs
• Modularity in several random graph models
• On the modularity of 3‐regular random graphs and random graphs with given degree sequences
• New modularity bounds for graphs \(G(n,r,s)\) and \(G_p(n,r,s)\)
• Modularity of regular and treelike graphs

Cites work

• A note on graphs whose largest eigenvalues of the modularity matrix equals zero
• A Random Graph Model for Power Law Graphs
• An algebraic analysis of the graph modularity
• Asymptotic modularity of some graph classes
• Bisecting sparse random graphs
• Communities in Networks
• Degree sequences of random digraphs and bipartite graphs
• scientific article; zbMATH DE number 3168330 (Why is no real title available?)
• scientific article; zbMATH DE number 4170917 (Why is no real title available?)
• scientific article; zbMATH DE number 7378595 (Why is no real title available?)
• scientific article; zbMATH DE number 964896 (Why is no real title available?)
• Modularity in several random graph models
• Modularity of Erdős-Rényi random graphs
• Modularity of regular and treelike graphs
• Network modularity in the presence of covariates
• Networks. An introduction.
• On Finding Graph Clusterings with Maximum Modularity
• On the Laplacian Eigenvalues of G_n,p
• Reconstruction and estimation in the planted partition model
• Spectral properties of modularity matrices
• Susceptibility in subcritical random graphs
• The Spectra of Random Graphs with Given Expected Degrees
• When are networks truly modular?

Cited in

(17)

• Modularity in several random graph models
• New modularity bounds for graphs \(G(n,r,s)\) and \(G_p(n,r,s)\)
• Spectrum of Johnson graphs
• Ensemble nonequivalence in random graphs with modular structure
• scientific article; zbMATH DE number 1943957 (Why is no real title available?)
• Modularity of Erdős-Rényi random graphs
• scientific article; zbMATH DE number 7378595 (Why is no real title available?)
• Modularity Maximization for Graphons
• On the modularity of 3‐regular random graphs and random graphs with given degree sequences
• Correcting for granularity bias in modularity-based community detection methods
• Modularity of minor‐free graphs
• Modularity in planted partition model
• Modularity of some distance graphs
• Insights into the structured coordination game with neutral options through simulation
• Modularity and graph expansion
• On graphs with modularity zero or near-zero
• The parameterised complexity of computing the maximum modularity of a graph

This page was built for publication: Modularity of Erdős-Rényi random graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5120747)