University of Cambridge > Talks.cam > Isaac Newton Institute Seminar Series > Recognizing graphs formed by spatial random processes

Recognizing graphs formed by spatial random processes

Add to your list(s) Download to your calendar using vCal

If you have a question about this talk, please contact info@newton.ac.uk.

SNAW04 - Dynamic Networks

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

This talk is part of the Isaac Newton Institute Seminar Series series.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.

 

© 2006-2017 Talks.cam, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity