BIRS Workshop Lecture Videos

Banff International Research Station Logo

BIRS Workshop Lecture Videos

Recognizing graphs with linear random structure Janssen, Jeannette


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.

Item Media

Item Citations and Data


Attribution-NonCommercial-NoDerivatives 4.0 International