PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Tiago P. Peixoto

arXiv:1310.4377v6physics.data-ancond-mat.dis-nncond-mat.stat-mechcs.SIphysics.soc-phstat.ML

TL;DR

Existing network community methods can miss statistical validation and fail to resolve small but well-defined modules in large networks. The paper introduces a nested stochastic block model whose upper levels inform lower-level inference, yielding finer resolution while preserving parsimonious model selection. The approach is reported to avoid spurious communities, generalize across mixing patterns and graph types, and scale to very large networks.

  • Problem

    Existing methods may fail to separate structure from noise and exhibit a resolution limit that hides smaller modules as networks grow.

  • Method

    The paper uses a nested stochastic block model in which upper-level models provide prior information to lower levels, with MDL-based parsimonious selection and an efficient inference algorithm.

  • Results

    The nested model replaces the nonhierarchical resolution scale with logarithmic dependence on N and is reported to detect correct block counts in sparse networks without spurious communities.

  • Takeaways & Limitations

    The method provides multiscale descriptions of large networks while supporting arbitrary mixing patterns and hierarchical forms.

Abstract

from arXiv · show

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.

I. INTRODUCTION

Existing network community methods can miss statistical validation, spuriously detect structure, and fail to resolve small modules as networks grow. The paper motivates a nested stochastic block model to address these limitations while retaining generality and tractability.

  • Community detection seeks to characterize salient large-scale structures in biological, technological, and social networks.
  • Modularity optimization favors partitions with more internal edges than expected under a random-graph null model but does not assess statistical evidence.
  • Existing methods can detect high-scoring partitions in random graphs and therefore fail to distinguish actual structure from statistical fluctuations.
  • Modularity optimization misses clusters below a threshold that increases with E, the total number of network edges, and can yield degenerate large-network partitions.
  • Statistical model selection avoids spurious communities but retains a resolution limit because the maximum detectable block count scales with N, the number of nodes.
  • The proposed nested hierarchy uses upper-level models as priors for lower levels, reducing the resolution scale to logarithmic dependence on N while supporting arbitrary structures and parsimonious model selection.

II. HIERARCHICAL MODEL

The nested stochastic block model recursively models block-level edge-count multigraphs, producing a hierarchy that describes network structure across scales. It remains general enough for arbitrary mixing patterns and directed or undirected graphs.

  • The stochastic block model divides nodes into blocks with arbitrary connection probabilities and can represent core-periphery, bipartite, and directed structures.
  • The nested model treats block edge counts as a multigraph and recursively generates smaller block multigraphs until reaching a single block.
  • An upper-level generative model supplies prior information to lower levels, increasing resolution while keeping the hierarchy tractable and nonparametric.
  • The analysis focuses on undirected networks, while the formulation is stated to apply straightforwardly to directed networks.

A. Module inference

Module inference finds node partitions by maximizing posterior likelihood, equivalently minimizing ensemble entropy, within a multilevel block-model hierarchy. The hierarchy encodes the observed network through progressively coarser block multigraphs.

  • Module inference: Inference seeks the node partition that maximizes posterior likelihood in the observed network.
  • Module inference: Because graphs with identical block edge counts have equal probability, likelihood maximization is equivalent to minimizing ensemble entropy.
  • Hierarchical representation: At successive levels, nodes are grouped into blocks while edge totals remain conserved across the resulting block multigraphs.
  • Hierarchical representation: The full generative model encodes the network as a sequence of choices from the top-level model through lower-level branches to the observed graph.
  • Model-size inference: When hierarchy size is unknown, directly minimizing entropy is inadequate because it favors the trivial hierarchy with B_l=N at every level.

B. Model selection

