Lorentz Center - New Frontiers in Random Geometric Graphs from 14 Apr 2014 through 17 Apr 2014
  Current Workshop  |   Overview   Back  |   Home   |   Search   |     

    New Frontiers in Random Geometric Graphs
    from 14 Apr 2014 through 17 Apr 2014



Speaker: David Aldous (Berkeley).
Title: Random Spatial Networks
Abstract: The talk will give an overview of my interests in this topic, emphasizing:

(i) There are models for connected networks other than the familiar ``geometric random graph" model and its variants.

(ii) Believing one can describe complex real-world networks by highly specific models with only few parameters seems unduly optimistic. As an alternative, one could consider some initially unspecified model within a specified large class. (analogy: natural language modeled as some initially unspecified stationary process). For instance, the property that route-lengths are linear should hold very generally.

(iii) There is a (presumably) large class of scale-invariant models with mathematically interesting structure.

Speaker: Michel Bode (Birmingham)
Title: The component structure of random geometric graphs on the hyperbolic plane
Abstract: We study the component structure of random geometric graphs on the hyperbolic plane. Here, \(N\) points are chosen randomly on a disc of radius \(R\) on the hyperbolic plane according to some suitable distribution depending on a variable, \(\alpha\). When \(\alpha=1\), this distribution is the uniform distribution on the given disc. Any two of them are joined by an edge if their hyperbolic distance is at most $R$. This model has been introduced by Krioukov et al. as a model for complex networks that appear often in real world contexts.
We establish thresholds of \(\alpha\) for the connectivity and the emergence of a giant component.

Speaker: Pierre Calka (Rouen)
Title: Asymptotic study of Gaussian polytopes
Abstract: We consider the convex hull of a set of \(n\) i.i.d. points distributed according to the standard normal distribution on the Euclidean space \({\mathbb R}^d\). This polytope, called Gaussian polytope, is one of the central models of the theory of random polytopes which goes back to Sylvester's four-point problem in 1864 and the seminal works due to Rényi and Sulanke in 1963 and 1964. Classical questions concern the distribution and moments of functionals such as the volume or the number of extreme points and more generally the shape of the polytope.

We show that the extreme points are in the vicinity of some deterministic critical sphere and that the boundary process converges in distribution after rescaling to a limit process called parabolic growth process. We deduce from it the explicit calculation of limiting variances for the number of \(k\)-dimensional faces and the volume. We will discuss the a priori unexpected connection between the limit process associated with the Gaussian polytope and the geometric construction of the zero viscosity solution to Burgers' equation with random input.

This is joint work with J. E. Yukich.

Speaker: Elisabetta Candellero (Warwick)
Title: The number of ends of critical branching random walks
Abstract: In this talk we will introduce the concepts of "end" of a graph and "trace" of a branching random walk (BRW).
We will discuss examples showing that, on some one-ended Cayley graphs, the trace of a transient (symmetric) BRW has infinitely many ends almost surely.
(Joint work with Matthew Roberts, University of Bath.)

Speaker: Christopher Daniels (Bath)
Title: Nonpercolation at criticality for the Random Connection Model
Abstract: The Random Connection Model on the plane is a continuum percolation model where points are distributed on \(\mathbb{R}^2\) according to a Poisson point process of rate 1, and then each pair of points has a connection between them formed randomly, with distribution depending on the distance between the points. We look at a simple version of this model with parameters \(p\in[0,1]\) and \(r>0\) where the probability of a connection between the points \(x\) and \(y\) is \(p\) if the distance \( d(x,y) < r \), and otherwise has probability 0. We show that there is some \(p_0<1\) such that for \(p>p_0\), this random connection model does not percolate at the critical value \(r_c(p), p\).

Speaker: Maurits De Graaf (Thales)
Abstract: We present an average case analysis of the minimum spanning tree heuristic for the power assignment problem. The worst-case approximation ratio of this heuristic is 2. We show that when the edge weights are uniform \([0, 1]\)-distributed, the expected approximation ratio is bounded above by \(2−1/2 \zeta(3)\), where \(\zeta(\cdot)\) denotes the Riemann zeta function.


Speaker: Josep Diaz (UPC Barcelona)
Title: Some open problems and recent results on RGG and UDG
Abstract: We present a recent result proving that the min bisection problem is NP-hard for Unit Discs Graphs.
We also introduce a new type of RGG, the Gaussian RGG, with some results and open problems.

