Graph limits and exchangeable random graphs

By Persi Diaconis, Svante Janson. 2007

418 citations recorded by the source corpus.

We develop a clear connection between deFinetti's theorem for exchangeable arrays (work of Aldous{Hoover{Kallenberg) and the emerging area of graph limits (work of Lov asz and many coauthors). Along the way, we translate the graph theory into more classical prob- ability.

Subfields: Computational Theory and Mathematics, Discrete Mathematics and Combinatorics, Geometry and Topology

View Paper: https://www.semanticscholar.org/paper/4fcfc3a3263d3d8487e887165ae4200cdac269c5

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Discrete Mathematics and Combinatorics

In Geometry and Topology

Citations in the corpus

INVARIANT MEASURES CONCENTRATED ON COUNTABLE STRUCTURES (2012, methodology): “phs. Before connecting our methods to the theory of dense graph limits, we describe how invariant measures arise in this context. We begin with some denitions from [LS06]; for more details, see also [DJ08], and [Lov09, x3.1]. A graphon is dened to be a symmetric measurable function W: [0;1]2 ![0;1].”
Matrix estimation by Universal Singular Value Thresholding (2012, background): “Such functions also arise in the related study of weakly exchangeable random arrays [5, 9, 42, 57].”
Limit theorems for eigenvectors of the normalized Laplacian for random graphs (2016, background): “A random dot product graph on n vertices is also, when viewed as an induced subgraph of an infinite graph, an exchangeable random graph [17].”
A Survey of Statistical Network Models (2009, methodology): “The proof relies on the exchangeability results developed in the statistics community [15; 165] applied to paired measurements [84].”
Metrics for sparse graphs (2007, background): “(This is the approach taken in the sparse case by Bollobás, Janson and Riordan [8].)”
Estimating and understanding exponential random graph models (2011, methodology): “(See also the related work of Austin [3] and Diaconis and Janson [18] which traces this back to work of Aldous [1], Hoover [33] and Kallenberg [35].)”
An introduction to large deviations for random graphs (2016, background): “For connections with the theory of exchangeable arrays in probability theory, see [1, 24, 27, 29].”
Graphons, cut norm and distance, couplings and rearrangements (2010, methodology): “One definition is the following, which has the advantage that it easily is adapted to many other situations such as hypergraphs, bipartite graphs, directed graphs, compactly decorated graphs and posets, see [4, 14, 15, 24, 26, 36, 40, 44, 52, 53].”
On exchangeable random variables and the statistics of large graphs and hypergraphs (2008, result): “As this paper neared completion, many of the main relations between exchangeability and hypergraph theory that it was written to advertise were also independently reported in work of Diaconis and Janson [20].”
A nonparametric view of network models and Newman–Girvan and other modularities (2009, background): “As Diaconis and Janson (13) point out h(.”
Probability and Mathematical Genetics: More uses of exchangeability: representations of complex random structures (2009, background): “ence in the equivalent way via (10) and obtained the same characterization. This is the second recent rediscovery of special cases of partially exchangeable representation theory. Diaconis and Janson [27] give a very clear and detailed account of the relation between the two settings, and Diaconis-H”
Large Networks and Graph Limits (2012, methodology): “We conclude this section with a construction of a convergent graph sequence from a countable random graph model (without the locality assumption) given independently by Lovász and Szegedy [2012a] and Diaconis and Janson ([2008], Theorem 5.”
A Limit Theorem for Scaled Eigenvectors of Random Dot Product Graphs (2013, background): “In Diaconis and Janson (2008), Diaconis and Janson prove several fundamental results on graph limits, constructed via subgraph counts, for exchangeable graphs.”
The large deviation principle for the Erd\H{o}s-R\'enyi random graph (2010, methodology): “We quote the definition verbatim from [22] (see also [6, 7, 12]).”
Relational Pooling for Graph Representations (2019, methodology): “Joint RP. Inspired by joint exchangeability (Aldous, 1981; Diaconis & Janson, 2008; Orbanz & Roy, 2015), joint RP deﬁnes isomorphic-invariant functions over non-bipartite graphs, whether with directed or undirected edges, as where f is an arbitrary (and possibly permutation-sensitive ) function of…”
Random graphs with a given degree sequence (2010, methodology): “See also the related work of Diaconis and Janson [19] and Austin [2] which traces this back to work of Aldous [1] and Hoover [28].”