Edge-exchangeable graphs and sparsity

Abstract

A known failing of many popular random graph models is that the Aldous-Hoover Theorem guarantees these graphs are dense with probability one; that is, the number of edges grows quadratically with the number of nodes. This behavior is considered unrealistic in observed graphs. We define a notion of edge exchangeability for random graphs in contrast to the established notion of infinite exchangeability for random graphs --- which has traditionally relied on exchangeability of nodes (rather than edges) in a graph. We show that, unlike node exchangeability, edge exchangeability encompasses models that are known to provide a projective sequence of random graphs that circumvent the Aldous-Hoover Theorem and exhibit sparsity, i.e., sub-quadratic growth of the number of edges with the number of nodes. We show how edge-exchangeability of graphs relates naturally to existing notions of exchangeability from clustering (a.k.a. partitions) and other familiar combinatorial structures.

arXiv commentThis paper appeared in the NIPS 2015 Workshop on Networks in the Social and Information Sciences, http://stanford.edu/~jugander/NetworksNIPS2015/. An earlier version appeared in the NIPS 2015 Workshop Bayesian Nonparametrics: The Next Generation, https://sites.google.com/site/nipsbnp2015/

References in corpus (2)

• Power laws, Pareto distributions and Zipf's law
• Cluster and Feature Modeling from Combinatorial Stochastic Processes

Cited by in corpus (12)

• Exponential-Family Models of Random Graphs: Inference in Finite-, Super-, and Infinite Population Scenarios
• On edge exchangeable random graphs
• Subsampling large graphs and invariance in networks
• Sparse power-law network model for reliable statistical predictions based on sampled data
• A unified construction for series representations and finite approximations of completely random measures
• Priors on exchangeable directed graphs
• A Bayesian model for sparse graphs with flexible degree distribution and overlapping community structure
• Pseudo-likelihood-based $M$-estimation of random graphs with dependent edges and parameter vectors of increasing dimension
• A note on quickly sampling a sparse matrix with low rank expectation
• Local Exchangeability
• A Nonparametric Bayesian Model for Sparse Dynamic Multigraphs
• Asymptotic Analysis of Statistical Estimators related to MultiGraphex Processes under Misspecification