Mathematics and Statistics

Colloquium
Finding The Hidden Space Behind Complex Networks:
An Approach Using The New Theory Of Graph Limits

Jeanette Janssen (Dalhousie)

Wednesday, October 9, 2013 at 2:30 pm

Carleton Hall Room 306

Many real-life networks can be modeled by stochastic processes with a spatial embedding. In such processes, the link probability decreases with distance. The spatial embedding can be seen as a representation of the “hidden reality” about the network. Retrieving the spatial information if only the graph is given is a fundamental problem which can be approached in many different ways.

In this talk, I will discuss how this question can be approached using the theory of graph limits. This is a new theory, first proposed by Lovasz and Szefedy and now developed into an active research area. In this theory, convergence of graph sequences can be defined, and a limit object, which itself is not a graph, can be defined.

I will discuss recent work, with co-authors Chuangpishit, Hurshman, Kalyaniwalla, and Ghandehari, which shows how to recognize graph sequences produced by random graphs with a linear embedding (a natural embedding into the reals). We define an operator Gamma which applies to graph limits, which assumes a value zero precisely for graph limits of random graphs with a linear embedding. Moreover we introduce a corresponding graph parameter Gamma-star and show that, for graph sequence which converge to a graph limit under theory, the Gamma-star-values converge to the Gamma-value of the limit. Thus, there is a theoretical basis for considering the value of Gamma-star of a graph as a measure of how closely it conforms to having a linear embedding.

Jeanette Janssen is the Director of AARMS and a Professor from Dalhousie University