Modularity of regular and treelike graphs
arXiv:1606.09101 · doi:10.1093/comnet/cnx046
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 -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 , and for random -regular graphs with large it usually is of order . 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 mentioned above on the modularity of random cubic graphs.
arXiv comment25 pages
References in corpus (15)
- Fast unfolding of communities in large networks
- Finding and evaluating community structure in networks
- Community detection in graphs
- Resolution limit in community detection
- Statistical Mechanics of Community Detection
- Community detection in networks: A user guide
- Modularity from Fluctuations in Random Graphs and Complex Networks
- Limits of modularity maximization in community detection
- When are networks truly modular?
- Extremal Cuts of Sparse Random Graphs
- Communities and bottlenecks: Trees and treelike networks have high modularity
- On the Complexity of Newman's Community Finding Approach for Biological and Social Networks
- Lower bounds for the isoperimetric numbers of random regular graphs
- Network modularity in the presence of covariates
- When the largest eigenvalue of the modularity and normalized modularity matrix is zero