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.

Speaker Details

László Lovász is a distinguished mathematician, best known for his work in combinatorics, for which he was awarded the Wolf Prize and the Knuth Prize in 1999, and the Kyoto Prize in 2010. Lovász was a professor at Yale University during the 1990s and was a Principal Researcher at Microsoft Research until 2006. He returned to Eötvös Loránd University, Budapest, where he was the director of the Mathematical Institute (2006–2011).

He served as president of the International Mathematical Union between 2007 and 2010.

Series:
Microsoft Research Talks
Date:
Speakers:
Laszlo Lovasz
Affiliation:
Budapest

    • Portrait of Jeff Running

      Jeff Running

Series: Microsoft Research Talks