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 Citations and Data
Attribution-NonCommercial-NoDerivatives 4.0 International