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

sparse random graphsgraph metrics

Mathematics Subject Classification ID

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

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

• scientific article; zbMATH DE number 1107723 (Why is no real title available?)
• scientific article; zbMATH DE number 2079360 (Why is no real title available?)
• 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
• 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

(54)

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

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)