Laszlo Lovasz
The similarity distance on graphs and graphons
The similarity distance measures how "similar" two nodes in a dense graph are.
Selecting an epsilon-net with respect to this metric is a useful tool in
algorithms for very large graphs. For example, the Voronoi cells of such a
set form a weak regularity partition.
One can introduce the same distance on graph limits (graphons). This defines
a compact metric space, whose dimension is an important complexity measure of
the graphon and of any graph sequence converging to it. Graphons for which
this dimension is finite have polynomial-size weak regularity partitions. We
will state some sufficient conditions, some proven and some conjectured, for
this dimension to be finite.