Speaker: Victor Falgas-Ravry (Umeå)
Title: Small components in \(k\)-nearest neighbour random geometric graphs
Abstract: The \(k\)-nearest neighbour random geometric graph model \(S_{n,k}\) is obtained by scattering vertices inside a square of area n according to a Poisson point process of intensity 1, and placing an (undirected) edge between each vertex and the \(k=k(n)\) points of the process closest to it. In this talk I will present some recent results about the distribution of small components in \(S_{n,k}\) for \(k\) below the connectivity threshold.

Speaker: Nikolaos Fountoulakis (Birmingham)
Title: Random graphs on the hyperbolic plane: degree distribution, clustering and component structure
Abstract: Random geometric graphs have been studied over the last 50 years in great detail. These are graphs that are formed between points randomly allocated on a Euclidean space and any two of them are joined if they are close enough. However, all this theory has been developed when the underlying space is equipped with the Euclidean metric. But, what if the underlying space is curved? Our focus will be on the case where the underlying space is a hyperbolic space. We will give an overview of this theory and, in particular, we will discuss the typical degree distribution of these random graphs as well as the existence of global clustering. Furthermore, we will discuss briefly critical conditions on the parameters of the model that determine the existence of a giant component as well as the connectivity of the random graph.

This is joint work with E. Candellero, M. Bode and T. Müller.

Speaker: Nicolas Fraiman (UPenn)
Title: Bounding the diameter of the random connection model on the torus
Abstract: We study the diameter of a family of random graphs on the torus. In the random connection model two points \(x\) and \(y\) are connected with probability \(g(y-x)\) where \(g\) is a given function. We prove that the diameter of the graph is bounded by a constant, that only depends on the \(L^1\) norm of \(g\), with high probability as the number of vertices in the graph tends to infinity.
(This is joint work with Luc Devroye.)

Speaker: Jean-Baptiste Gouéré (Orleans)
Title: Continuum percolation and distribution of the radii of the balls.
Abstract: We consider the Boolean model on \(R^d\). This is the union of i.i.d. random Euclidean balls centered at points of an homogeneous Poisson point process on \(R^d\). The intensity of the Poisson point process is chosen so that the Boolean model is critical for percolation. We are interested in the volumetric proportion of \(R^d\) which is covered by this critical Boolean model. This critical volumetric proportion is a function of the dimension d and of the common distribution of the radii.

Speaker: Matan Harel (NYU)
Title: The Localization Phase Transition in Random Geometric Graphs with Too Many Edges
Abstract: Consider the Gilbert random geometric graph \(G(n, r(n))\), given by a connecting two points of a Poisson Point Process of intensity \(n\) on the unit torus whenever their distance is smaller than the parameter \(r(n)\). This model is conditioned on the rare event that the number of edges observed, \(|E|\), is greater than \([1 + \delta(n)]\) times its expectation. We show that, when \(\delta\) is fixed or vanishing sufficiently slowly in \(n\), there exists a "giant clique" with almost all the excess edges forced into the model by conditioning event. If \(\delta\) vanishes sufficiently quickly, the largest clique will be, at most, a constant multiple of the usual clique number. Finally, we discuss progress in finding a phase transition function \(\delta_0(n)\), so that when \(\delta\) is much bigger than \(\delta_0\), the giant clique scenario holds, while \(\delta\) much smaller than \(\delta_0\) implies no giant clique.

Speaker: Christian Hirsch (Ulm)
Title: On percolation and asymptotic properties of random geometric graphs approximating minimal spanning forests
Abstract: We consider properties of so-called creek-crossing and minimal-separator graphs, which can be seen as families of geometric graphs converging to the minimal spanning forest (MSF) on a stationary point process from above and from below, respectively.

First, we investigate percolation in these graphs, allowing us to recover as special cases known results for the relative-neighborhood and nearest-neighbor graph.

This talk is based on joint work with T. Brereton, D. Kroese and V. Schmidt.

Speaker: Jonathan Jordan (Sheffield)
Title: Geometric preferential attachment graphs in general compact metric spaces
Abstract: We investigate the degree sequences of geometric preferential attachment graphs in general compact metric spaces. We show that, under certain conditions on the attractiveness function, the behaviour of the degree sequence is similar to that of the preferential attachment with multiplicative fitness models investigated by Borgs et al. When the metric space is finite, the degree distribution at each point of the space converges to a degree distribution which is an asymptotic power law whose index depends on the chosen point. For infinite metric spaces, we can show that for vertices in a Borel subset of \(S\) of positive measure the degree distribution converges to a distribution whose tail is close to that of a power law whose index again depends on the set.

