Sparse graphs using exchangeable random measures
From MaRDI portal
Publication:4603788
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.
Recommendations
Cites work
- scientific article; zbMATH DE number 3248623 (Why is no real title available?)
- A Representation of Independent Increment Processes without Gaussian Components
- A nonparametric view of network models and Newman–Girvan and other modularities
- A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
- A survey of statistical network models
- An Introduction to the Theory of Point Processes
- Asymptotic behavior and distributional limits of preferential attachment graphs
- Asymptotic laws for compositions derived from transformed subordinators
- 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
- Brownian excursions, critical random graphs and the multiplicative coalescent
- Co-clustering separately exchangeable network data
- Collective dynamics of `small-world' networks
- Completely random measures
- Consistency of community detection in networks under degree-corrected stochastic block models
- Controlling the Reinforcement in Bayesian Non-Parametric Mixture Models
- Convergent sequences of dense graphs. I: Subgraph frequencies, metric properties and testing
- Convergent sequences of sparse graphs: a large deviations approach
- Distributional results for means of normalized random measures with independent increments
- Emergence of Scaling in Random Networks
- Estimation and Prediction for Stochastic Blockstructures
- Exchangeable Rasch matrices
- Exchangeable and partially exchangeable random partitions
- Exchangeable random measures in the plane
- Ferguson distributions via Polya urn schemes
- Generalized Gamma measures and shot-noise Cox processes
- Generating simple random graphs with prescribed degree distribution
- Graph limits and exchangeable random graphs
- Investigating nonparametric priors with Gibbs structure
- Latent Space Approaches to Social Network Analysis
- Limits of dense graph sequences
- MCMC for normalized random measure mixture models
- Mixed membership stochastic blockmodels
- Modelling heterogeneity in survival analysis by the compound Poisson distribution
- Moments of two-variable functions and the uniqueness of graph limits
- Networks. An introduction.
- Notes on the occupancy problem with infinitely many boxes: general asymptotics and power laws
- On Lewis' simulation method for point processes
- On a conditionally Poissonian graph process
- On the bootstrap of \(U\) and \(V\) statistics
- Posterior Analysis for Normalized Random Measures with Independent Increments
- Power-law distributions in empirical data
- Random Fragmentation and Coagulation Processes
- Random Geometric Graphs
- Random variate generation for exponentially and polynomially tilted stable distributions
- Representations for partially exchangeable arrays of random variables
- Sampling exponentially tilted stable distributions
- Simulation of nonhomogeneous poisson processes by thinning
- Spectral clustering and the high-dimensional stochastic blockmodel
- Stochastic processes directed by randomized time
- Survival models for heterogeneous populations derived from stable distributions
- The Structure and Function of Complex Networks
- The method of moments and degree distributions for network models
- The phase transition in inhomogeneous random graphs
- The structure of scientific collaboration networks
Cited in
(73)- Identifiability for graphexes and the weak kernel metric
- Inference for High-Dimensional Exchangeable Arrays
- 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
- Finite-dimensional Discrete Random Structures and Bayesian Clustering
- On convergence for graphexes
- Exponential-family models of random graphs: inference in finite, super and infinite population scenarios
- Nonexchangeable random partition models for microclustering
- Bayesian consensus clustering in multiplex networks
- Causal Inference for Social Network Data
- Graph theory. Abstracts from the workshop held January 2--8, 2022
- An improved algorithm for generalized community structure inference in complex networks
- Bayesian modeling via discrete nonparametric priors
- Sampling perspectives on sparse exchangeable graphs
- On exchangeability in network models
- Asymptotic analysis of statistical estimators related to multigraphex processes under misspecification
- scientific article; zbMATH DE number 7415089 (Why is no real title available?)
- Efficient Simulation of Sparse Graphs of Point Processes
- On edge exchangeable random graphs
- Exact simulation of Poisson-Dirichlet distribution and generalised gamma process
- Exchangeable trait allocations
- Bayesian nonparametric sparse VAR models
- Sparse maximum-entropy random graphs with a given power-law degree distribution
- On the Truncation Error of a Superposed Gamma Process
- A statistical framework for modern network science
- Modularity Maximization for Graphons
- Hierarchical Network Models for Exchangeable Structured Interaction Processes
- Gibbs partitions, Riemann-Liouville fractional operators, Mittag-Leffler functions, and fragmentations derived from stable subordinators
- Recent advances on mechanisms of network generation: community, exchangeability, and scale-free properties
- Metrics for sparse graphs
- Non-parametric overlapping community detection
- Minimax rates in network analysis: graphon estimation, community detection and hypothesis testing
- Projective, sparse and learnable latent position network models
- 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
- 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
- A note on nonparametric inference for species variety with Gibbs-type priors
- Bayesian mixture models (in)consistency for the number of clusters
- Sampling and estimation for (sparse) exchangeable graphs
- Local 2-separators
- Nonnegative Bayesian nonparametric factor models with completely random measures
- Exchangeable random networks
- A unified construction for series representations and finite approximations of completely random measures
- Integrability conditions for compound random measures
- A hierarchical Bayesian model for predicting ecological interactions using scaled evolutionary relationships
- Truncated Poisson-Dirichlet approximation for Dirichlet process hierarchical models
- Network of scientific concepts: empirical analysis and modeling
- 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
- Local exchangeability
- Rejoinder to the discussion of ``Bayesian graphical models for modern biological applications
- Efficient Estimation for Random Dot Product Graphs via a One-Step Procedure
- 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
- Probabilities of Sentences about Very Sparse Random Graphs
- Truncated two-parameter Poisson-Dirichlet approximation for Pitman-Yor process hierarchical models
- Sparse exchangeable graphs and their limits via graphon processes
- Approximating predictive probabilities of Gibbs-type priors
- Bayesian learning of graph substructures
- Limit theorems for distributions invariant under groups of transformations
- Fallacy of data-selective inference in modelling networks
- Random walks on dense graphs and graphons
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)
