Modularity of regular and treelike graphs

DOI10.1093/COMNET/CNX046MaRDI QIDQ3388894zbMATH OpenOpenAlexFDO

Authors Fiona Skerman, Colin McDiarmid

Publication date 7 May 2021

Published in Journal of Complex Networks (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1606.09101

zbMATH Keywords

community detectionedge expansionNewman-Girvan modularitytreewidth

Mathematics Subject Classification ID

Small world graphs, complex networks (graph-theoretic aspects) (05C82) Graph algorithms (graph-theoretic aspects) (05C85)

Abstract: Clustering algorithms for large networks typically use modularity values to test which partitions of the vertex set better represent structure in the data. The modularity of a graph is the maximum modularity of a partition. We consider the modularity of two kinds of graphs. For $r$-regular graphs with a given number of vertices, we investigate the minimum possible modularity, the typical modularity, and the maximum possible modularity. In particular, we see that for random cubic graphs the modularity is usually in the interval $(0.666,0.804)$, and for random $r$-regular graphs with large $r$ it usually is of order $1/sqrtr$. These results help to establish baselines for statistical tests on regular graphs. The modularity of cycles and low degree trees is known to be close to 1: we extend these results to `treelike' graphs, where the product of treewidth and maximum degree is much less than the number of edges. This yields for example the (deterministic) lower bound $0.666$ mentioned above on the modularity of random cubic graphs.

Recommendations

• A characterization of modularity in graphs
• Modularity of cycles and paths in graphs
• Modular irregularity strength of graphs
• Modularity of some distance graphs
• An algebraic analysis of the graph modularity
• Modularity of minor‐free graphs
• Asymptotic modularity of some graph classes
• Modular decomposition of graphs and the distance preserving property
• Modulus on graphs as a generalization of standard graph theoretic quantities
• Characterization of expansion-related properties of modular graphs

Cited in

(18)

• New modularity bounds for graphs \(G(n,r,s)\) and \(G_p(n,r,s)\)
• Spectrum of Johnson graphs
• Exact modularity of line graphs of complete graphs
• Asymptotic modularity of some graph classes
• Modularity of Erdős-Rényi random graphs
• scientific article; zbMATH DE number 7378595 (Why is no real title available?)
• Modularity of Erdős-Rényi random graphs
• On Module-Composed Graphs
• On the modularity of 3‐regular random graphs and random graphs with given degree sequences
• Modularity of minor‐free graphs
• Characterization of expansion-related properties of modular graphs
• Modularity in planted partition model
• Modularity of some distance graphs
• Fractal networks: topology, dimension, and complexity
• Modularity and graph expansion
• Modularity clustering parameterized by max leaf number
• On graphs with modularity zero or near-zero
• The parameterised complexity of computing the maximum modularity of a graph

This page was built for publication: Modularity of regular and treelike graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3388894)