Sparse graphs: metrics and random models

DOI10.1002/RSA.20334MaRDI QIDQ5198669zbMATH OpenOpenAlexFDO

Authors Béla Bollobás, Oliver Riordan

Publication date 9 August 2011

Published in Random Structures \& Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

graph metricssparse random graphs

Mathematics Subject Classification ID

Distance in graphs (05C12) Random graphs (graph-theoretic aspects) (05C80)

Abstract: Recently, Bollob'as, Janson and Riordan introduced a family of random graph models producing inhomogeneous graphs with $n$ vertices and $Theta(n)$ edges whose distribution is characterized by a kernel, i.e., a symmetric measurable function $ka:[0,1{]}^{2}o[0,infty)$. To understand these models, we should like to know when different kernels $ka$ give rise to `similar' graphs, and, given a real-world network, how `similar' is it to a typical graph $G(n,ka)$ derived from a given kernel $ka$. The analogous questions for dense graphs, with $Theta(n^2)$ edges, are answered by recent results of Borgs, Chayes, Lov'asz, S'os, Szegedy and Vesztergombi, who showed that several natural metrics on graphs are equivalent, and moreover that any sequence of graphs converges in each metric to a graphon, i.e., a kernel taking values in $[0,1]$. Possible generalizations of these results to graphs with $o(n^2)$ but $omega(n)$ edges are discussed in a companion paper [arXiv:0708.1919]; here we focus only on graphs with $Theta(n)$ edges, which turn out to be much harder to handle. Many new phenomena occur, and there are a host of plausible metrics to consider; many of these metrics suggest new random graph models, and vice versa.

Recommendations

• Metrics for sparse graphs
• An L^p theory of sparse graph convergence. I: Limits, sparse random graph models, and power law distributions
• Sparse random graphs with clustering
• Measures on the square as sparse graph limits
• Connectivity of inhomogeneous random graphs

Cites work

• A conjecture concerning a limit of non-Cayley graphs
• A spectral heuristic for bisecting random graphs
• Asymptotic Enumeration of Spanning Trees
• Automorphism groups of graphs as topological groups
• Bisecting sparse random graphs
• Bounds on the bisection width for random \(d\)-regular graphs
• Convergent sequences of dense graphs. I: Subgraph frequencies, metric properties and testing
• Convergent sequences of dense graphs. II. Multiway cuts and statistical physics
• Endomorphisms of symbolic algebraic varieties
• Generalized quasirandom graphs
• Graph limits and parameter testing
• Group-invariant percolation on graphs
• scientific article; zbMATH DE number 1107723 (Why is no real title available?)
• scientific article; zbMATH DE number 2079360 (Why is no real title available?)
• Hyperlinear and Sofic Groups: A Brief Guide
• Improved approximation of Max-Cut on graphs of bounded degree
• Limits of dense graph sequences
• Max Cut for Random Graphs with a Planted Partition
• Maximum weight independent sets and matchings in sparse random graphs. Exact results using the local weak convergence method
• On the editing distance of graphs
• Percolation on nonunimodular transitive graphs
• Processes on unimodular random networks
• Quick approximation to matrices and applications
• Random MAX SAT, random MAX CUT, and their phase transitions
• Recurrence of distributional limits of finite planar graphs
• Rounding of continuous random variables and oscillatory asymptotics
• Sofic groups and direct finiteness.
• Sofic groups and dynamical systems.
• The cut metric, random graphs, and branching processes
• The isoperimetric number of random regular graphs
• The phase transition in inhomogeneous random graphs

Cited in

(56)

• Metric models for random graphs
• Finite graphs and amenability
• Sparse quasi-random graphs
• Empirical spectral distributions of sparse random graphs
• Limits of sparse configuration models and beyond: graphexes and multigraphexes
• On the expected number of perfect matchings in cubic planar graphs
• On the significance of edges for connectivity in uncertain random graphs
• Almost unimodal and real-rooted graph polynomials
• New results relating independence and matchings
• A novel approach to subgraph selection with multiple weights on arcs
• Measures on the square as sparse graph limits
• Structural sparsity of complex networks: bounded expansion in random models and real-world graphs
• On the almost eigenvectors of random regular graphs
• Asymptotic behavior and distributional limits of preferential attachment graphs
• Limits of locally-globally convergent graph sequences
• Connectivity of inhomogeneous random graphs
• Kőnig's line coloring and Vizing's theorems for graphings
• Sparse random graphs with clustering
• Percolation on sequences of graphs
• First order convergence of matroids
• Identifiability for graphexes and the weak kernel metric
• Metrics for sparse graphs
• Probabilities of Sentences about Very Sparse Random Graphs
• From quasirandom graphs to graph limits and graphlets
• Sparsity. Graphs, structures, and algorithms
• Weak regularity and finitely forcible graph limits
• Right-convergence of sparse random graphs
• The diameter of inhomogeneous random graphs
• Finitely forcible graphons and permutons
• Left and right convergence of graphs with bounded degree
• First order limits of sparse graphs: plane trees and path-width
• Action convergence of operators and graphs
• Graph space: using both geometric and probabilistic structure to evaluate statistical graph models
• Continuum limit of the nonlocal p-Laplacian evolution problem on random inhomogeneous graphs
• Semantic limits of dense combinatorial objects
• Optimal couplings between sparse block models
• Uniform rank gradient, cost, and local-global convergence
• Local-global convergence, an analytic and structural approach
• An L^p theory of sparse graph convergence. I: Limits, sparse random graph models, and power law distributions
• Unimodular random trees
• Structural Properties of Sparse Graphs
• The interpolation method for random graphs with prescribed degrees
• Property graphs -- a statistical model for fire and explosion losses based on graph theory
• On local weak limit and subgraph counts for sparse random graphs
• scientific article; zbMATH DE number 7651162 (Why is no real title available?)
• The cut metric, random graphs, and branching processes
• Graph limits: An alternative approach to s‐graphons
• Efficient Simulation of Sparse Graphs of Point Processes
• On a curious problem and what it lead to
• On the limit of large girth graph sequences
• The space of actions, partition metric and combinatorial rigidity
• Global stability for McKean-Vlasov equations on large networks
• Leaves of preferential attachment trees
• Strong modeling limits of graphs with bounded tree-width
• Large deviations of empirical neighborhood distribution in sparse random graphs
• A short proof of the equivalence of left and right convergence for sparse graphs

This page was built for publication: Sparse graphs: metrics and random models

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