Graph sequences sampled from Robinson graphons

DOI10.1016/J.EJC.2023.103859MaRDI QIDQ6146495zbMATH OpenOpenAlexFDO

Authors Mahya Ghandehari, Jeannette Janssen

Publication date 5 February 2024

Published in European Journal of Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

graph limitsinterval graphslinear embeddingrandom graphs

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Random graphs (graph-theoretic aspects) (05C80) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40) Combinatorial probability (60C05)

Abstract: The function $Gamma$ on the space of graphons, introduced in [CGH${}^{+}$15], aims to measure the extent to which a graphon $w$ exhibits the Robinson property: for all $x<y<z$, $w(x,z)leqminw(x,y),w(y,z)$. Robinson graphons form a model for graphs with a natural line embedding so that most edges are local. Function $Gamma$ is compatible with the cut-norm $|cdot{|}_{B}ox$, in the sense that graphons close in cut-norm have similar $Gamma$-values. Here we show the converse, by proving that every graphon $w$ can be approximated by a Robinson graphon $R_w$ so that $|w-R_w{|}_{B}ox$ is bounded in terms of $Gamma(w)$. We then use classical techniques from functional analysis to show that a converging graph sequence $G_n$ converges to a Robinson graphon if and only if $Gamma(G_n)ightarrow0$. Finally, using probabilistic techniques we show that the rate of convergence of $Gamma$ for graph sequences sampled from a Robinson graphon can differ substantially depending on how strongly $w$ exhibits the Robinson property.

Recommendations

• Robust recovery of Robinson property in L^p-graphons: a cut-norm approach
• Relating the cut distance and the weak* topology for graphons
• Monotone graph limits and quasimonotone graphs
• Convergent sequences of dense graphs. II. Multiway cuts and statistical physics
• Linear embeddings of graphs and graph limits

Cites work

• A Popularity Scaled Latent Space Model for Large-Scale Directed Social Network
• A structural characterization for certifying Robinsonian matrices
• An optimal algorithm to recognize Robinsonian dissimilarities
• An optimization parameter for seriation of noisy data
• Community detection and stochastic block models: recent developments
• Large networks and graph limits
• Latent Space Approaches to Social Network Analysis
• Limits of dense graph sequences
• Limits of randomly grown graph sequences
• Linear embeddings of graphs and graph limits
• Monotone graph limits and quasimonotone graphs
• Optimal rates of statistical seriation
• Quick approximation to matrices and applications
• Seriation and matrix reordering methods: An historical overview
• Seriation in the presence of errors: a factor 16 approximation algorithm for \(l_{\infty }\)-fitting Robinson structures to distances
• Spectral ranking using seriation
• The geometry of continuous latent space models for network data
• Threshold graph limits and random threshold graphs

Cited in

(1)

• Robust recovery of Robinson property in L^p-graphons: a cut-norm approach

This page was built for publication: Graph sequences sampled from Robinson graphons

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