Clique number of random geometric graphs in high dimension

Posted on January 19, 2013 by Sebastien Bubeck

I would like to discuss now another class of random graphs, called random geometric graphs. In general a random geometric graph arises by taking {n} i.i.d. random variables in some metric space, and then putting an edge between two of these random variables if the distance between them is smaller than some pre-specified quantity. In this post I’d like to focus on a specific class of random geometric graph defined as follows. Let {X_1, \hdots, X_n} be i.i.d. random variables uniformly distributed on the Euclidean sphere {\mathbb{S}^{d-1} = \{x \in {\mathbb R}^d: \|x\| =1\}}. We define {G_{n,d} = ([n], E_{n,d})} by

\displaystyle (i,j) \in E_{n,d} \; \text{if} \; i \neq j, \; \text{and} \; X_i^{\top} X_j > 0 .

Similarly to the Erdös-Rényi model, one has {\mathop{\mathbb P}((i,j) \in E_{n,d}) = 1/2}, but now these events are not mutually independent anymore! Indeed, knowing that {i} is connected to both {j} and {k} gives some information on whether {j} and {k} are connected. This lack of independence between edges changes dramatically the behavior of the graph. An interesting consequence of this is that random geometric graphs might be much better models for real-world networks than the classical Erdös-Rényi random graph. Thus, quite naturally, random geometric graphs have also been extensively studied, see for example this book. However, most of the literature focuses on the case where {d} is fixed and {n} tends to infinity. In this post I would like to discuss some high-dimensional effect that happens when both {d} and {n} grow together to infinity. I’ll focus the discussion on the clique number {\omega(G_{n,d})}.

Let us first consider the standard case where {d} is fixed and {n} tends to infinity. Then one would expect to have roughly of order of {n/2^d} points in the positive orthant {{\mathbb R}^d_+ \cap \mathbb{S}^{d-1}} (recall that there are {2^d} orthants in {{\mathbb R}^d}). In particular, since all points in the positive orthant have a positive scalar product with each other, these points will all be connected and thus one would expect {\omega(G_{n,d}) = \Omega(n/2^d)}. This argument can easily be made formal, and one can show that for {d= o(\log n)}, one has {\mathop{\mathbb E} \omega(G_{n,d}) = \Omega(n^{1-\epsilon})}, {\forall \epsilon > 0}. Thus in small dimension ({d=o(\log n)}) random geometric graphs behaves very differently than Erdös-Rényi random graphs, as in the former case one has cliques of size almost linear, while for the latter case they are of logarithmic size (see previous post).

Let us now consider the other extreme, where {n} is fixed and {d} tends to infinity. Then, intuitively, it is clear that the coordinates that will ‘decide’ if two vertices are connected will be almost surely different for each pair of vertices, which means that the geometry of the problem is lost and that we are back to the Erdös-Rényi model. This argument can easily be made formal by resorting to the multidimensional Central Limit Theorem, and one can show that the total variation between {G_n} and {G_{n,d}} tends to {0} as {d} tends to infinity. In particular the clique number {\omega(G_{n,d})} is of logarithmic size when {n} is large, and {d} is much larger than {n}. In fact, by doing a much more subtle analysis, one can show that this last statement is true for much smaller values of {d}. More precisely, one can show that if {d = \Omega(\log^3 n)} then {\omega(G_{n,d})} is almost surely equivalent to {2 \log_2(n)}. In fact the clique number of a random geometric graph is already small at {d = \Omega(\log^2 n)} where one can prove that almost surely {\omega(G_{n,d}) = O(\log^3 n)}. All of these results can be found in the very nice paper by Devroye, György, Lugosi, and Udina: High-dimensional random geometric graphs and their clique number. A natural question left open by this work is where exactly the transition between polynomial size cliques and logarithmic cliques happen. The above results show that it has to be after {d=o(\log(n))} and before {d=\Omega(\log^2(n))}. The following theorem gives the answer:

Theorem 1 (Arias-Castro, Bubeck and Lugosi 2012) There exists some numerical constant {c>0} such that with probability at least {1/2},

\displaystyle \omega(G_{n,d}) \geq c \exp\left(c \frac{\log^2(n)}{d} \right) .

Surprisingly, this result shows a phase transition at {d \sim \log^2(n)}. Indeed for {d=o(\log^2(n))} the above inequality implies that the clique number is larger than any poly-logarithmic term, that is {\text{Median}(\omega(G_{n,d})) = \Omega(\log^a(n)), \forall a >0}. On the other hand Devroye et al. proved that at {d \geq 9 \log^2(n)} one already has almost surely {\omega(G_{n,d}) = O(\log^3 n)}. Thus the clique number of the random geometric graph {G_{n,d}} becomes logarithmic brutally at {d \sim \log^2(n)}. In the next blog post I will discuss our proof of the above theorem.

This entry was posted in Random graphs. Bookmark the permalink.

Leave a reply