×

Modularity of complex networks models. (English) Zbl 1398.05188

Bonato, Anthony (ed.) et al., Algorithms and models for the web graph. 13th international workshop, WAW 2016, Montreal, QC, Canada, December 14–15, 2016. Proceedings. Cham: Springer (ISBN 978-3-319-49786-0/pbk; 978-3-319-49787-7/ebook). Lecture Notes in Computer Science 10088, 115-126 (2016).
Summary: 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 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.
For the entire collection see [Zbl 1350.68010].

MSC:

05C82 Small world graphs, complex networks (graph-theoretic aspects)
PDFBibTeX XMLCite
Full Text: DOI arXiv