Metrics for sparse graphs
Metrics for sparse graphs
复制标题
稀疏图的指标
DOI：
10.1017/cbo9781107325975.009
复制
发表时间：
2007
期刊：
影响因子：
--
通讯作者：
O. Riordan
中科院分区：
文献类型：
--
作者：
B. Bollobás;O. Riordan
最近，Bollob、Janson和Riordan引入了一类非常普遍的随机图模型，产生了具有$Theta(N)$边的非齐次随机图。粗略地说，每个{\em核}都有一个模型，即每个对称可测函数从$[0，1]^2$到非负实数，尽管细节要复杂得多。在Borgs，Chayes，Lov‘asz，S，Szegdy和Vesztergombi的最新工作中，核和随机图之间出现了一种不同的联系。他们在稠密图(具有$n$顶点和$\theta(n^2)$边的图)上引入了几个自然度量，证明了这些度量是等价的，并用本质上是有界核的{em图}刻画了所有图关于这些度量的空间的完备性。这项工作最吸引人的方面之一是，非齐次拟随机图序列在某种意义上是完全一般的：任何稠密图序列都包含这样的子序列。
我们的目的是简要地回顾这些结果，然后研究它们在多大程度上可以推广到具有$o(n^2)$边的图。尽管许多定义都以一种简单的方式扩展，但各种指标之间以及指标和随机图模型之间的连接结果比密集情况下要复杂得多。我们将证明许多部分结果，并提出更多的猜想和公开问题，它们的解决将极大地加强目前相当不满意的稀疏图上的度量理论。本文主要讨论具有$o(n^2)$但具有$omega(N)$边的图：一篇配套论文[arxiv：0812.2656]将讨论具有O(N)条边的图的(更有问题的)情况。
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.