Metrics for sparse graphs

By Béla Bollobás, Oliver Riordan. 2007

100 citations recorded by the source corpus.

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.

Subfields: Computational Theory and Mathematics, Discrete Mathematics and Combinatorics, Geometry and Topology

View Paper: https://www.semanticscholar.org/paper/d08566773ce25465f191008ab8a181b8752024c3

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Discrete Mathematics and Combinatorics

In Geometry and Topology

Citations in the corpus

An $L^{p}$ theory of sparse graph convergence II: LD convergence, quotients and right convergence (2014, methodology): “The work of Bollobás and Riordan in [2] and the prior work on dense graph sequences amount to the special case p = ∞, while L graphons with p < ∞ describe limiting behaviors that”
Estimating and understanding exponential random graph models (2011, methodology): “This model has been the subject of extensive investigations since the pioneering work of Erdős and Rényi [19], yielding a large body of literature (see [8, 34] for partial surveys).”
Nonlinear large deviations (2014, background): “ Szemer´edi’s lemma makes it impossible to extend the results of [16, 17, 15] to sparse graphs. Serious attempts have been made at formulating a sparse graph limit theory and sparse regularity lemmas [3, 5, 6], but it is unlikely that these will provide the precision required for large deviations. T”
The large deviation principle for the Erd\H{o}s-R\'enyi random graph (2010, background): “as (see e.g. [10]). Their theory has been developed for dense graphs (number of edges comparable with the square of number of vertices) but parallel theories for sparse graphs are beginning to emerge [3]. 1.2. Graph limits and graphons. The limit of a sequence of dense graphs can be deﬁned as follow”
Concentration of the adjacency matrix and of the Laplacian in random graphs with independent edges (2009, background): “Other papers [13, 14] have focused on the relationship between convergence of subgraph counts vs. convergence in the cut metric (see below) for sparse graphs, a topic that is far from completely elucidated.”
An introduction to large deviations for random graphs (2016, methodology): “graph theoretic tools used for the analysis of large deviations for random graphs are useful only in the dense setting. In spite of considerable progress in developing a theory of sparse graph limits [6, 11, 12], there is still no result that fully captures the power of Szemer´edi’s lemma in the spa”
Graphons, cut norm and distance, couplings and rearrangements (2010, unknown): “C O ] 3 J un 2”