Taylor Dane, Caceres Rajmonda S, Mucha Peter J
Carolina Center for Interdisciplinary Applied Mathematics, Department of Mathematics, University of North Carolina, Chapel Hill, North Carolina 27599, USA.
Department of Mathematics, University at Buffalo, State University of New York, Buffalo, New York 14260, USA.
Phys Rev X. 2017 Jul-Sep;7(3). doi: 10.1103/PhysRevX.7.031056. Epub 2017 Sep 26.
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 trade-offs 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 nodes and layers, which are drawn from an ensemble of Erdős-Rényi networks with communities planted in subsets of layers. 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 . When layers are aggregated via a summation, we obtain [Formula: see text], where is the number of layers across which the community persists. Interestingly, if is allowed to vary with , then summation-based layer aggregation enhances small-community detection even if the community persists across a vanishing fraction of layers, provided that decays more slowly than 𝒪(). Moreover, we find that thresholding the summation can, in some cases, cause to decay exponentially, decreasing by orders of magnitude in a phenomenon we call super-resolution community detection. In other words, 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.
应用网络科学通常涉及在应用网络分析方法之前对网络数据进行预处理，而这些步骤之间通常存在理论上的脱节。例如，在分析之前将随时间变化的网络数据聚合到窗口中是很常见的，而这种预处理的权衡并没有得到很好的理解。针对多层网络中检测小社区的问题，我们通过为与具有(n)个节点和(l)层的层聚合网络相关的模块化矩阵发展随机矩阵理论，研究层聚合的影响，这些网络是从在层的子集中植入社区的厄多斯 - 雷尼网络集合中抽取的。我们研究特征向量定位到社区（从而允许检测它们）的相变，并且对于给定的社区，当它的大小超过可检测性极限(\tau)时就会发生这种相变。当通过求和进行层聚合时，我们得到(\tau = \frac{c}{\log(n/l)})，其中(c)是社区持续存在的层数。有趣的是，如果允许(c)随(n)和(l)变化，则基于求和的层聚合增强了小社区检测，即使社区仅在消失比例的层中持续存在，前提是(c)的衰减比(O(1))慢。此外，我们发现对求和进行阈值处理在某些情况下会导致(\tau)呈指数衰减，在一种我们称为超分辨率社区检测的现象中下降几个数量级。换句话说，带阈值处理的层聚合是一种非线性数据滤波器，能够检测否则太小而无法检测的社区。重要的是，不同的阈值通常会增强具有不同属性的社区的可检测性，这表明如果使用单个阈值分析网络数据，社区检测可能会被掩盖。
