Geometric Embeddings of Graphs and Graph Limits
February 15, 2013
University of Saskatchewan
Mathematics and Statistics Department
Friday, February 15, 2013
3:30 pm to 4:30 pm
Title: Geometric Embeddings of Graphs and Graph Limits
Many real-life networks can be modelled by stochastic processes with a spatial embedding. The nodes of such networks are assumed to be embedded in a metric space, and the link probability decreases with distance.
However, for a particular network, it may be hard to determine whether the network has been produced via such a stochastic process, and if so, what the underlying metric space is.
In this talk, I will use the theory of graph limits to show how to recognize graph sequences produced by random graphs with a linear embedding (a natural embedding into the real line). We introduce a graph parameter Gamma^* and show that, graph sequences that have diminishing Gamma^*-values can be seen as the result of a random graph process with a linear embedding.
This is joint work with Huda Chuangpishit, Matt Hurshman, Jeannette Janssen, and Nauzer Kalyaniwalla.