Modularity of Erdős-Rényi random graphs
| Autor: | McDiarmid, C, Skerman, F |
|---|---|
| Rok vydání: | 2018 |
| Předmět: | |
| DOI: | 10.48550/arxiv.1808.02243 |
| Popis: | 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\leq 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 \geq 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. 35 pages, to appear in Random Structures and Algorithms |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|