Model selection minimizes description length for both the network and its hierarchical parameters, using MDL to balance fit against model complexity. The nested formulation can match or improve on flat models and is reported to remove the nonhierarchical resolution limit.

  • Minimum description length: Minimum description length selects the model by encoding both the observed data and the model parameters.
  • Minimum description length: The hierarchical description assigns upper-level model entropy to describing parameters at the next lower level, recursively across the hierarchy.
  • Partition encoding: The improved partition description is more effective for nonuniform block sizes than treating all partitions as equally likely.
  • Degree correction: For Poisson degree distributions, traditional and degree-corrected models have identical total description lengths, whereas non-Poisson distributions generally favor the degree-corrected variant.
  • Nested versus flat selection: The nested model fully contains the flat model and therefore has a shorter or equal minimum description length.
  • Degree correction: The degree-corrected model still incurs additional description length for encoding the degree sequence, even when total lengths are asymptotically equal.
  • Model-selection comparison: The reported comparisons find that nested selection detects the correct block count for sparse networks and avoids the resolution limit of nonhierarchical inference.

1. Module detectability and the “resolution limit”

Community detectability requires both recovering the planted partition and selecting the correct number of blocks. The nested model addresses resolution limits that cause smaller structures to be merged in large networks.

  • Detectability: Module detectability asks whether planted parameters can be recovered from a single observed network, conditional on prior knowledge such as the number of blocks.When B is known, the task is node classification; when B is unknown, model selection is also required.
  • Detectability: For perfectly isolated blocks, the detectability threshold is ⟨k⟩=1 when B is known, but model-selection criteria can require higher average degree.MDL and dense BMS fail below ⟨k⟩=2, although detectability remains possible when the true B is known.
  • Resolution limit: Modularity and nonhierarchical inference merge smaller blocks in large networks despite strong structure, producing a resolution limit that depends on network size and block count.For the nonhierarchical model, the optimal block count has a threshold that increases with network size.
  • Model selection: The resolution limit is not unique to modularity: even statistically grounded model selection can merge blocks because nonhierarchical models assign equal prior weight across many possible structures.The nested hierarchy supplies multiscale structure without requiring prior knowledge of a specific mixing pattern.
  • Nested model: The nested model reduces the characteristic detectable block size from a scale proportional to N/B* to one scaling as ln N, enabling smaller communities to be resolved in very large networks.Its description-length dependence on network size and block count is only logarithmic in the isolated-block example.
  • Resolution limit: For two small isolated blocks embedded in a larger network, the flat model’s detectable region shrinks as the remaining network becomes denser or larger, whereas the nested model avoids this dependence to a substantial extent.Figure 3 compares nonhierarchical and hierarchical boundaries as functions of average block size, average degree, and network size.

III. INFERENCE ALGORITHM

The inference algorithm constructs and optimizes a hierarchy using local changes to its levels. It combines agglomerative inference with resize, insertion, and deletion moves and is designed to remain efficient for large networks.

  • Inference procedure: Each hierarchy level is a regular block model, so its node classification can use established inference methods.The paper uses an agglomerative heuristic that is unbiased toward the types of block structures inferred.
  • Scalability: The agglomerative implementation has complexity O(N ln^2 N), independent of the number of blocks B, and has been applied to networks exceeding 10^7 edges.This supports its use for large-scale systems.
  • Hierarchy moves: The resize move changes the number of blocks at a level while preserving the partition imposed by the level above.This restriction makes description-length updates depend only on modifications at the current level.
  • Hierarchy moves: Insert and delete moves respectively add a new hierarchy level or remove one by grouping the lower-level nodes directly according to the next level.Together with resize, these moves can construct any hierarchy.
  • Optimization: The greedy optimization repeatedly attempts resize, insert, and delete moves and retains moves that decrease the total description length.The procedure tracks completed levels and revisits neighboring levels after successful changes.

IV. SYNTHETIC BENCHMARKS