Speaker: Marc Lelarge (INRIA)
Title: Community detection for the edge-labeled stochastic block model
Abstract: The labeled stochastic block model is a random graph model representing networks with community structure and interactions of multiple types. In its simplest form, it consists of two communities of approximately equal size, and the edges are drawn and labeled at random with probability depending on whether their two endpoints belong to the same community or not. It has been conjectured that this model exhibits a phase transition: reconstruction (i.e. identification of a partition positively correlated with the true partition into the underlying communities) would be feasible if and only if a model parameter exceeds a threshold. We prove this conjecture for ’not too sparse’ graphs.
(joint work with C. Bordenave, L. Massoulie and Jiaming Xu)

Speaker: Bodo Manthey (Twente)
Title: Probabilistic Analysis of Power Assignments
Abstract: A fundamental problem for wireless ad hoc networks is the assignment of suitable transmission powers to the wireless devices such that the resulting communication graph is connected and the total transmit power is minimized. Our goal is a probabilistic analysis of this power assignment (PA) problem.

We prove complete convergence of PA for arbitrary combinations of the dimension \(d\) and the distance-power gradient \(p\). In particular, we prove complete convergence for the case \(p>d\) for PA and also for the minimum spanning tree problem. As far as we are aware, complete convergence for \(p>d\) has not been proved yet for any Euclidean functional.

As an application, we prove that the expected approximation ratio of a simple spanning tree heuristic is strictly less than its worst-case ratio of 2.

(Joint work with Maurits de Graaf.)

Speaker: Ronald Meester (VU Amsterdam)
Title: connectivity in fractal percolation - recent developments
Abstract: In the process of fractal percolation, a random fractal subset of the unit cube is generated as a pointwise limit of decreasing compact sets. We say that percolation occurs of this random fractal set contains connected components larger than one point. Another definition involves the existence of continuous curves. In two dimensions, we explain how the machinery of Aizenmann and Burchard, dealing with converge in distribution of collections of random curves, can be used to draw conclusions about the pointwise limit in fractal percolation. This involves a rather subtle interplay between various types of convergence in different topologies. If time permits we also discuss the situation when the limit set has positive Lebesgue measure.

Speaker: Dieter Mitsche (Nice)
Title: On the relation between graph distance and Euclidean distance in random geometric graphs
Abstract: Given a connected random geometric graph and the Euclidean distance between any pair of vertices \(d_E(u,v)\), we give almost sharp bounds on the graph distance \(d_G(u,v)\) as a function of \(d_E(u,v)\).

Joint work with J. Diaz, X. Pérez-Giménez and G. Perarnau.

Speaker: David Neuhäuser (Ulm)
Title: Bivariate functionals of shortest-path trees in random geometric graphs and their application to telecommunication networks
Abstract: Shortest-path trees constructed on the basis of random geometric graphs play an important role in the field of optimising fixed-access telecommunication networks with respect to costs and capacities, see [1,2]. Distributional properties of the corresponding two half-trees Gh1 and Gh2, originating from the root of such a tree G, are of special interest for engineers. In this talk, we present parametric approximation formulas for the marginal density functions of the skeletal backbone of the tree as well as the total lengths of both half-trees. Note that naturally, these functionals of Gh1 and Gh2 are not independent random variables. Therefore, parametric copulas (see [3,4]) are provided in order to combine the marginal distributions of these functionals to a bivariate joint distribution.

[1] Neuhäuser D., Hirsch C., Gloaguen C. and Schmidt V. (2013). A parametric copula approach for modelling shortest-path trees in telecommunication networks. In: A. Dudin and K. Turck (eds.) An- alytical and Stochastic Modeling Techniques and Applications. Lecture Notes in Computer Science 7984, Springer, 324–336.
[2] Neuhäuser D., Hirsch C., Gloaguen C. and Schmidt V. Joint distributions for total lengths of shortest-path trees in telecommunication networks. Preprint (submitted).
[3] Mai J.-F. and Scherer M (2012). Simulating Copulas: Stochastic Models, Sampling Algorithms, and Applications. Imperial College Press, London.
[4] Nelsen R. B. (2006). An Introduction to Copulas. Springer, New York.

Speaker: Mathew Penrose (Bath)
Title: Connectivity of soft random geometric graphs
Abstract: For certain random graph models, it is known that the main obstacle to connectivity is the existence of isolated vertices; the probability that the graph is disconnected but free of isolated vertices is vanishingly small when the number of vertices \(n\) becomes large. This is known to hold for the classical Erdős-Rényi random graph \(G(n,p)\) (with \(p\) possibly varying with \(n\)), and also for random geometric graphs \(G(V_n,r)\) (\(V_n\) a set of \(n\) uniform random points in the unit square, and \(r\) a distance parameter, possibly varying with \(n\)).
We discuss the extension of this fact to a more general class of random graph model, in which each pair of points \(x,y\) of \(V_n\) is connected with probability \(f(|y-x|)\) for some specified connection function \(f\) (again, possibly varying with \(n\)). This includes both of the random graph models mentioned above as special cases, and may be of interest in modelling wireless communications networks.

