Modularity of networks
Fiona Skerman · Oxford University Research Archive (ORA) (University of Oxford) · 2015
Modularity is a quality function on partitions of a network which may be used to identify highly clustered components. It is commonly used to analyse large real networks, for example in social networks and protein discovery to find communities and related proteins respectively. 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 maximum modularity q*(G) of G (where 0 ≤ q*(G) 1 a constant, functions are constructed with 0 < a(c) < b(c) < 1 and b(c) → 0 as c → ∞ such that whp the maximum modularity is bounded between these functions. Concentration of the maximum modularity about its expectation and structural properties of any optimal partition are also established. Finding the maximum modularity of graph classes helps us understand the behaviour of the modularity function. We study trees, lattices and related graphs. The maximum modularity of a large k-ary tree was shown to be near 1 by Bagrow 2012. This was extended to trees with maximal degree o(n1/5) in Montgolfier et al. 2011. This thesis further extends the result to any tree with maximal degree o(n). Indeed it is shown that the maximum modularity will tend to 1 for any graph where the product of the treewidth and the maximal degree is much less than the number of edges. This shows random planar graphs typically have modularity 1 + o(1). Lower bounds were given in Guimerà et al. 2004 for the maximum modularity of complete sections of the integer lattice and for lattices with extra axis aligned edges included. The maximum modularity of any subgraph of this lattice is shown to be at least the same order of magnitude in the number of edges. This generalises to any graph which can be embedded in Euclidean space such that no edge is too long and no two vertices fall too close together.