Identifiability for graphexes and the weak kernel metric

DOI10.1007/978-3-662-59204-5_3MaRDI QIDQ3295264zbMATH OpenOpenAlexFDO

Authors Henry Cohn, László Miklós Lovász, Christian Borgs, Jennifer T. Chayes

Publication date 8 July 2020

Published in Bolyai Society Mathematical Studies (Search for Journal in Brave)

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

zbMATH Keywords

expected subgraph countsgraphexidentifiabilityPoisson processregularitysparse networkweak kernel metric

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Exchangeability for stochastic processes (60G09) Point processes (e.g., Poisson, Cox, Hawkes processes) (60G55) Random measures (60G57) Nonparametric estimation (62G05)

Abstract: In two recent papers by Veitch and Roy and by Borgs, Chayes, Cohn, and Holden, a new class of sparse random graph processes based on the concept of graphexes over $sigma$-finite measure spaces has been introduced. In this paper, we introduce a metric for graphexes that generalizes the cut metric for the graphons of the dense theory of graph convergence. We show that a sequence of graphexes converges in this metric if and only if the sequence of graph processes generated by the graphexes converges in distribution. In the course of the proof, we establish a regularity lemma and determine which sets of graphexes are precompact under our metric. Finally, we establish an identifiability theorem, characterizing when two graphexes are equivalent in the sense that they lead to the same process of random graphs.

Recommendations

• Sparse exchangeable graphs and their limits via graphon processes
• On convergence for graphexes
• Sampling perspectives on sparse exchangeable graphs
• Sparse graphs: metrics and random models
• Metrics for sparse graphs

Cites work

• An L^p theory of sparse graph convergence. I: Limits, sparse random graph models, and power law distributions
• An Introduction to the Theory of Point Processes
• Convergent sequences of dense graphs. I: Subgraph frequencies, metric properties and testing
• Convergent sequences of dense graphs. II. Multiway cuts and statistical physics
• Counting graph homomorphisms
• Graphons, cut norm and distance, couplings and rearrangements
• scientific article; zbMATH DE number 1022658 (Why is no real title available?)
• scientific article; zbMATH DE number 3274494 (Why is no real title available?)
• Limits of dense graph sequences
• Measure theory
• Moments of two-variable functions and the uniqueness of graph limits
• Probabilistic Symmetries and Invariance Principles
• Probability Inequalities for Sums of Bounded Random Variables
• Quick approximation to matrices and applications
• Regularity partitions and the topology of graphons
• Sampling and estimation for (sparse) exchangeable graphs
• Sampling perspectives on sparse exchangeable graphs
• Sparse exchangeable graphs and their limits via graphon processes
• Sparse graphs using exchangeable random measures
• Szemerédi's lemma for the analyst

Cited in

(9)

• An optimal lower bound on the number of variables for graph identification
• Limits of sparse configuration models and beyond: graphexes and multigraphexes
• On convergence for graphexes
• Bootstrap estimators for the tail-index and for the count statistics of graphex processes
• Sparse exchangeable graphs and their limits via graphon processes
• On the dense preferential attachment graph models and their graphon induced counterpart
• Subgraph densities in Markov spaces
• Recent advances on mechanisms of network generation: community, exchangeability, and scale-free properties
• The spectral barycentre of a set of graphs with community structure

This page was built for publication: Identifiability for graphexes and the weak kernel metric

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