Sparse graphs using exchangeable random measures
From MaRDI portal
Publication:4603788
DOI10.1111/RSSB.12233zbMATH Open1381.62072arXiv1401.1137OpenAlexW2963730104WikidataQ47130290 ScholiaQ47130290MaRDI QIDQ4603788FDOQ4603788
Authors: Francois Caron, Emily B. Fox 
Publication date: 19 February 2018
Published in: Journal of the Royal Statistical Society Series B: Statistical Methodology (Search for Journal in Brave)
Abstract: Statistical network modeling has focused on representing the graph as a discrete structure, namely the adjacency matrix, and considering the exchangeability of this array. In such cases, the Aldous-Hoover representation theorem (Aldous, 1981;Hoover, 1979} applies and informs us that the graph is necessarily either dense or empty. In this paper, we instead consider representing the graph as a measure on . For the associated definition of exchangeability in this continuous space, we rely on the Kallenberg representation theorem (Kallenberg, 2005). We show that for certain choices of such exchangeable random measures underlying our graph construction, our network process is sparse with power-law degree distribution. In particular, we build on the framework of completely random measures (CRMs) and use the theory associated with such processes to derive important network properties, such as an urn representation for our analysis and network simulation. Our theoretical results are explored empirically and compared to common network models. We then present a Hamiltonian Monte Carlo algorithm for efficient exploration of the posterior distribution and demonstrate that we are able to recover graphs ranging from dense to sparse--and perform associated tests--based on our flexible CRM-based formulation. We explore network properties in a range of real datasets, including Facebook social circles, a political blogosphere, protein networks, citation networks, and world wide web networks, including networks with hundreds of thousands of nodes and millions of edges.
Full work available at URL: https://arxiv.org/abs/1401.1137
Recommendations
exchangeabilitypoint processrandom graphsgeneralized gamma processLévy measureKallenberg representation
Applications of graph theory (05C90) Characterization and structure theory for multivariate probability distributions; copulas (62H05) General theory of stochastic processes (60G07)
Cites Work
- Simulation of nonhomogeneous poisson processes by thinning
- Power-law distributions in empirical data
- A nonparametric view of network models and Newman–Girvan and other modularities
- Estimation and Prediction for Stochastic Blockstructures
- Random variate generation for exponentially and polynomially tilted stable distributions
- Sampling exponentially tilted stable distributions
- A Representation of Independent Increment Processes without Gaussian Components
- Spectral clustering and the high-dimensional stochastic blockmodel
- Limits of dense graph sequences
- Modelling heterogeneity in survival analysis by the compound Poisson distribution
- Random Geometric Graphs
- A survey of statistical network models
- On the bootstrap of \(U\) and \(V\) statistics
- Consistency of community detection in networks under degree-corrected stochastic block models
- Completely random measures
- Mixed membership stochastic blockmodels
- Emergence of Scaling in Random Networks
- The Structure and Function of Complex Networks
- The method of moments and degree distributions for network models
- On Lewis' simulation method for point processes
- Latent Space Approaches to Social Network Analysis
- MCMC for normalized random measure mixture models
- Exchangeable and partially exchangeable random partitions
- The phase transition in inhomogeneous random graphs
- Collective dynamics of `small-world' networks
- Networks. An introduction.
- Representations for partially exchangeable arrays of random variables
- Graph limits and exchangeable random graphs
- Ferguson distributions via Polya urn schemes
- Distributional results for means of normalized random measures with independent increments
- Moments of two-variable functions and the uniqueness of graph limits
- Investigating nonparametric priors with Gibbs structure
- Posterior Analysis for Normalized Random Measures with Independent Increments
- Generalized Gamma measures and shot-noise Cox processes
- A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
- Brownian excursions, critical random graphs and the multiplicative coalescent
- Survival models for heterogeneous populations derived from stable distributions
- On a conditionally Poissonian graph process
- Random Fragmentation and Coagulation Processes
- An Introduction to the Theory of Point Processes
- Generating simple random graphs with prescribed degree distribution
- Asymptotic behavior and distributional limits of preferential attachment graphs
- Convergent sequences of dense graphs. I: Subgraph frequencies, metric properties and testing
- Controlling the Reinforcement in Bayesian Non-Parametric Mixture Models
- The structure of scientific collaboration networks
- Title not available (Why is that?)
- Notes on the occupancy problem with infinitely many boxes: general asymptotics and power laws
- Exchangeable Rasch matrices
- Asymptotic laws for compositions derived from transformed subordinators
- Stochastic processes directed by randomized time
- Bayesian Poisson process partition calculus with an application to Bayesian Lévy moving averages
- Bayesian nonparametric Plackett-Luce models for the analysis of preferences for college degree programmes
- Co-clustering separately exchangeable network data
- Exchangeable random measures in the plane
- Convergent sequences of sparse graphs: a large deviations approach
Cited In (74)
- Two part envelopes for rejection sampling of some completely random measures
- Exchangeable Random Measures for Sparse and Modular Graphs with Overlapping Communities
- Compound Poisson models for weighted networks with applications in finance
- Hierarchical normalized completely random measures for robust graphical modeling
- Infinite-color randomly reinforced urns with dominant colors
- On convergence for graphexes
- Exponential-family models of random graphs: inference in finite, super and infinite population scenarios
- Nonexchangeable random partition models for microclustering
- Graph theory. Abstracts from the workshop held January 2--8, 2022
- An improved algorithm for generalized community structure inference in complex networks
- On exchangeability in network models
- Sampling perspectives on sparse exchangeable graphs
- Title not available (Why is that?)
- Efficient Simulation of Sparse Graphs of Point Processes
- Exact simulation of Poisson-Dirichlet distribution and generalised gamma process
- On edge exchangeable random graphs
- Bayesian nonparametric sparse VAR models
- Exchangeable trait allocations
- Modularity Maximization for Graphons
- Sparse maximum-entropy random graphs with a given power-law degree distribution
- Hierarchical Network Models for Exchangeable Structured Interaction Processes
- A statistical framework for modern network science
- Metrics for sparse graphs
- Combinatorial approach to the interpolation method and scaling limits in sparse random graphs
- Non-parametric overlapping community detection
- Minimax rates in network analysis: graphon estimation, community detection and hypothesis testing
- Core-periphery structure in networks: a statistical exposition
- Asymptotic behavior of the number of distinct values in a sample from the geometric stick-breaking process
- Network representation using graph root distributions
- Sparse networks with core-periphery structure
- Asymptotic behavior of common connections in sparse random networks
- Bootstrap estimators for the tail-index and for the count statistics of graphex processes
- Random Walks on Dense Graphs and Graphons
- A note on nonparametric inference for species variety with Gibbs-type priors
- Sampling and estimation for (sparse) exchangeable graphs
- Local 2-separators
- Nonnegative Bayesian nonparametric factor models with completely random measures
- A unified construction for series representations and finite approximations of completely random measures
- A hierarchical Bayesian model for predicting ecological interactions using scaled evolutionary relationships
- Integrability conditions for compound random measures
- Truncated Poisson-Dirichlet approximation for Dirichlet process hierarchical models
- Limits of sparse configuration models and beyond: graphexes and multigraphexes
- Truncated simulation and inference in edge-exchangeable networks
- Distribution-free connectivity testing for sparse graphs
- Rejoinder to the discussion of ``Bayesian graphical models for modern biological applications
- Higher-order fluctuations in dense random graph models
- A generalization of hierarchical exchangeability on trees to directed acyclic graphs
- Sufficientness postulates for Gibbs-type priors and hierarchical generalizations
- Sparse exchangeable graphs and their limits via graphon processes
- Probabilities of Sentences about Very Sparse Random Graphs
- Approximating predictive probabilities of Gibbs-type priors
- Gibbs partitions, Riemann–Liouville fractional operators, Mittag–Leffler functions, and fragmentations derived from stable subordinators
- Limit theorems for distributions invariant under groups of transformations
- Inference for High-Dimensional Exchangeable Arrays
- Identifiability for graphexes and the weak kernel metric
- Finite-dimensional Discrete Random Structures and Bayesian Clustering
- Causal Inference for Social Network Data
- Bayesian consensus clustering in multiplex networks
- Bayesian modeling via discrete nonparametric priors
- Asymptotic analysis of statistical estimators related to multigraphex processes under misspecification
- On the Truncation Error of a Superposed Gamma Process
- Recent advances on mechanisms of network generation: community, exchangeability, and scale-free properties
- Projective, sparse and learnable latent position network models
- On sparsity, power-law, and clustering properties of graphex processes
- Parameter Estimators of Sparse Random Intersection Graphs with Thinned Communities
- Tractably modelling dependence in networks beyond exchangeability
- Bayesian mixture models (in)consistency for the number of clusters
- Exchangeable random networks
- Network of scientific concepts: empirical analysis and modeling
- Local exchangeability
- Efficient Estimation for Random Dot Product Graphs via a One-Step Procedure
- Truncated two-parameter Poisson-Dirichlet approximation for Pitman-Yor process hierarchical models
- Bayesian learning of graph substructures
- Fallacy of data-selective inference in modelling networks
Uses Software
This page was built for publication: Sparse graphs using exchangeable random measures
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4603788)
