Super-Resolution Community Detection for Layer-Aggregated Multilayer Networks

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 $N$ nodes and $L$ 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 $K^{*}$. When layers are aggregated via a summation, we obtain $K^{*}\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^{*}$ 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.

Popular Summary

Networks can represent relationships between the online behaviors of individuals such as emailing, file sharing, and purchasing history. Small-community detection, which attempts to identify anomalous clusters within such networks, has important applications in cybersecurity for detecting attacks, intrusions, and fraud. Before analyzing the structural patterns of these networks, data are often preprocessed using a variety of techniques. While there is a wealth of theory for network analysis methodology, most preprocessing is done on an ad hoc basis, and there is significant need for an encompassing theory bridging these two steps.

Here, we focus on the task of detecting small communities in large multilayer networks, wherein “layers” encode different types of connections, such as different instances in time. Because it can be beneficial to aggregate layers that are similar, we analyze the effects of layer aggregation on the detectability of communities. We analyze a novel, important metric: the number of layers a community must persist across in order for aggregation to benefit detection. In addition, we introduce layer aggregation with thresholding as a nonlinear data filter, showing that this preprocessing step can allow super-resolution detection of communities that are otherwise too small to detect.

This work paves the way for a new class of holistic methods that simultaneously address both the data preprocessing and network analysis steps. Such an approach will lead to improved pattern analytics in cybersecurity and broadly benefit the analysis of diverse networks arising in the social, biological, and engineering sciences.

Figure 1

Preprocessing networks (including multilayer representations of temporal networks) often involves aggregating network data into bins (or time windows). We study how many layers must contain a community in order for aggregation to enhance its detection and introduce layer aggregation with thresholding as a filter enabling super-resolution community detection.

Figure 2

Eigenvector localization yields detectability phase transition. (a) Entries $v_i^{(r)}$ (symbols) of a dominant eigenvector of the modularity matrix for the summation network of a multilayer network with a hidden community of size $K_r$. Parameters include $T_r=2$, $L=16$, $N=10^4$, $\rho =1$, and the edge probabilities $\{p_l\}$ of layers are Gaussian distributed with mean $⟨p_l⟩=0.01$ and standard deviation ${\sigma }_p=0.001$. To allow visualization, we assume nodes $i\in \{1,\dots ,K\}$ are in the community, and we only visualize $v_i^{(r)}$ for nodes $i\in \{1,100\}$. As shown by the illustration, as $K_r$ increases, ${\mathbf{v}}^{(r)}$ aligns with the indicator vector ${\mathbf{u}}^{(r)}$, which is nonzero only for the $K_r\ll N$ entries $u_i^{(r)}$ that correspond to nodes in the community, ${\mathcal{K}}_r$. (b) Observed (symbols) and predicted (curves) values of $|⟨{\mathbf{v}}^{(r)},{\mathbf{u}}^{(r)}⟩{|}^2$ given by Eq. (10) quantify this localization phenomenon. Arrows indicate the values of $K$ used for panel (a). The critical size $K_r^{*}$ such that $|⟨{\mathbf{v}}^{(r)},{\mathbf{u}}^{(r)}⟩{|}^2=0$ for $K_r\le K_r^{*}$, whereas $|⟨{\mathbf{v}}^{(r)},{\mathbf{u}}^{(r)}⟩{|}^2>0$ for $K_r>K_r^{*}$ marks a phase transition—that is, both in terms of eigenvector localization and detectability of the community.

Figure 3

Influence of community persistence $T_r$ on eigenvector localization for summation-based layer aggregation. (a) Observed (symbols) and predicted values of $|⟨{\mathbf{v}}^{(r)},{\mathbf{u}}^{(r)}⟩{|}^2$ given by Eq. (10) (curves) vs $K_r$ for $T_r\in \{1,2,4,8\}$. Open symbols indicate the parameters used in Fig. 2, whereas filled symbols indicate when the layers’ edge probabilities $\{p_l\}$ are drawn uniformly from [0, 0.02]; we plot the mean value of $|⟨{\mathbf{v}}^{(r)},{\mathbf{u}}^{(r)}⟩{|}^2$ across 10 choices for the sets ${\mathcal{K}}_r$ and ${\mathcal{T}}_r$. (b) Critical size $K_r^{*}$ given by Eq. (11) vs $L$ for fixed $T_r$ (dashed line) and $T_r=L$ (solid line). As indicated by Eq. (12), layer aggregation by summation can enhance or inhibit detection depending on whether or not the scaling for $T_r(L)$ exceeds $\mathcal{O}(L^{1/2})$.

Figure 4

