Collapsed Structured Block Models for Community Detection in Complex Networks
Marios Papamichalis, Regina Ruane · 2026
Read Collapsed Structured Block Models for Community Detection in Complex Networks by Marios Papamichalis, Regina Ruane (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-02828.txt.
Introduction
Marios Papamichalis and Regina Ruane compute the thresholds at which a collapsed stochastic block model changes its mind about a network's communities. A block model splits nodes into groups with tie probabilities between them. Collapsing those probabilities out leaves each split scored by a marginal likelihood, and every decision, how many groups, whether a weak group survives, becomes a comparison of two scores. Those comparisons fail in known ways.
Weak structure gets dropped, small communities get merged, and a cluster of hubs can be returned in place of the real groups. Each failure has a threshold, and the authors compute them. The best single partition keeps planted structure only above a first moment bound that sits above the classic Kesten Stigum threshold for up to ten communities. Evidence summed over all partitions switches exactly at Kesten Stigum. That leaves a gap where the posterior favors structure no reported partition shows.
Catalog record
| CREATOR | Marios Papamichalis, Regina Ruane |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 71 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2601-02828
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Collapsed Structured Block Models for Community Detection in Complex Networks Marios Papamichalis, Regina Ruane Abstract Community detection seeks to recover mesoscopic structure from network data that may be binary, count-valued, signed, directed, weighted, or multilayer. The stochastic block model (SBM) explains such structure by positing a latent partition of nodes and block-specific edge distributions. In Bayesian SBMs, standard MCMC alternates between updating the partition and sampling block parameters, which can hinder mixing and complicate principled comparison across different partitions and numbers of communities. We develop a collapsed Bayesian SBM framework in which block-specific nuisance parameters are analytically integrated out under conjugate priors, so the marginal likelihood p ( Y ∣ z ) p(Y\mid z) depends only on the partition z z and blockwise sufficient statistics. This yields fast local Gibbs/Metropolis updates based on ratios of closed-form integrated likelihoods and provides evidence-based complexity control that discourages gratuitous over-partitioning. We derive exact collapsed marginals for the most common SBM edge types—Beta–Bernoulli (binary), Gamma–Poisson (counts), and Normal–Inverse-Gamma (Gaussian weights)—and we extend collapsing to gap-constrained SBMs via truncated conjugate priors that enforce explicit upper bounds on between-community connectivity. We further show that the same collapsed strategy supports directed SBMs that model reciprocity through dyad states, signed SBMs via categorical block models, and multiplex SBMs where multiple layers contribute additive evidence for a shared partition. Across synthetic benchmarks and real networks (including email communication, hospital contact counts, and citation graphs), collapsed inference produces accurate partitions and interpretable posterior block summaries of within- and between-community interaction strengths while remaining computationally simple and modular. 1 Introduction Networks encode relational structure across domains (communication, biology, finance, science). A central inferential task is community detection : partitioning nodes into groups so that interaction patterns are approximately homogeneous within and systematically different between groups. The stochastic block model (SBM) is a canonical approach, positing that, conditional on a latent partition z\in\{1,\dots,K\}^{n} , dyads follow a block-specific distribution (e.g., Bernoulli or Poisson) with parameters shared by all node pairs in the same block-pair. While SBMs provide a clean likelihood-based route to clustering and uncertainty quantification, two practical mismatches recur in modern network data: (i) diagonal blocks are not i.i.d. , because within-community subgraphs often exhibit internal structure (heavy-tailed sociability, triadic closure, metric/latent geometry, or latent features), and (ii) off-diagonal blocks are not merely “different” , but can be constrained by domain knowledge (e.g., between-group connectivity is possible yet intrinsically bounded and should not be explained by inflating a between-block probability/rate). These mismatches lead to overfitting, unstable partitions, and poor interpretability when a single unstructured block family is forced to explain all scales of network variation. The goal of community detection is not only to produce a partition, but to deliver an interpretable mesoscopic explanation of interaction patterns: which groups interact strongly, which weakly, and why . In many applications, the scientific signal lives precisely in the mechanisms that standard SBMs treat as nuisance: degree heterogeneity can distinguish “hub-dominated” communities from egalitarian ones; closure can indicate social reinforcement within a group; geometry can encode spatial/functional constraints (e.g. connectomes); and directionality or sign can reveal asymmetries and antagonism. At the same time, between-group interactions are often rare by construction (organizational silos, specialization, physical separation), so partitions that require dense off-diagonal interaction should be penalized sharply and transparently. A framework that (i) models structured within-block behavior, (ii) enforces explicit between-block constraints, and (iii) remains computationally tractable is therefore essential for reliable inference in complex networks. Adding structure to block models typically introduces many nuisance parameters: block probabilities/rates, regression coefficients, latent positions/features, or even discrete block types (e.g. “ER-like” vs. “closure” vs. “geometry” inside a community). Posterior inference then becomes challenging: the state space mixes discrete (partitions, block types) and continuous (parameters, latent variables), and model selection for K and within-block mechanisms becomes trans-dimensional. Naively sampling all parameters can yield slow mixing and brittle solutions, while optimizing a large parameterization risks overfitting and obscures uncertainty. We propose a collapsed Bayesian approach that integrates out block-specific nuisance parameters analytically whenever conjugacy (or augmentation-based conditional conjugacy) is available. The core output is a collapsed marginal likelihood p(Y\mid z) (and optionally p(Y\mid z,t) when diagonal block types are included), which depends only on discrete structure and blockwise sufficient statistics. In its simplest form, p(z\mid Y)\ \propto\ p(z)\,p(Y\mid z), so inference can be carried out directly on partitions using local ratio updates. Collapsing yields three concrete benefits that are central to this paper: 1. Computational tractability: label updates depend on a small set of maintained block sufficient statistics, enabling local Gibbs/Metropolis kernels that avoid sampling high-dimensional nuisance parameters at each sweep. 2. Automatic complexity control: the collapsed evidence carries an explicit Occam factor, so over-partitioning (or over-parameterizing within blocks) is penalized unless the data provide commensurate fit gains. 3. Scientific interpretability: collapsed posteriors naturally produce block-level summaries (e.g. posterior mean edge probabilities or intensities) that quantify within versus between interaction strengths, directionality, sign tendencies, and sparsity–intensity tradeoffs. Our model class separates diagonal and off-diagonal behavior. Off-diagonal blocks use exponential-family edge models with conjugate (or truncated conjugate) priors, so the integrated likelihood is available in closed form and depends only on block sufficient statistics. Diagonal blocks are allowed to be structured and may differ across communities: each community C_{k} is assigned a latent type t_{k}\in\mathcal{T} (finite or countable), and we collapse over types via a within-block marginal of the form m_{\mathrm{in}}(C_{k})\ :=\ \sum_{t\in\mathcal{T}}\pi(t)\,m_{t}(Y_{C_{k}}), so that the posterior can select the best-supported internal mechanism per community without committing to a single global block family. Between-community behavior can be constrained by design through gap constraints : for example, truncating a Beta prior to [0,x_{\max}] enforces that between-block probabilities are never large, a scientifically transparent regularization that prevents boundary erosion when a small number of noisy cross-edges appear. A model is collapsed when nuisance parameters are analytically integrated out so that the marginal likelihood depends only on latent discrete structure (e.g. community labels) and sufficient statistics. This yields Gibbs/Metropolis updates using ratios of integrated likelihoods rather than sampling high-dimensional parameters. The stochastic block model (SBM) is a foundational network model for community detection, where nodes are partitioned into latent blocks (communities) and edge distributions depend only on block memberships. The classic SBM was introduced by 3 . In a Bayesian framework, 7 provided an early treatment of SBMs with Gibbs sampling for joint inference of cluster assignments and block parameters. With conjugate priors on block connectivity parameters (e.g. Beta priors for Bernoulli edges), these block parameters can be integrated out analytically, yielding a collapsed marginal likelihood for a given partition and a posterior distribution directly on community assignments ( 7 ; 5 ) . By eliminating continuous block parameters, collapsed inference reduces model dimensionality and often improves MCMC mixing. Building on these ideas, allocation samplers for Bayesian mixtures with unknown component count ( 6 ) were later adapted to network models. Rather than using reversible-jump MCMC to explore different numbers of communities K , allocation samplers treat cluster labels as random and place a prior on K itself (or an implicit prior via a Chinese Restaurant Process). In the SBM context, 5 integrated out block probabilities and directly sampled node allocations, enabling automatic inference of K while scaling to large networks. The