Synthetic benchmarks show that nested stochastic block-model inference recovers planted structure while simplifying hierarchies when lower-level distinctions are unsupported, avoiding spurious structure near the detectability threshold.

  • Benchmark construction: The benchmark constructs nested planted-partition networks by recursively applying Kronecker products to a seed mixing matrix.The model uses B0 seed blocks and hierarchy depth L−1.
  • Benchmark construction: ⟨k⟩= [(B0 −1)/(cB0 −1)]2 is the detectability transition for equal-sized seed blocks.This matches the regular planted-partition model with B = B0.
  • Inference performance: For B0 = 2, L = 5, N = 104 and ⟨k⟩= 20, the correct block count is detected above the detectability threshold c∗.The inferred hierarchy matches the planted hierarchy exactly only at higher c values.
  • Inference performance: Shallower inferred hierarchies can be equivalent to the planted model because they encode the same lowest-level edge-count matrix with less description length.The simplification therefore represents compression rather than inference failure.
  • Inference performance: As c approaches the random-graph regime, the method settles on L = 1, B = 1 and does not tend to find spurious hierarchies.This conservative behavior supports confidence in the structures it does identify.

V. EMPIRICAL NETWORKS

Applications across political blogs, Internet autonomous systems, film-actor networks, and broader empirical datasets show that the nested model captures multiscale and non-assortative organization while reducing the resolution limitation seen in flat models.

  • Case studies: The political-blog network’s topmost nested partition closely matches the accepted Republican–Democratic division and also reveals lower-level subdivisions.The network contains N = 1,222 blogs and E = 19,027 directed edges.
  • Case studies: The Internet autonomous-systems network yields B = 191 lowest-level blocks and a prominent core–periphery structure with geographically distributed core nodes.The network contains N = 52,104 AS nodes and E = 399,625 direct connections.
  • Case studies: The IMDB network is separated into actors and films at the top level, then subdivided along geographical, temporal, and topical lines.The nested model finds B = 971 blocks versus B = 332 for the nonhierarchical model.
  • Meta-analysis: Across empirical networks, the nested model removes the dependence of smallest average block size on network size observed with the nonhierarchical model.This provides an empirical demonstration of the lack of a resolution limit.
  • Meta-analysis: Modularity can discard topological information when networks are not predominantly assortative, whereas statistical inference retains broader structural patterns.The authors therefore restrict modularity maximization to cases where assortative structure is known to dominate.

VI. DISCUSSION

The paper presents nested stochastic block models as a general, principled approach to hierarchical network structure. It improves resolution through a smaller logarithmic scale while retaining model selection against spurious communities.

  • Contributions: The nested stochastic block model generalizes hierarchical community detection to assortative, dissortative, mixed, directed, and non-binary structures.It places no restriction on the possible large-scale mixing pattern or hierarchy form.
  • Contributions: The resolution scale changes from a characteristic size scaling with N to a much smaller logarithmic dependence.The authors describe this as practically nonexistent for many applications.
  • Contributions: Robust model selection accompanies the increased resolution and prevents a tendency to identify spurious communities.The method also infers detailed large-scale features in very large empirical networks.
  • Extensions: The approach is proposed as applicable to overlapping and link-community models, missing-information detection, network-evolution prediction, and functional summaries.These are stated as prospective extensions rather than demonstrated results in this passage.

Appendix A: Bayesian model selection (BMS)

The appendix compares Bayesian model selection with MDL and examines priors that avoid overrepresenting dense networks when modeling sparse empirical data.

  • BMS–MDL comparison: Under compatible constraints, Bayesian model selection and MDL yield equivalent model-selection criteria.The appendix states that their differences arise from nuances in prior probabilities when constraints are compatible.
  • Bayesian model selection: Bayesian model selection integrates over model parameters rather than maximizing likelihood alone, helping avoid overfitting through an Occam’s-razor effect.Larger models contain many parameter choices that fit poorly and therefore contribute less to the integrated likelihood.
  • Prior choice: The flat prior P({prs}|B) = 1 is agnostic and analytically convenient but generates dense networks with average degree scaling as N/2.This conflicts with the sparsity typical of large empirical networks.
  • Prior choice: A prior constraining the expected edge count would better match sparse data, but its integral is difficult to solve directly.The authors instead fix the number of edges E, implicitly constraining the average degree while retaining tractability.
  • Reparameterization: With fixed E, maximizing over q_rs gives a likelihood equivalent to the earlier model in the appropriate limit while keeping average degree independent of the prior.The stated equivalence holds when m_rs ≫1 or m_rs = 0.

