{
  "id": "2007.15574",
  "version": "v1",
  "published": "2020-07-30T16:34:07.000Z",
  "updated": "2020-07-30T16:34:07.000Z",
  "title": "On the modularity of 3-regular random graphs and random graphs with given degree sequences",
  "authors": [
    "Lyuben Lichev",
    "Dieter Mitsche"
  ],
  "comment": "41 pages",
  "categories": [
    "math.PR",
    "math.CO"
  ],
  "abstract": "The modularity of a graph is a parameter introduced by Newman and Girvan measuring its community structure; the higher its value (between $0$ and $1$), the more clustered a graph is. In this paper we show that the modularity of a random $3-$regular graph is at least $0.667026$ asymptotically almost surely (a.a.s.), thereby proving a conjecture of McDiarmid and Skerman stating that a random $3-$regular graph has modularity strictly larger than $\\frac{2}{3}$ a.a.s. We also improve the upper bound given therein by showing that the modularity of such a graph is a.a.s. at most $0.789998$. For a uniformly chosen graph $G_n$ over a given bounded degree sequence with average degree $d(G_n)$ and with $|CC(G_n)|$ many connected components, we distinguish two regimes with respect to the existence of a giant component. In more detail, we precisely compute the second term of the modularity in the subcritical regime. In the supercritical regime, we further prove that there is $\\varepsilon > 0$ depending on the degree sequence, for which the modularity is a.a.s. at least \\begin{equation*} \\dfrac{2\\left(1 - \\mu\\right)}{d(G_n)}+\\varepsilon, \\end{equation*} where $\\mu$ is the asymptotically almost sure limit of $\\dfrac{|CC(G_n)|}{n}$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2020-07-30T16:34:07.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C80"
    ],
    "keywords": [
      "random graphs",
      "regular graph",
      "community structure",
      "bounded degree sequence",
      "sure limit"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 41,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}