Identifiability for graphexes and the weak kernel metric

DOI10.1007/978-3-662-59204-5_3zbMATH Open1443.05169arXiv1804.03277OpenAlexW2797787146MaRDI QIDQ3295264FDOQ3295264

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)

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.

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

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

zbMATH Keywords

identifiabilityPoisson processregularitysparse networkexpected subgraph countsgraphexweak kernel metric

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (8)

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

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)