Appendix B: Comparison with other community detection methods

The benchmark compares partition recovery and detected block counts across community-detection methods, showing that nested model selection avoids spurious structure while other methods misestimate structure or resolution.

  • Figure 9: Figure 9 averages VI and detected block counts over 20 realizations for networks with N = 2 × 10^4 and planted B = 100.The top panel varies VI with assortativity c; the bottom panel varies the inferred block count.
  • Evaluation metric: Variation of information is used because normalized mutual information can increase simply when methods return more blocks, without stronger correlation to the planted partition.VI equals zero for identical partitions and increases as overlap decreases.
  • Synthetic benchmark: For planted B = 100 networks, fixed-B inference becomes detectable slightly above c ≈0.2, whereas nested model selection selects B = 1 below approximately c ≈0.4.Above that range, nested inference increases its block count toward the planted value as assortativity rises.
  • Method comparison: Louvain finds systematically smaller block counts, produces spurious partitions below detectability, and recovers the correct partition only at c = 1.Its behavior combines a resolution limit with the lack of statistical model selection.
  • Method comparison: Infomod is largely compatible with the planted partition above c ≈0.6 but overestimates block counts at larger c and detects spurious structure below detectability.The appendix attributes this to its inability to distinguish planted structure from quenched topological fluctuations affecting random walks.

Appendix C: Directed and undirected networks

The appendix gives entropy and description-length formulations for directed and undirected block-model variants, with sparse-limit assumptions and a closed-form limitation outside that regime.

  • Extensions: The framework extends to directed graphs, while upper-level multigraphs contribute corresponding entropy terms.The appendix separately states the directed ensemble and upper-level multigraph entropy constructions.
  • Graph ensembles: The undirected and directed formulations differ in how edge counts between blocks are interpreted and how their entropy expressions are written.For undirected graphs, within-block counts correspond to half-edges; directed graphs use edges from block r to s.
  • Entropy expressions: The entropy expressions use e_rs as block-to-block edge counts and n_r as block sizes, with sparse-network approximations when e_rs ≪ n_r n_s.The same sparse-limit qualification applies to the degree-corrected expressions.
  • Scope limitation: Outside the sparse limit, the degree-corrected entropy has no closed-form expression, unlike the traditional variant.This limits direct analytic treatment of dense degree-corrected networks.
  • Degree correction: Degree-corrected models require description-length information for the degree sequence in addition to the block structure.The appendix describes this augmentation as analogous to the undirected formulation.

A. Empirical networks

Empirical applications show that the nested stochastic block model represents networks through multilevel blocks that capture large-scale organization and finer subdivisions.

  • Internet: The Internet hierarchy separates four top-level geographical or structural groups before further subdivision at lower levels.These include core AS nodes and three broad regional groupings.
  • Internet: The Internet autonomous-systems network exhibits a prominent core-periphery architecture in the nested stochastic block model hierarchy.The top-level core branch contains autonomous-system nodes distributed globally, while lower levels partition the network further.
  • Interpretation: The empirical examples illustrate that the hierarchy can associate blocks with interpretable geographical, temporal, and genre patterns.The Internet example emphasizes geographical divisions, while IMDB labels reflect multiple metadata dimensions.
  • IMDB: In the IMDB actor-film network, each displayed node represents a lowest-level block rather than an individual graph node.The hierarchy distinguishes actor and film branches, with labels based on geographical, temporal, or genre characteristics.
Loading 1310.4377v6…