Jeannette Janssen (Dalhousie University)

Recognizing graphs formed by a spatial random process

It is a safe assumption about social networks that links are more often formed between people that have a lot in common. This can be modelled with a simple spatial model for link formation. Individuals are represented by vertices placed in a virtual space that represents their interests and characteristics. Links are formed stochastically so that most links are local, i.e. links are less likely between vertices that are further apart.

Given a graph, but no information about the spatial embedding, can we measure whether the graph conforms to a spatial model? Focusing on the case where the space is one-dimensional, we introduce a parameter, $\Gamma$, that provide such a measure. We use the theory of graph limits to show that graphs for which $\Gamma$ is small resemble samples from a spatial model. We also show how, given a sample from a (1D) spatial model, essential spatial information about the vertices can be retrieved from the sample. This is joint work with Mahya Ghandehari and Aaron Smith.