skip to content

Recognizing graphs formed by spatial random processes

Presented by: 
Jeanette Janssen Dalhousie University
Monday 12th December 2016 - 16:00 to 16:45
INI Seminar Room 1
In many real life applications, network formation can be modelled using a spatial random graph model: vertices are embedded in a metric space S, and pairs of vertices are more likely to be connected if they are closer together in the space. A general geometric graph model that captures this concept is G(n,w), where w is a  symmetric "link probability" function from SxS to [0,1]. To guarantee the spatial nature of the random graph, we requite that this function has the property that, for fixed x in S, w(x,y) decreases as y is moved further away from x. The function w can be seen as the graph limit of the sequence G(n,w) as n goes to infinity.
 We consider the question: given a large graph or sequence of graphs, how can we determine if they are likely the results of such a general geometric random graph process? Focusing on the one-dimensional (linear) case where S=[0,1], we define a graph parameter \Gamma and use the theory of graph limits to show that this parameter indeed measures the compatibility of the graph with a linear model. 
This is joint work with Huda Chuangpishit, Mahya Ghandehari, Nauzer Kalyaniwalla, and Israel Rocha

The video for this talk should appear here if JavaScript is enabled.
If it doesn't, something may have gone wrong with our embedded player.
We'll get it fixed as soon as possible.
University of Cambridge Research Councils UK
    Clay Mathematics Institute London Mathematical Society NM Rothschild and Sons