Modularity of Erdos-Rényi random graphs
For a given graph G, modularity gives a score to each vertex partition, with higher values taken to indicate that the partition better captures community structure in G. The modularity q∗(G) (where 0 ≤ q∗(G) ≤ 1) of the graph G is defined to be the maximum over all vertex partitions of the modularit...
| Main Authors: | , |
|---|---|
| Format: | Conference item |
| Published: |
Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik
2018
|
| _version_ | 1797095478900293632 |
|---|---|
| author | McDiarmid, C Skerman, F |
| author_facet | McDiarmid, C Skerman, F |
| author_sort | McDiarmid, C |
| collection | OXFORD |
| description | For a given graph G, modularity gives a score to each vertex partition, with higher values taken to indicate that the partition better captures community structure in G. The modularity q∗(G) (where 0 ≤ q∗(G) ≤ 1) of the graph G is defined to be the maximum over all vertex partitions of the modularity value. Given the prominence of modularity in community detection, it is an important graph parameter to understand mathematically. For the Erdos-Rényi random graph Gn,pwith n vertices and edge-probability p, the likely modularity has three distinct phases. For np ≤ 1 + o(1) the modularity is 1 + o(1) with high probability (whp), and for np → 1 the modularity is o(1) whp. Between these regions the modularity is non-trivial: for constants 1 < c0 ≤ c1 there exists δ > 0 such that when c0 ≤ np ≤ c1 we have δ < q∗(G) < 1 - δ whp. For this critical region, we show that whp q∗(Gn, p) has order (np)-1/2, in accord with a conjecture by Reichardt and Bornholdt in 2006 (and disproving another conjecture from the physics literature). |
| first_indexed | 2024-03-07T04:28:23Z |
| format | Conference item |
| id | oxford-uuid:cd71fc3d-a646-4bcc-9ead-86cfbaf54f57 |
| institution | University of Oxford |
| last_indexed | 2024-03-07T04:28:23Z |
| publishDate | 2018 |
| publisher | Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik |
| record_format | dspace |
| spelling | oxford-uuid:cd71fc3d-a646-4bcc-9ead-86cfbaf54f572022-03-27T07:28:48ZModularity of Erdos-Rényi random graphsConference itemhttp://purl.org/coar/resource_type/c_5794uuid:cd71fc3d-a646-4bcc-9ead-86cfbaf54f57Symplectic Elements at OxfordSchloss Dagstuhl--Leibniz-Zentrum fuer Informatik2018McDiarmid, CSkerman, FFor a given graph G, modularity gives a score to each vertex partition, with higher values taken to indicate that the partition better captures community structure in G. The modularity q∗(G) (where 0 ≤ q∗(G) ≤ 1) of the graph G is defined to be the maximum over all vertex partitions of the modularity value. Given the prominence of modularity in community detection, it is an important graph parameter to understand mathematically. For the Erdos-Rényi random graph Gn,pwith n vertices and edge-probability p, the likely modularity has three distinct phases. For np ≤ 1 + o(1) the modularity is 1 + o(1) with high probability (whp), and for np → 1 the modularity is o(1) whp. Between these regions the modularity is non-trivial: for constants 1 < c0 ≤ c1 there exists δ > 0 such that when c0 ≤ np ≤ c1 we have δ < q∗(G) < 1 - δ whp. For this critical region, we show that whp q∗(Gn, p) has order (np)-1/2, in accord with a conjecture by Reichardt and Bornholdt in 2006 (and disproving another conjecture from the physics literature). |
| spellingShingle | McDiarmid, C Skerman, F Modularity of Erdos-Rényi random graphs |
| title | Modularity of Erdos-Rényi random graphs |
| title_full | Modularity of Erdos-Rényi random graphs |
| title_fullStr | Modularity of Erdos-Rényi random graphs |
| title_full_unstemmed | Modularity of Erdos-Rényi random graphs |
| title_short | Modularity of Erdos-Rényi random graphs |
| title_sort | modularity of erdos renyi random graphs |
| work_keys_str_mv | AT mcdiarmidc modularityoferdosrenyirandomgraphs AT skermanf modularityoferdosrenyirandomgraphs |