Graph limits and exchangeable random graphs

zbMATH Open1162.60009arXiv0712.2749MaRDI QIDQ3597136FDOQ3597136

Authors: Persi Diaconis, Svante Janson 

Publication date: 9 February 2009

Abstract: 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 Lovasz and many coauthors). Along the way, we translate the graph theory into more classical probability.

Full work available at URL: https://arxiv.org/abs/0712.2749

Recommendations

• Multigraph limits and exchangeability
• On edge exchangeable random graphs
• Quasi-random graphs and graph limits
• Sparse exchangeable graphs and their limits via graphon processes
• On exchangeable random variables and the statistics of large graphs and hypergraphs
• From quasirandom graphs to graph limits and graphlets
• Limits of discrete distributions and Gibbs measures on random graphs
• Extremal results in random graphs
• On limits of sparse random graphs
• scientific article; zbMATH DE number 3997847

zbMATH Keywords

de Finetti's theoremExchangeable arrayGraph limit

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graph representations (geometric and intersection representations, etc.) (05C62) Exchangeability for stochastic processes (60G09)

Cited In (only showing first 100 items - show all)

• Another conversation with Persi Diaconis
• Consistent nonparametric estimation for heavy-tailed sparse graphs
• Sparse random graphs with clustering
• Spin systems on Bethe lattices
• Consistency under sampling of exponential random graph models
• Maximum likelihood estimation in the \(\beta\)-model
• General erased-word processes: product-type filtrations, ergodic laws and Martin boundaries
• A limit theorem for scaled eigenvectors of random dot product graphs
• Universally consistent vertex classification for latent positions graphs
• RELATIVELY EXCHANGEABLE STRUCTURES
• Random graphs with a given degree sequence
• Co-clustering separately exchangeable network data
• On convergence for graphexes
• Hypergraph limits: A regularity approach
• Exponential-family models of random graphs: inference in finite, super and infinite population scenarios
• Sharp total variation bounds for finitely exchangeable arrays
• Matrix estimation by universal singular value thresholding
• Quantum invariant families of matrices in free probability
• Combinatorial Lévy processes
• From quasirandom graphs to graph limits and graphlets
• Differential calculus on graphon space
• Mixture models and networks: The stochastic blockmodel
• The geometry of continuous latent space models for network data
• On edge exchangeable random graphs
• An analytic approach to stability
• Testing for Equivalence of Network Distribution Using Subgraph Counts
• Generating hierarchial scale-free graphs from fractals
• Limits of discrete distributions and Gibbs measures on random graphs
• Multigraph limit of the dense configuration model and the preferential attachment graph
• On the typical structure of graphs in a monotone property
• σ-algebras for quasirandom hypergraphs
• Multigraph limits and exchangeability
• Graph limits and hereditary properties
• Multivariate Hawkes processes on inhomogeneous random graphs
• Poset limits can be totally ordered
• Relative exchangeability with equivalence relations
• Estimating and understanding exponential random graph models
• Limit of a nonpreferential attachment multitype network model
• On estimation and inference in latent structure random graphs
• An introduction to large deviations for random graphs
• Invariant measures via inverse limits of finite structures
• Cycles of a given length in tournaments
• Random Walks on Dense Graphs and Graphons
• Motif-based tests for bipartite networks
• Computable de Finetti measures
• A note on Fokker-Planck equations and graphons
• On the Density of Transitive Tournaments
• Variational Bayes model averaging for graphon functions and motif frequencies inference in \(W\)-graph models
• The large deviation principle for the Erdős-Rényi random graph
• Graphons and renormalization of large Feynman diagrams
• Rate-optimal graphon estimation
• Quasi-random graphs and graph limits
• Exchangeable interval hypergraphs and limits of ordered discrete structures
• A conversation with David J. Aldous
• Subsampling bootstrap of count features of networks
• The cut metric, random graphs, and branching processes
• Linear embeddings of graphs and graph limits
• Interval graph limits
• A measure theoretic perspective on the space of Feynman diagrams
• Limit theorems for eigenvectors of the normalized Laplacian for random graphs
• Sparse Graphs Using Exchangeable Random Measures
• The method of moments and degree distributions for network models
• Computable exchangeable sequences have computable de Finetti measures
• Limits of structures and the example of tree semi-lattices
• Tree limits and limits of random trees
• Rates of convergence for multivariate normal approximation with applications to dense graphs and doubly indexed permutation statistics
• Sparse exchangeable graphs and their limits via graphon processes
• A nonparametric view of network models and Newman–Girvan and other modularities
• Book Review: Probabilistic symmetries and invariance principles
• A representation of exchangeable hierarchies by sampling from random real trees
• On String Graph Limits and the Structure of a Typical String Graph
• Poset limits and exchangeable random posets
• No additional tournaments are quasirandom-forcing
• Semantic limits of dense combinatorial objects
• Title not available (Why is that?)
• Bethe states of random factor graphs
• On the maximum density of fixed strongly connected subtournaments
• Title not available (Why is that?)
• Decomposition of tournament limits
• Graphon-valued stochastic processes from population genetics
• Vertex Nomination Between Graphs via Spectral Embedding and Quadratic Programming
• Bayesian consensus clustering in multiplex networks
• Impartial digraphs
• The intransitive dice kernel: \( \frac{1\kern-2pt\mathrm{I}_{x\ge y}-1\kern-2pt\mathrm{I}_{x\le y}}{4} - \frac{3(x-y)(1+xy)}{8} \)
• Classification on Large Networks: A Quantitative Bound via Motifs and Graphons (Research)
• Cut distance identifying graphon parameters over weak* limits
• Sampling perspectives on sparse exchangeable graphs
• Random Simplicial Complexes: Models and Phenomena
• A Unified Approach to Structural Limits and Limits of Graphs with Bounded Tree-Depth
• Cut-norm and entropy minimization over \(\text{weak}^{\ast}\) limits
• Edgeworth expansions for network moments
• Limits of \(k\)-dimensional poset sequences
• Dense multigraphon-valued stochastic processes and edge-changing dynamics in the configuration model
• Localization in 1D non-parametric latent space models from pairwise affinities
• Network Estimation by Mixing: Adaptivity and More
• Sparse maximum-entropy random graphs with a given power-law degree distribution
• Title not available (Why is that?)
• Harmonic analysis of symmetric random graphs
• On a question of Vera T. Sós about size forcing of graphons
• Projective, sparse and learnable latent position network models

This page was built for publication: Graph limits and exchangeable random graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3597136)