Name
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*(G) of the graph G is defined to be the maximum over all vertex partitions of the modularity score, and satisfies 0 <= q*(G)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 >= 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. |
Year | DOI | Venue |
|---|---|---|
2018 | 10.1002/rsa.20910 | RANDOM STRUCTURES & ALGORITHMS |
Keywords | DocType | Volume |
modularity,community detection,random graphs,robustness | Journal | 57.0 |
Issue | ISSN | Citations |
1.0 | 1042-9832 | 0 |
PageRank | References | Authors |
0.34 | 0 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Colin McDiarmid | 1 | 1071 | 167.05 |
| Fiona Skerman | 2 | 8 | 4.26 |