Modularity and random graphs
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_ | 1866916971694522368 |
|---|---|
| author | McDiarmid, Colin Skerman, Fiona |
| author_facet | McDiarmid, Colin Skerman, Fiona |
| contents | This work will appear as a chapter in a forthcoming volume titled `Topics in Probabilistic Graph Theory'.
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 $G$ is the maximum over all vertex-partitions of the modularity score, and satisfies $0\leq q^*(G)< 1$. Modularity lies at the heart of the most popular algorithms for community detection. In this chapter we discuss the behaviour of the modularity of various kinds of random graphs, starting with the binomial random graph $G_{n,p}$ with $n$ vertices and edge-probability $p$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_22066 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Modularity and random graphs McDiarmid, Colin Skerman, Fiona Probability Social and Information Networks Combinatorics 05C80, 60C05 This work will appear as a chapter in a forthcoming volume titled `Topics in Probabilistic Graph Theory'. 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 $G$ is the maximum over all vertex-partitions of the modularity score, and satisfies $0\leq q^*(G)< 1$. Modularity lies at the heart of the most popular algorithms for community detection. In this chapter we discuss the behaviour of the modularity of various kinds of random graphs, starting with the binomial random graph $G_{n,p}$ with $n$ vertices and edge-probability $p$. |
| title | Modularity and random graphs |
| topic | Probability Social and Information Networks Combinatorics 05C80, 60C05 |
| url | https://arxiv.org/abs/2509.22066 |