Metrics for sparse graphs

MaRDI QIDQ3656241zbMATH OpenFDO

Authors Béla Bollobás, Oliver Riordan

Publication date 13 January 2010

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

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80)

Abstract: Recently, Bollob'as, Janson and Riordan introduced a very general family of random graph models, producing inhomogeneous random graphs with $Theta(n)$ edges. Roughly speaking, there is one model for each {em kernel}, i.e., each symmetric measurable function from $[0,1{]}^2$ to the non-negative reals, although the details are much more complicated. A different connection between kernels and random graphs arises in the recent work of Borgs, Chayes, Lov'asz, S'os, Szegedy and Vesztergombi. They introduced several natural metrics on dense graphs (graphs with $n$ vertices and $Theta(n^2)$ edges), showed that these metrics are equivalent, and gave a description of the completion of the space of all graphs with respect to any of these metrics in terms of {em graphons}, which are essentially bounded kernels. One of the most appealing aspects of this work is the message that sequences of inhomogeneous quasi-random graphs are in a sense completely general: any sequence of dense graphs contains such a subsequence. Our aim here is to briefly survey these results, and then to investigate to what extent they can be generalized to graphs with $o(n^2)$ edges. Although many of the definitions extend in a simple way, the connections between the various metrics, and between the metrics and random graph models, turn out to be much more complicated than in the dense case. We shall prove many partial results, and state even more conjectures and open problems, whose resolution would greatly enhance the currently rather unsatisfactory theory of metrics on sparse graphs. This paper deals mainly with graphs with $o(n^2)$ but $omega(n)$ edges: a companion paper [arXiv:0812.2656] will discuss the (more problematic still) case of {em extremely sparse} graphs, with O(n) edges.

Recommendations

• Sparse graphs: metrics and random models
• A metric for graphs
• Structural Properties of Sparse Graphs
• Structural Properties of Sparse Graphs
• scientific article; zbMATH DE number 4089609
• Girth of sparse graphs
• Estimating the global density of graphs by a sparseness index
• Sparse graphs using exchangeable random measures
• Sparsity. Graphs, structures, and algorithms
• Sparsity of weighted networks: measures and applications

Cited in

(55)

• An \(L^{p}\) theory of sparse graph convergence. II: LD convergence, quotients and right convergence
• Respondent-driven sampling and sparse graph convergence
• Interval graph limits
• The analytic evolution of Dyson-Schwinger equations via homomorphism densities
• Consistent nonparametric estimation for heavy-tailed sparse graphs
• Limits of sparse configuration models and beyond: graphexes and multigraphexes
• Higher-order fluctuations in dense random graph models
• Remarks on power-law random graphs
• A graphon counter example
• Exponential Chebyshev inequalities for random graphons and their applications
• Differential calculus on the space of countable labelled graphs
• The dynamics of non-perturbative phases via Banach bundles
• The complexities of nonperturbative computations
• Graphon-valued stochastic processes from population genetics
• Sampling and estimation for (sparse) exchangeable graphs
• Linear embeddings of graphs and graph limits
• A relative Szemerédi theorem
• Poset limits and exchangeable random posets
• Estimating and understanding exponential random graph models
• Support measures for graph data
• Nonlinear large deviations
• An introduction to large deviations for random graphs
• Connectivity of inhomogeneous random graphs
• Percolation on sequences of graphs
• Identifiability for graphexes and the weak kernel metric
• A metric for graphs
• Graphons and renormalization of large Feynman diagrams
• Sparse exchangeable graphs and their limits via graphon processes
• Convergence of graphs with intermediate density
• Interview with Yufei Zhao
• Testing for Equivalence of Network Distribution Using Subgraph Counts
• Continuum limits of nonlocal p-Laplacian variational problems on graphs
• 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
• Sparse graphs: metrics and random models
• An L^p theory of sparse graph convergence. I: Limits, sparse random graph models, and power law distributions
• Structural Properties of Sparse Graphs
• A counterexample to the Bollobás–Riordan conjectures on sparse graph limits
• The cut metric, random graphs, and branching processes
• A statistical mechanical model for non-perturbative regimes
• Continuum limit of p-Laplacian evolution problems on graphs: L^q graphons and sparse graphs
• Asymptotic for the cumulative distribution function of the degrees and homomorphism densities for random graphs sampled from a graphon
• Graph polynomials associated with Dyson-Schwinger equations
• Kontsevich Graphons
• From Dyson-Schwinger equations to quantum entanglement
• On sparsity, power-law, and clustering properties of graphex processes
• The large deviation principle for the Erdős-Rényi random graph
• Quasi-random graphs and graph limits
• Subsystems via quantum motions
• Asymptotic analysis of statistical estimators related to multigraphex processes under misspecification
• Tractably modelling dependence in networks beyond exchangeability
• The ``zero charge problem via graphon processes
• Rates of convergence for multivariate normal approximation with applications to dense graphs and doubly indexed permutation statistics
• Graph limits and hereditary properties

This page was built for publication: Metrics for sparse graphs

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