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.

• #science_technology
• #microsoft_research