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 (36)

• The structure and function of complex networks
• Finding and evaluating community structure in networks
• Community detection in graphs
• Maps of random walks on complex networks reveal community structure
• Multilayer Networks
• Benchmark graphs for testing community detection algorithms
• The structure and dynamics of multilayer networks
• Resolution limit in community detection
• Temporal Networks
• Community Structure in Time-Dependent, Multiscale, and Multiplex Networks
• Hierarchical structure and the prediction of missing links in networks
• Dynamic reconfiguration of human brain networks during learning
• 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
• Fundamental structures of dynamic social networks
• Graph spectra and the detectability of community structure in networks
• Localization and centrality in networks
• The largest eigenvalues of finite rank deformation of large Wigner matrices: convergence and nonuniversality of the fluctuations
• Hidden geometric correlations in real multiplex networks
• Distinct types of eigenvector localization in networks
• Clustering Network Layers With the Strata Multilayer Stochastic Block Model
• Detectability thresholds and optimal algorithms for community structure in dynamic networks
• Enhanced detectability of community structure in multilayer networks through layer aggregation
• Eigenvalue Spectra of Modular Networks
• Geometric correlations mitigate the extreme vulnerability of multiplex networks against targeted attacks
• Detectability of communities in heterogeneous networks
• A Spectral Framework for Anomalous Subgraph Detection
• Universality in the spectral and eigenfunction properties of random networks
• Phase Transitions in Spectral Community Detection
• 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
• Centrality metrics and localization in core-periphery networks
• Scaling Properties of Multilayer Random Networks
• Detectability of the spectral method for sparse graph partitioning
• Percolation-induced exponential scaling in the large current tails of random resistor 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