The similarity distance on graphs and graphons

Опубликовано 28 июля 2016, 23:16

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.