Abstract

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