Analysis & PDE seminar
Speaker : Jeannette Janssen
Title: Quantifying linearly embedded structure in large graphs
Abstract: An important question in the study of large networks is to quantify when graphs are structurally similar. In a seminal paper published in 2006, Lovasz and Szegedy developed a theory that classifies similarity between graphs in terms of homomorphism densities. In particular, sequences of graphs with converging homomorphism densities converge in the metric space of symmetric measurable functions, or graphons, equipped with a metric derived from the so-called cut norm. Graphs can be mapped to graphons in a straightforward manner, but the limit of a sequence of graphs may not correspond to any graph. Instead, the limit can be seen as a probability distribution, and the structure of the graphs in the sequence is that of `typical' samples from this distribution.
The theory of graph limits, as it has become known, has been used in the study of large networks to recognize hidden structure. With co-authors Chuangpishit, Ghandehari, Hurshman, and Kalyaniwalla, we focused on graphs that have a linearly embedded structure: vertices are embedded in the line, and links are more likely between vertices that are closer together. We introduced a graph parameter, $\Gamma^*$, and a corresponding graphon parameter $\Gamma$, to recognize graphs with such a structure. In particular, for graph sequences converging to a linearly embedded limit, $\Gamma^*$ converges to zero. In follow-up work with Ghandehari, we show the converse: graphs with small $\Gamma^*$-value are close, in cut norm, to a linearly embedded graphon, and converging sequences for which $\Gamma^*$ converges to zero have a linearly embedded limit.
#319 Colloquium Room, Chase Building