New bounds on the modularity of $G(n,p)$
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866912341661057024 |
|---|---|
| author | Rybarczyk, Katarzyna Sulkowska, Małgorzata |
| author_facet | Rybarczyk, Katarzyna Sulkowska, Małgorzata |
| contents | Modularity is a parameter indicating the presence of community structure in the graph. Nowadays it lies at the core of widely used clustering algorithms. We study the modularity of the most classical random graph, binomial $G(n,p)$. In 2020 McDiarmid and Skerman proved, taking advantage of the spectral graph theory and a specific subgraph construction by Coja-Oghlan from 2007, that there exists a constant $b$ such that with high probability the modularity of $G(n,p)$ is at most $b/\sqrt{np}$. The obtained constant $b$ is very big and not easily computable. We improve upon this result showing that a constant under $3$ may be derived here. Interesting is the fact that it might be obtained by basic probabilistic tools. We also address the lower bound on the modularity of $G(n,p)$ and improve the results of McDiarmid and Skerman from 2020 using estimates of bisections of random graphs derived by Dembo, Montanari, and Sen in 2017. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_16254 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | New bounds on the modularity of $G(n,p)$ Rybarczyk, Katarzyna Sulkowska, Małgorzata Combinatorics Probability 05C80, 60G99 G.2.1; G.2.2; G.3 Modularity is a parameter indicating the presence of community structure in the graph. Nowadays it lies at the core of widely used clustering algorithms. We study the modularity of the most classical random graph, binomial $G(n,p)$. In 2020 McDiarmid and Skerman proved, taking advantage of the spectral graph theory and a specific subgraph construction by Coja-Oghlan from 2007, that there exists a constant $b$ such that with high probability the modularity of $G(n,p)$ is at most $b/\sqrt{np}$. The obtained constant $b$ is very big and not easily computable. We improve upon this result showing that a constant under $3$ may be derived here. Interesting is the fact that it might be obtained by basic probabilistic tools. We also address the lower bound on the modularity of $G(n,p)$ and improve the results of McDiarmid and Skerman from 2020 using estimates of bisections of random graphs derived by Dembo, Montanari, and Sen in 2017. |
| title | New bounds on the modularity of $G(n,p)$ |
| topic | Combinatorics Probability 05C80, 60G99 G.2.1; G.2.2; G.3 |
| url | https://arxiv.org/abs/2504.16254 |