Graph sequences sampled from Robinson graphons
From MaRDI portal
(Redirected from Graph sequences sampled from Robinson graphons)
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 on the space of graphons, introduced in [CGH15], aims to measure the extent to which a graphon exhibits the Robinson property: for all , . Robinson graphons form a model for graphs with a natural line embedding so that most edges are local. Function is compatible with the cut-norm , in the sense that graphons close in cut-norm have similar -values. Here we show the converse, by proving that every graphon can be approximated by a Robinson graphon so that is bounded in terms of . We then use classical techniques from functional analysis to show that a converging graph sequence converges to a Robinson graphon if and only if . Finally, using probabilistic techniques we show that the rate of convergence of for graph sequences sampled from a Robinson graphon can differ substantially depending on how strongly 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
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)