Open Collections

Recognizing graphs with linear random structure

Banff International Research Station for Mathematical Innovation and Discovery

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 : S × S → [0, 1] is a symmetric “link probability” function with the property that, for fixed x ∈ S, w(x, y) decreases as y is moved further away from x. he function w can be seen as the graph limit of the sequence G(n, w) as n → ∞. 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 Γ and use the theory of graph limits to show that this parameter indeed measures the compatibility of the graph with a linear model.

Mathematics; Combinatorics; Probability theory and stochastic processes

video/mp4

Author affiliation: Dalhousie University

2017-05-10

Attribution-NonCommercial-NoDerivatives 4.0 International

http://hdl.handle.net/2429/61569

Unreviewed

http://creativecommons.org/licenses/by-nc-nd/4.0/