Mathematics Colloquium: Quantifying linearly embedded structure in large graphs

Speaker: Jeannette Janssen (Dalhousie University)

Title: Quantifying linearly embedded structure in large graphs

Microsoft Teams Meeting

Abstract: 

An important question in the study of large networks is to quantify when graphs are structurally similar. The theory of graph limits (Lovasz and Szegedy, 2006) defines a notion of structural similarity of graphs (networks), and a notion of convergence of graphs of increasing size. The limit object is a {\sl graphon}, which can be seen as a ``blueprint" for a random process that produces graphs similar to those in the sequence.

The theory of graph limits has been used in the study of large networks to reveal and measure hidden structure. Our focus is 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. In this talk, I will show how to measure to what extent a given graph exhibits such structure, and how to find a graphon that  provides the blueprint for the structure.

This is joint work with Mahya Ghandehari