1
$\begingroup$

Suppose we want to build a 2d geometric graph, where the domain is a $L$ by $L$ square and the geometric aspect means two vertices are connected by an edge if their distance is smaller than a given threshold $\delta.$ For simplicity we can fix beforehand the number of vertices and the ratio of $\delta/L.$

The question is about whether we can say something about how connected the graph will be if we were to once build it by (a) randomly placing the vertices (so randomized positions) and if alternatively we were to place them in a (b) orderly fashion (lattice structure of positions)? Is one method known for example to be more likely to lead to a connected graph than the other? Connectivity is itself rather vague unless we adopt known ideas for how to quantify how connected a graph is, for instance, one can consider the average degree of the graph as a potential measure of connectivity and then compare the two methods (a and b).

Intuitively, I would guess the random graph case will in general lead to more connected graphs, simply from a sampling point of view, but I have no idea how to consider this from a conceptual and rigorous point of view.

I'm trying to learn how one can start tackling such questions and whether there exists know results about them already.

$\endgroup$
2
$\begingroup$

In a lot of cases, the average degree of the graph is going to be pretty similar for the random geometric graph and the lattice geometric graph. In both cases, the average number of vertices in a region is going to be proportional to the area of that region: the average degree is going to be somewhere around $\pi (\frac{\delta}{L})^2 n$, where $n$ is the number of vertices. For both graphs, we'll need to adjust this slightly due to the boundary of the square, but the contribution from that is negligible.

The random graph will always achieve this average degree in expectation: more precisely, the expected average degree is $\pi (\frac{\delta}{L})^2 (n-1)$, because for each vertex $v$, each of the other $n-1$ vertices has a $\pi (\frac{\delta}{L})^2$ chance of ending up within distance $\delta$ of $v$.

In the case of the lattice graph, let's say that the $L\times L$ square is divided into $n$ small squares of area $\frac{L^2}{n}$, and a vertex is placed at the center of each square. If you draw a circle of radius $\delta$ around one vertex, the number of vertices in that circle is given by the number of squares of area $\frac{L^2}{n}$ inside the circle. Squares overlapping the circle partially are sometimes counted and sometimes not. This, again, is proportional to the area of the circle of radius $\delta$: we get about $\frac{\pi \delta^2}{L^2/n} = \pi(\frac{\delta}{L})^2n$ squares, when $n$ is large. But when $n$ is small, the lattice graph will be very sensitive to the exact value of $n$: the average degree as a function of $n$ will experience "jumps" when $n$ increases and a few more squares on the boundary of the circle get counted. (Notably, when $n$ is too small, the lattice graph might just end up being a bunch of isolated vertices.)

You might want to consider looking at minimum degree for the difference between the two graphs. For the lattice graph, the minimum degree is not too different from the average degree. It's controlled by the degree of a vertex in the corner somewhere, so it's between $\frac14$ and $\frac12$ of the average degree: closer to $\frac14$ for large $n$. For the random graph, the degree distribution is asymptotically Poisson, so the probability that a vertex is isolated is roughly $e^{-\pi (\frac{\delta}{L})^2 n}$.

When the average degree is a large constant, the lattice graph is connected, but the random graph still has a linear number of isolated vertices. The average degree needs to go up to around $\log n$ before the random graph stops having isolated vertices, at which point it is also likely to be connected.

$\endgroup$
4
  • $\begingroup$ Dear Misha, many thanks for the discussions. I hope it's okay if I ask a few questions. For our purposes, let us assume large $n$'s. (i): could you please elaborate a bit how you obtain the average degree in the 1st paragraph? Your 3rd and 4th paragraphs are of great interest to me because they really attempts to pinpoint a quantity that would allow one to draw a clear contrast between the consequences of the two embeddings when it comes to connectivity. In particular the 4th paragraph: (ii) so if I understand correctly, in the ordered case (...) $\endgroup$
    – user929304
    Sep 20 '18 at 17:10
  • $\begingroup$ (...), we need less vertices to reach a connected state of the graph? (iii) I had asked a more general version of this question on mathoverflow, where I extend the question to needle-like (finite line segment) vertices as opposed to point-like ones, where then the question of connectivity is: if positions are random, but orientations are (a) random as well, or (b) are correlated/aligned, which case is more likely to lead to higher average degree, or larger connectivity? $\endgroup$
    – user929304
    Sep 20 '18 at 17:14
  • $\begingroup$ In case you find the time and are interested, your input would be very valuable. $\endgroup$
    – user929304
    Sep 20 '18 at 17:15
  • $\begingroup$ (i) I have tried to expand on the average degree argument. (ii) Yes; when we proceed randomly, it is likely that a few vertices are "unlucky" for a long time. I don't immediately see what to say about (iii). $\endgroup$ Sep 20 '18 at 17:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.