Effective edge probabilities for threshold-based layer aggregation. Observed (symbols) and predicted values given by Eqs. (13) and (15) (curves) for the effective edge probability of the background network, ${\widehat{p}}^{(\tilde{L})}$, and for a community, ${\widehat{\rho }}_r^{(\tilde{L})}$, as a function of $\tilde{L}$. Network parameters include $N=10^4$, $L=16$, $T=5$, and ${\sigma }_p=0.001$ and either (a) $⟨p_l⟩=0.5$ or (b) $⟨p_l⟩=0.01$. Note that for the sparse network in panel (b), ${\widehat{\rho }}^{(\tilde{L})}$ undergoes an abrupt drop when $\tilde{L}$ surpasses $T_r=5$.

Figure 5

Detectability phase transitions for threshold-based layer aggregation. We plot $|⟨{\mathbf{v}}^{(r)},{\mathbf{u}}^{(r)}⟩{|}^2$ vs community size $K_r$ with identical parameters to those used to produce Fig. 4 except with selected choices for the threshold $\tilde{L}$.

Figure 6

Super-resolution community detection for threshold-based layer aggregation. We plot ${\widehat{K}}_r^{*}$ given by Eq. (18) as a function of $\tilde{L}$ for $p\in \{0.01,0.05,0.2,0.5\}$, $N=10^4$, $\rho =1$, ${\sigma }_p=0.001$, $L=16$, and either (a) $T_r=5$ or (b) $T_r=10$. Note that the $\tilde{L}$ value yielding the minimum ${\widehat{K}}_r^{*}$ occurs at $\tilde{L}=T_r$ (vertical dotted lines) for sparse networks, whereas it increases with increasing $p$ [e.g., compare $p=0.01$ and $p=0.5$ in panel (b)]. The horizontal lines on the right edge of the panels indicate $K_r^{*}$ given by Eq. (11) for summation networks. Importantly, thresholding can potentially decrease ${\widehat{K}}_r^{*}$ by many orders of magnitude as compared to $K_r^{*}$.

Figure 7

Detectability of small communities in temporal networks with summation-based binning into time windows. (a) Illustration of a temporal network with $L=32$ time layers and hidden communities that persist across different time layers. The shaded region indicates a bin, or time window, of size $w\le L$ at time $t$ for which the layers will be aggregated, which is a process that can be used to discretize and/or smooth the network data. The bin contains layers ${\mathcal{W}}_w(t)=\{t-(w-1)/2,\dots ,t+(w-1)/2\}$. (b) We illustrate by color the values $|⟨{\mathbf{v}}^{(r)},{\mathbf{u}}^{(r)}⟩{|}^2$ for the aggregation of layers across bins ${\mathcal{W}}_w(t)$ for each of the four communities $r\in \{1,2,3,4\}$. In particular, we show Eq. (10) under the variable substitutions $T_r({\mathcal{W}}_w(t))\mapsto T$ and $w\mapsto L$, where $T_r({\mathcal{W}}_w(t))$ is the number of layers in which community $r$ is present in bin ${\mathcal{W}}_w(t)$. Layer aggregation across each bin was implemented by summation. We study a temporal network with $N=10^4$, $L=32$, $p=0.01$, ${\sigma }_p=0.001$, and we show results for several bin widths $w\in \{1,3,5,7,9\}$. The hidden communities all contain $K_r=8$ nodes and have different persistent lengths $T_r$ as depicted in panel (a). The green arrows indicate, for each $r$, the bin location and $w$ value at which $|⟨{\mathbf{v}}^{(r)},{\mathbf{u}}^{(r)}⟩{|}^2$ obtains its maximum.

Figure 8

Detectability of small communities in temporal networks with time-window binning by summation and thresholding. We illustrate by color the values $|⟨{\widehat{\mathbf{v}}}^{(r)},{\mathbf{u}}^{(r)}⟩{|}^2$ given by Eq. (16) for each of the four communities $r\in \{1,2,3,4\}$ with the variable substitutions $T_r({\mathcal{W}}_w(t))\mapsto T$ and $w\mapsto L$ into Eqs. (13)–(18). Results are shown for bins of width $w\in \{1,3,5,7,9\}$ for a temporal network with $N=10^4$ nodes, $L=32$ time layers, and hidden communities as depicted in Fig. 7. The communities each contain $K_r=K=8$ nodes and have different persistence lengths $T_r$. Layer aggregation across each bin was implemented by summation and thresholding at $\tilde{L}$. Panels (a)–(c) respectively indicate the choices $\tilde{L}=w$, $\tilde{L}=0.8w$, and $\tilde{L}=0.5w$. The violet box in panel (b) indicates combinations of thresholds and bin sizes that yield accurate detection of all four communities. We stress, however, that since the detectability-limit criterion given by Eq. (18) depends on a complex interplay between the community and network characteristics, one should not, in general, expect there to exist a single best combination for all communities.