Title: Modularity of complex networks models,
Abstract: Modularity is designed to measure the strength of division of a network into
clusters (known also as communities). Networks with high modularity have dense
connections between the vertices within clusters but sparse connections between
vertices of different clusters. As a result, modularity is often used in
optimization methods for detecting community structure in networks, and so it
is an important graph parameter from a practical point of view. Unfortunately,
many existing non-spatial models of complex networks do not generate graphs
with high modularity; on the other hand, spatial models naturally create
clusters. We investigate this phenomenon by considering a few examples from
both sub-classes. We prove precise theoretical results for the classical model
of random d-regular graphs as well as the preferential attachment model, and
contrast these results with the ones for the spatial preferential attachment
(SPA) model that is a model for complex networks in which vertices are embedded
in a metric space, and each vertex has a sphere of influence whose size
increases if the vertex gains an in-link, and otherwise decreases with time.
The results obtained in this paper can be used for developing statistical tests
for models selection and to measure statistical significance of clusters
observed in complex networks.