Sparse Graphs: Metrics and Random Models

Recently, Bollobas, 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 kappa : [0, 1](2) -> [0, infinity). To understand these models, we should like to know when different kernels kappa give rise to "similar" graphs, and, given a real-world network, how "similar" is it to a typical graph G(n,kappa) derived from a given kernel kappa. The analogous questions for dense graphs, with Theta(n(2)) edges, are answered by recent results of Borgs, Chayes, Lovasz, Sos, 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 article [Bollobas and Riordan, London Math Soc Lecture Note Series 365 (2009), 211-287]; 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. (C) 2010 Wiley Periodicals, Inc. Random Struct. Alg., 39, 1-38, 2011