On edge exchangeable random graphs

Abstract

We study a recent model for edge exchangeable random graphs introduced by Crane and Dempsey; in particular we study asymptotic properties of the random simple graph obtained by merging multiple edges. We study a number of examples, and show that the model can produce dense, sparse and extremely sparse random graphs. One example yields a power-law degree distribution. We give some examples where the random graph is dense and converges a.s. in the sense of graph limit theory, but also an example where a.s. every graph limit is the limit of some subsequence. Another example is sparse and yields convergence to a non-integrable generalized graphon defined on $(0,\infty )$.

40 pages

References in corpus (6)

• Graph limits and exchangeable random graphs
• Local limit theorems for finite and infinite urn models
• Edge-exchangeable graphs and sparsity
• Graphons, cut norm and distance, couplings and rearrangements
• Graphons and cut metric on sigma-finite measure spaces
• Relational exchangeability

Cited by in corpus (12)

• Network Geometry
• Exponential-Family Models of Random Graphs: Inference in Finite-, Super-, and Infinite Population Scenarios
• Subsampling large graphs and invariance in networks
• Preferential Attachment and Vertex Arrival Times
• Preferential attachment without vertex growth: emergence of the giant component
• Sparse power-law network model for reliable statistical predictions based on sampled data
• A Dynamic Edge Exchangeable Model for Sparse Temporal Networks
• Anomalous Edge Detection in Edge Exchangeable Social Network Models
• A Bayesian model for sparse graphs with flexible degree distribution and overlapping community structure
• Local Exchangeability
• Asymptotic Analysis of Statistical Estimators related to MultiGraphex Processes under Misspecification
• Random Geometric Graphs on Euclidean Balls