Edge exchangeable models for network data

Abstract

Exchangeable models for countable vertex-labeled graphs cannot replicate the large sample behaviors of sparsity and power law degree distribution observed in many network datasets. Out of this mathematical impossibility emerges the question of how network data can be modeled in a way that reflects known empirical behaviors and respects basic statistical principles. We address this question by observing that edges, not vertices, act as the statistical units in networks constructed from interaction data, making a theory of edge-labeled networks more natural for many applications. In this context we introduce the concept of {\em edge exchangeability}, which unlike its vertex exchangeable counterpart admits models for networks with sparse and/or power law structure. Our characterization of edge exchangeable networks gives rise to a class of nonparametric models, akin to graphon models in the vertex exchangeable setting. Within this class, we identify a tractable family of distributions with a clear interpretation and suitable theoretical properties, whose significance in estimation, prediction, and testing we demonstrate.

35 pages; 8 figures; previously cited under title "Edge exchangeable network models and the power law" in arXiv:1509.08185 and elsewhere

References in corpus (5)

• Cooperative Game Theory Approaches for Network Partitioning
• Reaction-diffusion processes and metapopulation models in heterogeneous networks
• The Class of Random Graphs Arising from Exchangeable Random Measures
• A framework for statistical network modeling
• Atypical scaling behavior persists in real world interaction networks

Cited by in corpus (14)

• Dense Power-law Networks and Simplicial Complexes
• On edge exchangeable random graphs
• A framework for statistical network modeling
• On the reorderability of node-filtered order complexes
• Subsampling large graphs and invariance in networks
• Preferential Attachment and Vertex Arrival Times
• Relational exchangeability
• Minimax Rates in Network Analysis: Graphon Estimation, Community Detection and Hypothesis Testing
• Hierarchical network models for structured exchangeable interaction processes
• A Dynamic Edge Exchangeable Model for Sparse Temporal Networks
• Priors on exchangeable directed graphs
• The Four Point Permutation Test for Latent Block Structure in Incidence Matrices
• Bayesian Model Selection on Random Networks
• Stochastic Blockmodels with Edge Information