Speaker: Will Perkins (GeorgiaTech)
Title: Sharp Thresholds in Random Geometric Graphs
Abstract: In 2004, Goel, Rai, and Krishnamachari proved that all monotone properties of random geometric graphs exhibit a sharp threshold as the radius varies, as long as the critical radius for the property is sufficiently above the connectivity threshold. I will discuss characterizations of properties with sharp thresholds in all regimes, including sparse RGG's and RGG's in which the dimension tends to infinity with \(n\). I will give two criteria for sharp thresholds, one of which applies to "vertex monotone" properties and is straightforward to check, and the other of which applies to edge monotone properties and leads to a natural conjecture.

Speaker: Pawel Pralat (Ryerson)
Title: Chasing robbers on random geometric graphs
Abstract: We study the vertex pursuit game of Cops and Robbers, in which cops try to capture a robber on the vertices of the graph. The minimum number of cops required to win on a given graph \(G\) is called the cop number of \(G\). We focus on \(G_{d}(n,r,p)\), a random subgraph of the random geometric graph in which \(n\) vertices are chosen uniformly at random and independently from \([0,1]^d\), and two vertices are adjacent with probability \(p\) if the Euclidean distance between them is at most \(r\); \(T_{d}(n,r,p)\) is defined similarly with the only difference that the torus metric is used instead. We present asymptotic results for the game of Cops and Robber played on \(G_{d}(n,r,1)\) and \(T_{d}(n,r,p)\) for a wide range of \(p=p(n)\) and \(r=r(n)\).
(Joint work with Noga Alon.)

Speaker: Arnaud Rousselle (Rouen)
Title: Random walks on random graphs generated by point processes in \(\mathbb{R}^d\)
Abstract: In this talk, we consider random walks among conductances on graphs depending on the geometry of an infinite locally finite random set of points. More precisely, given a realisation of a simple point process in \(\mathbb{R}^d\), an (infinite locally finite) connected graph \(G=(V,E)\) is constructed and equipped with a conductance $C$, that is a positive symmetric function on its edge set. The random walk on \(G\) associated with \(C\) is the (time homogeneous) Markov chain \((X_n)_{n\geq 0}\) with transition probabilities given by: \[\mathbb{P}\big[X_{n+1}=v\big| X_n=u\big]=\frac{C(u,v)}{w(u)},\] where \(w(u):=\sum_{v\sim u}C(u,v)\). We present two general criteria for recurrence or almost sure transience of such walks. The proofs of these results rely on a well-known analogy between random walks and electrical networks, and on a comparison with random walk on percolation clusters in \(\mathbb{Z}^d\). Under suitable assumptions on the point process \(\xi\) and the conductance \(C\), we prove that random walks on the Delaunay triangulation, the Gabriel graph or the skeleton of the Voronoi tiling of \(\xi\) are recurrent if \(d=2\) and transient if \(d\geq 3\). Moreover, we state an annealed (or averaged) invariance principle (convergence to a Brownian motion) for continuous-time random walks starting from the origin on Delaunay triangulations and Gabriel graph generated by Palm versions of suitable point processes.

Speaker: Amites Sarkar (Western Washington U)
Title: Coverage and Percolation in the Secrecy Model
Abstract: Working in the infinite plane, consider a Poisson process of black points with intensity 1, and an independent Poisson process of red points with intensity \(\lambda\). We grow a disc around each black point until it hits the nearest red point, resulting in a random configuration \(A_{\lambda}\), which is the union of discs centered at the black points. Next, consider a fixed disc of area $n$ in the plane. What is the probability \(p_{\lambda}(n)\) that this disc is completely covered by \(A_{\lambda}\)? I'll present the best known bounds for this problem, and also briefly discuss a related percolation question, which was motivated by the issue of security in wireless networks.

Speaker: Perla Sousi (Cambridge)
Title: The detection problem in a mobile geometric graph
Abstract: We consider the following dynamic Boolean model introduced by van den Berg, Meester and White (1997). At time 0, let the nodes of the graph be a Poisson point process in \(R^d\) with constant intensity and let each node move independently according to Brownian motion. At any time \(t\), we put an edge between every pair of nodes if their distance is at most \(r\). We study the question of detection, which is the first time until a target point -- fixed or moving -- is within distance \(r\) from some node of the graph. What is then the best strategy for the target to stay undetected for a long time? Using the connection to the Wiener sausage and rearrangement inequalities we will answer this question.
(based on joint works with Yuval Peres, Alistair Sinclair and Alexandre Stauffer)

