Hierarchical block structures and high-resolution model selection in large networks

By Tiago P. Peixoto. arXiv.org, 2013

431 citations recorded by the source corpus.

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 not only 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.

Subfields: Cognitive Neuroscience, Condensed Matter Physics, Statistical and Nonlinear Physics

View Paper: https://www.semanticscholar.org/paper/41ae5e5860ab27e95e9a8e9dd2dabc5a4815b6f0

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Cognitive Neuroscience

In Condensed Matter Physics

In Statistical and Nonlinear Physics

Citations in the corpus

Multilayer networks (2013, background): “One can also use multilayer ideas in the formulation of a stochastic blockmodel [264] or start with a monoplex network and try to assign layers to construct a multilayer-network representation [83,270].”
Learning Latent Block Structure in Weighted Networks (2014, neutral): “odern standards, and thus should be applicable to networks of millions of vertices or more. Alternative algorithms such as those based on Markov chain Monte Carlo for unweighted networks are possible [8, 29]; however, each must contend with several technical problems presented by edge weight distrib”
Community detection in networks: A user guide (2016, methodology): “The generative model is an extension of the hierarchical stochastic block model (SBM) [63] with degree-correction for the case with edge layers [118].”
Robustness and resilience of complex networks (2024, neutral): “…are usually heterogeneous and fat-tailed, with a few units acting as hubs and several other units with a few connections 4–8 , exhibiting a marked mesoscale organization into modules 9–13 , hierarchies 14–16 , networks of networks 17–22 , high-order structures 23–25 and latent geometry 26–28 .”
MetaCell: analysis of single-cell RNA-seq data using K-nn graph partitions (2019, background): “…flexible intra-MC models, capable of accounting for not only sampling noise but also convergent processes such as cell cycle or stress [47, 48], or embedding the metacells in hierarchical or multi-resolution structures [49, 50] should allow for more efficient extraction of the signals of interest.”
The ground truth about metadata and community detection in networks (2016, methodology): “A deeper analysis, however, suggests that this network is better described by subdividing these two groups, a step that reveals substantial substructure within the dominant patterns of political connectivity [19, 39].”