# Rapidly Varying Completely Random Measures for Modeling Extremely Sparse Networks

arXiv: https://arxiv.org/abs/2505.13206 · HTML: https://mlsanity.com/paper/2505.13206/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 18 of its 57 references that are in the map.
- First posted on arXiv 19 May 2025.

## Builds on (most cited first, 18 of 18)

- [A Conceptual Introduction to Hamiltonian Monte Carlo](https://mlsanity.com/paper/1701.02434/) (2017)
- [Sparse graphs using exchangeable random measures](https://mlsanity.com/paper/1401.1137/) (2014)
- [Revisiting the Gelman-Rubin Diagnostic](https://mlsanity.com/paper/1812.09384/) (2018)
- [The Class of Random Graphs Arising from Exchangeable Random Measures](https://mlsanity.com/paper/1512.03099/) (2015)
- [Flexible Models for Microclustering with Application to Entity Resolution](https://mlsanity.com/paper/1610.09780/) (2016)
- [Exchangeable Random Measures for Sparse and Modular Graphs with Overlapping Communities](https://mlsanity.com/paper/1602.02114/) (2016)
- [Edge-exchangeable graphs and sparsity](https://mlsanity.com/paper/1603.06898/) (2016)
- [Random Partition Models for Microclustering Tasks](https://mlsanity.com/paper/2004.02008/) (2020)
- [Sampling and Estimation for (Sparse) Exchangeable Graphs](https://mlsanity.com/paper/1611.00843/) (2016)
- [Latent nested nonparametric priors](https://mlsanity.com/paper/1801.05048/) (2018)
- [Compound random measures and their use in Bayesian nonparametrics](https://mlsanity.com/paper/1410.0611/) (2014)
- [Truncated Random Measures](https://mlsanity.com/paper/1603.00861/) (2016)
- [Non-exchangeable random partition models for microclustering](https://mlsanity.com/paper/1711.07287/) (2017)
- [Beyond the Chinese Restaurant and Pitman-Yor processes: Statistical Models with Double Power-law Behavior](https://mlsanity.com/paper/1902.04714/) (2019)
- [A unified construction for series representations and finite approximations of completely random measures](https://mlsanity.com/paper/1905.10733/) (2019)
- [The Normal-Generalised Gamma-Pareto process: A novel pure-jump L'evy process with flexible tail and jump-activity properties](https://mlsanity.com/paper/2006.10968/) (2020)
- [Modelling and computation using NCoRM mixtures for density regression](https://mlsanity.com/paper/1608.00874/) (2016)
- [Sparse Networks with Core-Periphery Structure](https://mlsanity.com/paper/1910.09679/) (2019)

## Abstract (arXiv)

Completely random measures (CRMs) are fundamental to Bayesian nonparametric models, with applications in clustering, feature allocation, and network analysis. A key quantity of interest is the Laplace exponent, whose asymptotic behavior determines how the random structures scale. When the Laplace exponent grows nearly linearly - known as rapid variation - the induced models exhibit approximately linear growth in the number of clusters, features, or edges with sample size or network nodes. This regime is especially relevant for modeling sparse networks, yet existing CRM constructions lack tractability under rapid variation. We address this by introducing a new class of CRMs with index of variation α∈(0,1], defined as mixtures of stable or generalized gamma processes. These models offer interpretable parameters, include well-known CRMs as limiting cases, and retain analytical tractability through a tractable Laplace exponent and simple size-biased representation. We analyze the asymptotic properties of this CRM class and apply it to the Caron-Fox framework for sparse graphs. The resulting models produce networks with near-linear edge growth, aligning with empirical evidence from large-scale networks. Additionally, we present efficient algorithms for simulation and posterior inference, demonstrating practical advantages through experiments on real-world sparse network datasets.