Modularity of regular and treelike graphs

Fiona Skerman, Colin McDiarmid

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

5 Citations (Scopus)

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/√r. 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.
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.
Original languageEnglish
Number of pages20
JournalJournal of Complex Networks
Volume6
DOIs
Publication statusPublished - 2018

Fingerprint

Dive into the research topics of 'Modularity of regular and treelike graphs'. Together they form a unique fingerprint.

Cite this