Recognizing graphs formed by spatial random processes

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

• Jeanette Janssen (Dalhousie University)
• Monday 12 December 2016, 16:00-16:45
• Seminar Room 1, Newton Institute.

If you have a question about this talk, please contact INI IT.

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.

This talk is included in these lists:

• All CMS events
• Cambridge Centre for Data-Driven Discovery (C2D3)
• Cambridge talks
• Chris Davis' list
• Featured lists
• INI info aggregator
• Interested Talks
• Isaac Newton Institute Seminar Series
• School of Physical Sciences
• Seminar Room 1, Newton Institute
• Trust & Technology Initiative - interesting events
• bld31
• ndk22's list
• ob366-ai4er
• rp587

Note that ex-directory lists are not shown.