Graph limits and exchangeable random graphs

MaRDI QIDQ3597136zbMATH OpenFDO

Authors Persi Diaconis, Svante Janson

Publication date 9 February 2009

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

zbMATH Keywords

de Finetti's theoremExchangeable arrayGraph limit

Mathematics Subject Classification ID

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

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.

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

Cited in

(only showing first 100 items - show all)

• Rate-optimal graphon estimation
• A representation of exchangeable hierarchies by sampling from random real trees
• On edge exchangeable random graphs
• Relative exchangeability with equivalence relations
• Bethe states of random factor graphs
• On the maximum density of fixed strongly connected subtournaments
• Combinatorial Lévy processes
• Limits of \(k\)-dimensional poset sequences
• Sparse maximum-entropy random graphs with a given power-law degree distribution
• Limit theorems for eigenvectors of the normalized Laplacian for random graphs
• Interval graph limits
• Spin systems on Bethe lattices
• Limits of structures and the example of tree semi-lattices
• Minimax rates in network analysis: graphon estimation, community detection and hypothesis testing
• On estimation and inference in latent structure random graphs
• Consistent nonparametric estimation for heavy-tailed sparse graphs
• Limits of sparse configuration models and beyond: graphexes and multigraphexes
• Higher-order fluctuations in dense random graph models
• A generalization of hierarchical exchangeability on trees to directed acyclic graphs
• On coprime percolation, the visibility graphon, and the local limit of the GCD profile
• Limit theorems for distributions invariant under groups of transformations
• A conversation with David J. Aldous
• Cycles of a given length in tournaments
• No additional tournaments are quasirandom-forcing
• Cut distance identifying graphon parameters over weak* limits
• A note on Fokker-Planck equations and graphons
• Edgeworth expansions for network moments
• Motif-based tests for bipartite networks
• On convergence for graphexes
• Cut norm discontinuity of triangular truncation of graphons
• Asymptotic behavior of common connections in sparse random networks
• Multivariate Hawkes processes on inhomogeneous random graphs
• A graphon counter example
• General erased-word processes: product-type filtrations, ergodic laws and Martin boundaries
• On finite exchangeability and conditional independence
• A general framework for Bayes structured linear models
• Bootstrap estimators for the tail-index and for the count statistics of graphex processes
• Relating the cut distance and the weak* topology for graphons
• Exponential-family models of random graphs: inference in finite, super and infinite population scenarios
• Graphon-valued stochastic processes from population genetics
• Sampling perspectives on sparse exchangeable graphs
• The geometry of continuous latent space models for network data
• Cut-norm and entropy minimization over \(\text{weak}^{\ast}\) limits
• Optimal graphon estimation in cut distance
• Matrix estimation by universal singular value thresholding
• Linear embeddings of graphs and graph limits
• Differential calculus on graphon space
• Generating hierarchial scale-free graphs from fractals
• Limits of discrete distributions and Gibbs measures on random graphs
• Decomposition of tournament limits
• A measure theoretic perspective on the space of Feynman diagrams
• Poset limits and exchangeable random posets
• Estimating and understanding exponential random graph models
• Co-clustering separately exchangeable network data
• Another conversation with Persi Diaconis
• Impartial digraphs
• On a question of Vera T. Sós about size forcing of graphons
• Replica symmetry breaking without replicas
• Sharp total variation bounds for finitely exchangeable arrays
• An introduction to large deviations for random graphs
• A limit theorem for scaled eigenvectors of random dot product graphs
• σ-algebras for quasirandom hypergraphs
• Poisson approximation of subgraph counts in stochastic block models and a graphon model
• A nonparametric view of network models and Newman–Girvan and other modularities
• On string graph limits and the structure of a typical string graph
• Limit of a nonpreferential attachment multitype network model
• Sparse random graphs with clustering
• Time evolution of dense multigraph limits under edge-conservative preferential attachment dynamics
• Hypergraph limits: A regularity approach
• Goodness of Fit of Logistic Regression Models for Random Graphs
• Variational Bayes model averaging for graphon functions and motif frequencies inference in \(W\)-graph models
• Consistency under sampling of exponential random graph models
• Computable exchangeable sequences have computable de Finetti measures
• Maximum likelihood estimation in the -model
• Universally consistent vertex classification for latent positions graphs
• From quasirandom graphs to graph limits and graphlets
• Multigraph limit of the dense configuration model and the preferential attachment graph
• Graphons and renormalization of large Feynman diagrams
• Sparse exchangeable graphs and their limits via graphon processes
• Relatively exchangeable structures
• Sparse graphs using exchangeable random measures
• An analytic approach to sparse hypergraphs: hypergraph removal
• Bayesian consensus clustering in multiplex networks
• The cut metric for probability distributions
• scientific article; zbMATH DE number 7626706 (Why is no real title available?)
• Random Simplicial Complexes: Models and Phenomena
• Vertex Nomination Between Graphs via Spectral Embedding and Quadratic Programming
• Iterative Collaborative Filtering for Sparse Matrix Estimation
• Testing for Equivalence of Network Distribution Using Subgraph Counts
• Exchangeable and sampling-consistent distributions on rooted binary trees
• A de Finetti-type representation of joint hierarchically exchange
• A unified approach to structural limits and limits of graphs with bounded tree-depth
• Classification on large networks: a quantitative bound via motifs and graphons (research)
• Matrix estimation, latent variable model and collaborative filtering
• Semantic limits of dense combinatorial objects
• Random walks on dense graphs and graphons
• Poset limits can be totally ordered
• On the density of transitive tournaments
• Book Review: Probabilistic symmetries and invariance principles
• Quantum invariant families of matrices in free probability

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)