Speaker: Alexandre Stauffer (Bath)
Title: Mobile Geometric Graphs
Abstract: In this talk we consider what we call the mobile geometric graph model, which is a natural extension of random geometric graphs with nodes moving in time according to independent Brownian motions. We will given an overview of the percolation properties of this model.
Based on joint works with Yuval Peres, Vladas Sidoravicius, Alistair Sinclair and Perla Sousi.

Speaker: Mike Steele (UPenn)
Title: Open Problems Concerning Classical Euclidean Functionals
Abstract: I will go over my list of favorite open problems. All the problems are easy to state, but perhaps not so easy to solve. Enough partial results will be proved to show what has been tried --- and what has not worked (yet!). Specifices include: Problems on the degree sequences for MSTs, problems on the variance of the TSP for a random sample, problems related to "two parameter" functionals (to be defined in the talk), and the problem of a Beardwood, Halton, Hammersly theorem for dependent sequences. A construction will be sketched that proves that ergodicity is not enough --- and strong mixing may not help.

Speaker: Kaspar Stucki (Göttingen)
Title: Continuum percolation for Gibbs processes
Abstract: In this talk we consider percolation properties of a Boolean model, where the grains are (non-random) balls and their centers form a Gibbs point process. It is well-known that if the Gibbs process is Poisson, then there exists a percolation phase transition. That is for intensities below a critical threshold the Boolean model a.s. does not contain an infinite cluster, and above this threshold there is a.s. an infinite cluster.

Speaker: Christoph Temmel (VU Amsterdam)
Title: Avoidance probabilities of one-independent point processes
Abstract: A point process is one-independent, if subprocesses at distances larger than one are independent of each other. We show that for low intensities, every simple one-independent point process has positive avoidance probabilities. For a fixed low intensity, the extreme case with uniformly minimal avoidance probabilities is unique and has interesting properties. We conclude with remarks on connections to the problem of stochastically dominating a one-independent point process by a Poisson point process.

Speaker: Johan Tykesson (Gothenburg)
Title: The Poisson cylinder model
Abstract: We consider a Poisson point process on the space of lines in \(R^d\), where a multiplicative factor \(u>0\) of the intensity measure determines the density of lines. Each line in the process is taken as the axis of a bi-infinite solid cylinder of radius 1. We show that there is a phase transition in the parameter u regarding the existence of infinite connected components in the complement of the union of the cylinders. We also show that given any two cylinders \(c_1\) and \(c_2\) in the process, one can find a sequence of \(d-2\) other cylinders which creates a connection between \(c_1\) and \(c_2\).

Talk is based on joint works with Erik Broman and David Windisch

Speaker: Rob Van den berg (CWI)
Title: Sharpness of the percolation transition for a class of contact processes
Abstract: It is well-known that the `classical' percolation models have a sharp phase transition: Below the critical value, the cluster size distribution has exponential decay. In recent years these results have been extended to some percolation models with spatial dependencies. Motivated by studies of vegetation patterns and desertification in the life-sciences literature, we have tried to stretch the above mentioned results further. In particular, we investigated the question whether the (quite complicated) percolation models used in that literature could have a substantially different behaviour (namely, with `robust' criticality instead of sharp transition) from the classical ones. After a general introduction and explaing these notions and models, I will state recent results which were obtained in cooperation with Jakob Bjornberg and Markus Heydenreich.

Speaker: Andrew Wade (Durham)
Title: Phase transitions for random geometric preferential attachment graphs
Abstract: Vertices arrive one at a time at random locations in the unit cube and are joined to existing vertices at random according to a rule that combines preference according to current degree with preference according to spatial proximity. We investigate phase transitions in the structure of the resulting graph as the relative weighting of these two components of the attachment rule is varied.

This is joint work with Jonathan Jordan (Sheffield).

Speaker: Joseph Yukich (Lehigh)
Title: Surface Order Scaling in Stochastic Geometry
Abstract: Limit theory for functionals in stochastic geometry having input given by an i.i.d. sample often involves scaling by the sample size. However in many situations this scaling is not natural. We give general results showing when it is more natural to scale by the surface area of an appropriately chosen re-scaled manifold of lower dimension. Using general results we deduce variance asymptotics and central limit theorems for statistics arising in stochastic geometry, including score functions of the Poisson - Voronoi tessellation, answering some open problems.