Sparse graphs using exchangeable random measures
From MaRDI portal
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
- 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 Representation of Independent Increment Processes without Gaussian Components
- 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 nonparametric Plackett-Luce models for the analysis of preferences for college degree programmes
- Bayesian Poisson process partition calculus with an application to Bayesian Lévy moving averages
- 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 and partially exchangeable random partitions
- Exchangeable random measures in the plane
- Exchangeable Rasch matrices
- 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
- scientific article; zbMATH DE number 3248623 (Why is no real title available?)
- 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 a conditionally Poissonian graph process
- On Lewis' simulation method for point processes
- 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 method of moments and degree distributions for network models
- The phase transition in inhomogeneous random graphs
- The Structure and Function of Complex Networks
- The structure of scientific collaboration networks
Cited in
(81)- An improved algorithm for generalized community structure inference in complex networks
- On edge exchangeable random graphs
- Integrability conditions for compound random measures
- Exchangeable trait allocations
- Sufficientness postulates for Gibbs-type priors and hierarchical generalizations
- Sparse maximum-entropy random graphs with a given power-law degree distribution
- Approximating predictive probabilities of Gibbs-type priors
- Minimax rates in network analysis: graphon estimation, community detection and hypothesis testing
- A statistical framework for modern network science
- Network representation using graph root distributions
- Sparse networks with core-periphery structure
- Nonexchangeable random partition models for microclustering
- Nonnegative Bayesian nonparametric factor models with completely random measures
- Limits of sparse configuration models and beyond: graphexes and multigraphexes
- Truncated simulation and inference in edge-exchangeable networks
- Asymptotic behavior of the number of distinct values in a sample from the geometric stick-breaking process
- Higher-order fluctuations in dense random graph models
- A generalization of hierarchical exchangeability on trees to directed acyclic graphs
- Limit theorems for distributions invariant under groups of transformations
- Infinite-color randomly reinforced urns with dominant colors
- On convergence for graphexes
- Rejoinder to the discussion of ``Bayesian graphical models for modern biological applications
- Asymptotic behavior of common connections in sparse random networks
- A hierarchical Bayesian model for predicting ecological interactions using scaled evolutionary relationships
- Bootstrap estimators for the tail-index and for the count statistics of graphex processes
- Exponential-family models of random graphs: inference in finite, super and infinite population scenarios
- Sampling perspectives on sparse exchangeable graphs
- Sampling and estimation for (sparse) exchangeable graphs
- Hierarchical normalized completely random measures for robust graphical modeling
- Two part envelopes for rejection sampling of some completely random measures
- Bayesian nonparametric sparse VAR models
- Local 2-separators
- Truncated Poisson-Dirichlet approximation for Dirichlet process hierarchical models
- Graph theory. Abstracts from the workshop held January 2--8, 2022
- Core-periphery structure in networks: a statistical exposition
- Identifiability for graphexes and the weak kernel metric
- Non-parametric overlapping community detection
- Metrics for sparse graphs
- Probabilities of Sentences about Very Sparse Random Graphs
- Sparse exchangeable graphs and their limits via graphon processes
- Bayesian consensus clustering in multiplex networks
- Gibbs partitions, Riemann-Liouville fractional operators, Mittag-Leffler functions, and fragmentations derived from stable subordinators
- Exchangeable Random Measures for Sparse and Modular Graphs with Overlapping Communities
- Nonparametric modeling of higher-order interactions via hypergraphons
- Random walks on dense graphs and graphons
- On exchangeability in network models
- On the Truncation Error of a Superposed Gamma Process
- Parameter Estimators of Sparse Random Intersection Graphs with Thinned Communities
- Exchangeable random networks
- Modularity Maximization for Graphons
- Inference for High-Dimensional Exchangeable Arrays
- Local exchangeability
- A unified construction for series representations and finite approximations of completely random measures
- Efficient Estimation for Random Dot Product Graphs via a One-Step Procedure
- Efficient Simulation of Sparse Graphs of Point Processes
- Hierarchical Network Models for Exchangeable Structured Interaction Processes
- Bayesian learning of graph substructures
- Causal Inference for Social Network Data
- Exact simulation of Poisson-Dirichlet distribution and generalised gamma process
- Projective, sparse and learnable latent position network models
- On sparsity, power-law, and clustering properties of graphex processes
- Network of scientific concepts: empirical analysis and modeling
- Truncated two-parameter Poisson-Dirichlet approximation for Pitman-Yor process hierarchical models
- Fallacy of data-selective inference in modelling networks
- Finite-dimensional Discrete Random Structures and Bayesian Clustering
- Bayesian modeling via discrete nonparametric priors
- Asymptotic analysis of statistical estimators related to multigraphex processes under misspecification
- Recent advances on mechanisms of network generation: community, exchangeability, and scale-free properties
- Tractably modelling dependence in networks beyond exchangeability
- Bayesian mixture models (in)consistency for the number of clusters
- A Smoothed-Bayesian Approach to Frequency Recovery from Sketched Data
- Posterior sampling from truncated Ferguson-Klass representation of normalised completely random measure mixtures
- Multiway empirical likelihood
- Next waves in veridical network embedding*
- Fast unfolding of communities in large networks: 15 years later
- ACRONYM: Augmented Degree Corrected, Community Reticulated Organized Network Yielding Model
- Merging rate of opinions via optimal transport on random measures
- Inverse clustering of Gibbs partitions via independent fragmentation and dual dependent coagulation operators
- Compound Poisson models for weighted networks with applications in finance
- A note on nonparametric inference for species variety with Gibbs-type priors
- Distribution-free connectivity testing for sparse graphs
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)
