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)- On exchangeability in network models
- On edge exchangeable random graphs
- On convergence for graphexes
- A statistical framework for modern network science
- Nonnegative Bayesian nonparametric factor models with completely random measures
- Bayesian nonparametric sparse VAR models
- Asymptotic behavior of common connections in sparse random networks
- Network representation using graph root distributions
- Sparse networks with core-periphery structure
- Rejoinder to the discussion of ``Bayesian graphical models for modern biological applications
- Compound Poisson models for weighted networks with applications in finance
- Exchangeable trait allocations
- Minimax rates in network analysis: graphon estimation, community detection and hypothesis testing
- Exchangeable Random Measures for Sparse and Modular Graphs with Overlapping Communities
- Exact simulation of Poisson-Dirichlet distribution and generalised gamma process
- Probabilities of Sentences about Very Sparse Random Graphs
- A hierarchical Bayesian model for predicting ecological interactions using scaled evolutionary relationships
- A note on nonparametric inference for species variety with Gibbs-type priors
- Approximating predictive probabilities of Gibbs-type priors
- Two part envelopes for rejection sampling of some completely random measures
- Exponential-family models of random graphs: inference in finite, super and infinite population scenarios
- Modularity Maximization for Graphons
- Inference for High-Dimensional Exchangeable Arrays
- Higher-order fluctuations in dense random graph models
- A generalization of hierarchical exchangeability on trees to directed acyclic graphs
- A unified construction for series representations and finite approximations of completely random measures
- Hierarchical normalized completely random measures for robust graphical modeling
- Integrability conditions for compound random measures
- Non-parametric overlapping community detection
- An improved algorithm for generalized community structure inference in complex networks
- scientific article; zbMATH DE number 7415089 (Why is no real title available?)
- Infinite-color randomly reinforced urns with dominant colors
- Sampling perspectives on sparse exchangeable graphs
- Gibbs partitions, Riemann-Liouville fractional operators, Mittag-Leffler functions, and fragmentations derived from stable subordinators
- Sparse maximum-entropy random graphs with a given power-law degree distribution
- Bootstrap estimators for the tail-index and for the count statistics of graphex processes
- Nonexchangeable random partition models for microclustering
- Truncated Poisson-Dirichlet approximation for Dirichlet process hierarchical models
- Limits of sparse configuration models and beyond: graphexes and multigraphexes
- Random walks on dense graphs and graphons
- Truncated simulation and inference in edge-exchangeable networks
- Identifiability for graphexes and the weak kernel metric
- Efficient Simulation of Sparse Graphs of Point Processes
- Asymptotic behavior of the number of distinct values in a sample from the geometric stick-breaking process
- Local 2-separators
- Core-periphery structure in networks: a statistical exposition
- Metrics for sparse graphs
- Graph theory. Abstracts from the workshop held January 2--8, 2022
- Sparse exchangeable graphs and their limits via graphon processes
- Sufficientness postulates for Gibbs-type priors and hierarchical generalizations
- Sampling and estimation for (sparse) exchangeable graphs
- Hierarchical Network Models for Exchangeable Structured Interaction Processes
- Distribution-free connectivity testing for sparse graphs
- Limit theorems for distributions invariant under groups of transformations
- Asymptotic analysis of statistical estimators related to multigraphex processes under misspecification
- Causal Inference for Social Network Data
- Projective, sparse and learnable latent position network models
- Bayesian consensus clustering in multiplex networks
- Exchangeable random networks
- Fallacy of data-selective inference in modelling networks
- Network of scientific concepts: empirical analysis and modeling
- Bayesian modeling via discrete nonparametric priors
- Recent advances on mechanisms of network generation: community, exchangeability, and scale-free properties
- On the Truncation Error of a Superposed Gamma Process
- Local exchangeability
- Bayesian mixture models (in)consistency for the number of clusters
- Truncated two-parameter Poisson-Dirichlet approximation for Pitman-Yor process hierarchical models
- Efficient Estimation for Random Dot Product Graphs via a One-Step Procedure
- On sparsity, power-law, and clustering properties of graphex processes
- Finite-dimensional Discrete Random Structures and Bayesian Clustering
- Parameter Estimators of Sparse Random Intersection Graphs with Thinned Communities
- Tractably modelling dependence in networks beyond exchangeability
- Bayesian learning of graph substructures
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)
