Super-resolution community detection for layer-aggregated multilayer networks

Abstract

Applied network science often involves preprocessing network data before applying a network-analysis method, and there is typically a theoretical disconnect between these steps. For example, it is common to aggregate time-varying network data into windows prior to analysis, and the tradeoffs of this preprocessing are not well understood. Focusing on the problem of detecting small communities in multilayer networks, we study the effects of layer aggregation by developing random-matrix theory for modularity matrices associated with layer-aggregated networks with $N$ nodes and $L$ layers, which are drawn from an ensemble of Erdős-Rényi networks. We study phase transitions in which eigenvectors localize onto communities (allowing their detection) and which occur for a given community provided its size surpasses a detectability limit $K^{\ast }$. When layers are aggregated via a summation, we obtain $K^{\ast }\propto \mathcal{O}(\sqrt{NL}/T)$, where $T$ is the number of layers across which the community persists. Interestingly, if $T$ is allowed to vary with $L$ then summation-based layer aggregation enhances small-community detection even if the community persists across a vanishing fraction of layers, provided that $T/L$ decays more slowly than $\mathcal{O}(L^{-1/2})$. Moreover, we find that thresholding the summation can in some cases cause $K^{\ast }$ to decay exponentially, decreasing by orders of magnitude in a phenomenon we call super-resolution community detection. That is, layer aggregation with thresholding is a nonlinear data filter enabling detection of communities that are otherwise too small to detect. Importantly, different thresholds generally enhance the detectability of communities having different properties, illustrating that community detection can be obscured if one analyzes network data using a single threshold.

11 pages, 8 figures

References in corpus (14)

• Maps of random walks on complex networks reveal community structure
• Benchmark graphs for testing community detection algorithms
• The structure and dynamics of multilayer networks
• Resolution limit in community detection
• Hierarchical structure and the prediction of missing links in networks
• Layer aggregation and reducibility of multilayer interconnected networks
• Extracting the hierarchical organization of complex systems
• Phase transition in the detection of modules in sparse networks
• Graph spectra and the detectability of community structure in networks
• Geometric correlations mitigate the extreme vulnerability of multiplex networks against targeted attacks
• Universality in the spectral and eigenfunction properties of random networks
• Correlations between weights and overlap in ensembles of weighted multiplex networks
• Limitations in the spectral method for graph partitioning: detectability threshold and localization of eigenvectors
• Scaling Properties of Multilayer Random Networks

Cited by in corpus (10)

• A Framework for the Construction of Generative Models for Mesoscale Structure in Multilayer Networks
• Multilayer Network Science: from Cells to Societies
• Layer Communities in Multiplex Networks
• Introduction to correlation networks: Interdisciplinary approaches beyond thresholding
• Community detection in multiplex networks based on orthogonal nonnegative matrix tri-factorization
• Transient crosslinking kinetics optimize gene cluster interactions
• Multiplex Markov Chains: Convection Cycles and Optimality
• Network construction: A learning framework through localizing principal eigenvector
• Network-ensemble comparisons with stochastic rewiring and von Neumann entropy
• Random Matrix Analysis of Multiplex Networks