Hierarchical Block Structures and High-Resolution Model Selection in Large Networks

Discovering and characterizing the large-scale topological features in empirical networks are crucial steps in understanding how complex systems function. However, most existing methods used to obtain the modular structure of networks suffer from serious problems, such as being oblivious to the statistical evidence supporting the discovered patterns, which results in the inability to separate actual structure from noise. In addition to this, one also observes a resolution limit on the size of communities, where smaller but well-defined clusters are not detectable when the network becomes large. This phenomenon occurs for the very popular approach of modularity optimization, which lacks built-in statistical validation, but also for more principled methods based on statistical inference and model selection, which do incorporate statistical validation in a formally correct way. Here, we construct a nested generative model that, through a complete description of the entire network hierarchy at multiple scales, is capable of avoiding this limitation and enables the detection of modular structure at levels far beyond those possible with current approaches. Even with this increased resolution, the method is based on the principle of parsimony, and is capable of separating signal from noise, and thus will not lead to the identification of spurious modules even on sparse networks. Furthermore, it fully generalizes other approaches in that it is not restricted to purely assortative mixing patterns, directed or undirected graphs, and ad hoc hierarchical structures such as binary trees. Despite its general character, the approach is tractable and can be combined with advanced techniques of community detection to yield an efficient algorithm that scales well for very large networks.

Popular Summary

Many social, technological, and biological networks are known to organize into modules or “communities,” groups of nodes with a similar connectivity pattern. At first sight, the task of identifying and characterizing these modules seems a simple one. This simplicity is, however, deceiving. Despite a large amount of effort aimed at implementing this task, several fundamental questions still remain open: How should one formally quantify the network’s modular structure? Given a formal characterization, what is the optimal method to identify modules from empirical or simulated data? How should one distinguish modules that arise from some underlying organizational principle from those that occur purely by chance? Why do some existing methods have a “resolution” limit, in other words, fail to detect modules smaller than a certain size? And, how does one overcome such limits? In this work, we show that the concepts of statistical inference and modular hierarchy may hold the key to all these questions, in particular, in terms of providing a principled means for distinguishing structure from noise and a detection method without a resolution limit.

We approach the module-detection problem in two steps. First, we view networks as the results of a nested generative model that is capable of incorporating arbitrary hierarchical modular structures present at different size scales. Indeed, this model serves as a general and formally satisfying definition of arbitrary modular structure and provides a more faithful description for many empirical networks. Based on this view, we then use principled statistical inference methods to detect modules of different sizes and show that this detection approach can reliably distinguish genuine modules from spurious ones arising from noise while at the same time not suffering from severe resolution limits present in other approaches.

Our modular-hierarchy approach does not impose any specific constraints on the types of modular structures, and the statistical inference methods are derived from basic principles rather than being ad hoc. Despite its general character, the approach can be effectively combined with some of the existing community-detection techniques for efficient implementations on very large empirical networks.

Figure 1

Example of a nested stochastic block model with three levels, and a generated network at the bottom. The top-level structure describes a core-periphery network, which is further subdivided in the lower levels.

Figure 2

Model selection results for a PP model with $N={10}^4$, $B_{\mathrm{true}}=100$, and fully isolated blocks ($c=1$), using the model-selection criteria described in the text. The top panel shows the inferred value of $B$ versus the average degree $⟨k⟩$ in the network. The solid lines show the theoretical value according to each criterion, and the data points are direct optimization of the corresponding quantities for actual generated network, averaged over 40 independent realizations. The bottom panel shows the normalized mutual information (NMI) between the inferred and planted partitions. The dashed line marks the threshold $⟨k⟩=1$ where inference becomes impossible for $N\to \infty$.

Figure 3

Parameter region where two isolated blocks with $e_c/2$ internal edges and $n_c=e_c/5$ nodes are detectable as separate blocks [shown schematically in panel (c)], as a function of the average block size $N/B$, and depending on (a) the average degree $⟨k⟩$ with $N={10}^5$ and (b) the number of nodes $N$ with $⟨k⟩=20$. The dashed curves show the boundaries for the nonhierarchical block model, and the solid lines for the hierarchical variant. The line segments on the right-hand side of the plots show the detectability threshold for modularity [14], $e_c^{*}=\sqrt{2E}$. The points marked with stars ($\star$) correspond to the maximum value of $B$ that is detectable in the remaining network with the nonhierarchical model, and the dotted line shows the same quantity for various $⟨k⟩$ values (i.e., the region on the left of this curve corresponds to an overfitting of the remaining network, according to the non-hierarchical criterion). (d) The hierarchical construction used to decide if the two isolated blocks are merged together with the nested model.

Figure 4

Top: NMI between the inferred and true partitions for network realizations of the nested PP model described in the text with $B_1=2$, $L=5$, $⟨k⟩=20$, and $N={10}^4$, as a function of the assortativity strength $c$, both via the standard stochastic block model with $B=16$ and the nested variant with unspecified parameters. The star symbols ($\star$) show the value of $L$ for the inferred hierarchy. All points are averaged over 20 independent realizations. The gray vertical line marks the detectability threshold when $B$ is predetermined, and the red line when the nested model fails to detect any structure. Bottom: Example hierarchies inferred for the values of $c$ indicated in the top panel. The left-hand image shows the network realization itself, and the right-hand one the hierarchical structure [the planted hierarchy corresponds to the one in (a)].

Figure 5

The political blog network of Adamic and Glance [67]. Left: Topmost partition of the hierarchy inferred with the nested model. Right: The same network, using a circular layout, with edge bundling following the inferred hierarchy [68] (indicated also by the square nodes and the node colors). The size of the nodes corresponds to the total degree, and the edge color indicates its direction (from dark to light). Nodes marked with a blue halo were incorrectly classified at the topmost level, according to the accepted partition in Ref. [67].

Figure 6

Large-scale structure of the Internet at the autonomous systems level, as obtained by the nested stochastic block model, displaying a prominent core-periphery architecture. The magnification shows the nodes that belong to the “core” top-level branch, containing AS nodes spread all over the globe, as shown in the map inset. See the Supplemental Material [96] for a higher-resolution version of this figure.

Figure 7

Large-scale structure of the IMDB film-actor network. Each node in this graph represents a lowest-level block in the hierarchy, instead of individual nodes in the graph. The size of the nodes indicates the number of nodes in each group. The hierarchy branch at the top are the actors, and at the bottom are the films. The labels classify each branch according to the most prominent geographical and temporal characteristics found in the database. See the Supplemental Material [96] for a higher-resolution version of this figure.

Figure 8

(a) The average block size $N/B$ obtained using the nonhierarchical model, as a function of $E$, for the empirical networks listed in the bottom table (the Dir. column specifies whether a given network is directed). The dashed line shows a $\sqrt{E}$ slope. (b) The same as (a) but with the nested model. (c) The description length $\mathrm{\Sigma }/E$ for the nested model as a function of $E$. (d) The value of modularity $Q$ as function of $\mathrm{\Sigma }/E$, for the nested model.