Eigenvalue Spectra of Modular Networks

Abstract

A large variety of dynamical processes that take place on networks can be expressed in terms of the spectral properties of some linear operator which reflects how the dynamical rules depend on the network topology. Often such spectral features are theoretically obtained by considering only local node properties, such as degree distributions. Many networks, however, possess large-scale modular structures that can drastically influence their spectral characteristics, and which are neglected in such simplified descriptions. Here we obtain in a unified fashion the spectrum of a large family of operators, including the adjacency, Laplacian and normalized Laplacian matrices, for networks with generic modular structure, in the limit of large degrees. We focus on the conditions necessary for the merging of the isolated eigenvalues with the continuous band of the spectrum, after which the planted modular structure can no longer be easily detected by spectral methods. This is a crucial transition point which determines when a modular structure is strong enough to affect a given dynamical process. We show that this transition happens in general at different points for the different matrices, and hence the detectability threshold can vary significantly depending on the operator chosen. Equivalently, the sensitivity to the modular structure of the different dynamical processes associated with each matrix will be different, given the same large-scale structure present in the network. Furthermore, we show that, with the exception of the Laplacian matrix, the different transitions coalesce into the same point for the special case where the modules are homogeneous, but separate otherwise.

5 pages, 5 figures + Supplemental Material; Minor text improvements, updated references and publication information

References in corpus (13)

• Finding community structure in networks using the eigenvectors of matrices
• Synchronization in complex networks
• Stochastic blockmodels and community structure in networks
• Thresholds for epidemic spreading in networks
• Phase transition in the detection of modules in sparse networks
• Graph spectra and the detectability of community structure in networks
• Laplacian spectra of complex networks and random walks on them: Are scale-free architectures really important?
• Community detection and graph partitioning
• Spectra of random graphs with arbitrary expected degrees
• Dynamical and spectral properties of complex networks
• Multifractal Network Generator
• Detectability of communities in heterogeneous networks
• Random Walks on Complex Networks

Cited by in corpus (27)

• Spectral methods for network community detection and graph partitioning
• Hierarchical Block Structures and High-resolution Model Selection in Large Networks
• Enhanced detectability of community structure in multilayer networks through layer aggregation
• Super-resolution community detection for layer-aggregated multilayer networks
• The role of modularity in self-organisation dynamics in biological networks
• Universal Phase Transition in Community Detectability under a Stochastic Block Model
• Origin and implications of zero degeneracy in networks spectra
• A generative model for protein contact networks
• A unifying model for random matrix theory in arbitrary space dimensions
• Spectra of Random Stochastic Matrices and Relaxation in Complex Systems
• Finding the Resistance Distance and Eigenvector Centrality from the Network's Eigenvalues
• Graph Product Multilayer Networks: Spectral Properties and Applications
• Functional control of network dynamics using designed Laplacian spectra
• Spectra of random networks in the weak clustering regime
• Thermodynamics of network model fitting with spectral entropies
• Finite size analysis of the detectability limit of the stochastic block model
• Multi-scale Laplacian community detection in heterogeneous networks
• Structured networks and coarse-grained descriptions: a dynamical perspective
• Effects of clustering heterogeneity on the spectral density of sparse networks
• Sparse Random Block Matrices
• Revisiting Spectral Graph Clustering with Generative Community Models
• Large algebraic connectivity fluctuations in spatial network ensembles imply a predictive advantage from node location information
• Impact of Community Structure on Consensus Machine Learning
• Asymptotics of the spectral radius for directed Chung-Lu random graphs with community structure
• Twists and Turns in the US-North Korea Dialogue: Key Figure Dynamic Network Analysis using News Articles
• Emergence of a spectral gap in a class of random matrices associated with split graphs
• Network-ensemble comparisons with stochastic rewiring and von Neumann entropy