Modularity in random regular graphs and lattices

Colin McDiarmid, Fiona Skerman

Research output: Contribution to journalArticle (Academic Journal)peer-review

6 Citations (Scopus)
1 Downloads (Pure)

Abstract

Given a graph G, the modularity of a partition of the vertex set measures the extent to which edge density is higher within parts than between parts; and the modularity of G is the maximum modularity of a partition.

We give an upper bound on the modularity of r-regular graphs as a function of the edge expansion (or isoperimetric number) under the restriction that each part in our partition has a sub-linear numbers of vertices. This leads to results for random r-regular graphs. In particular we show the modularity of a random cubic graph partitioned into sub-linear parts is almost surely in the interval (0.66, 0.88).

The modularity of a complete rectangular section of the integer lattice in a fixed dimension was estimated in Guimer et. al. [R. Guimerà, M. Sales-Pardo and L.A. Amaral, Modularity from fluctuations in random graphs and complex networks, Phys. Rev. E 70 (2) (2004) 025101]. We extend this result to any subgraph of such a lattice, and indeed to more general graphs
Original languageEnglish
Pages (from-to)431-437
Number of pages7
JournalElectronic Notes in Discrete Mathematics
Volume43
Early online date3 Sep 2013
DOIs
Publication statusPublished - 5 Sep 2013

Keywords

  • edge expansion
  • isoperimetric number
  • lattices
  • regular graphs
  • random regular graphs
  • random cubic graphs

Fingerprint Dive into the research topics of 'Modularity in random regular graphs and lattices'. Together they form a unique fingerprint.

Cite this