The goal of this mini-project is to verify John Kleinberg's theorem on small-world navigability, stated in the article The Small-World Phenomenon: An Algorithmic Perspective.
Consider an $n \times n$ flat grid, where each node has up to $4$ regular neighbors (West, East, North, South). Additionally, each node has a special shortcut picked up at random among the other nodes of the grid. Denoting by $d(a,b) = |a_x - b_x| + |a_y - b_y|$ the Manhattan distance between two nodes $a = (a_x, a_y)$ and $b = (b_x, b_y)$, the probability to choose $b$ as the shortcut of $a$ is proportional to $1 / d(a,b)^r$ for some $r > 0$ which does not depend on $a$ an $b$. The vector from a node to its shortcut is called the shortcut offset.
We are interested in the average routing time. It is defined as the mean number of hops necessary to link up two nodes chosen uniformly and independently at random in a grid where the shortcuts are generated according to the previous distribution. The routing is decentralized in the sense that we always choose the next hope as (one of) the neighbor(s) which is the closest to the destination for the Manhattan distance. In general, the routing time between a source and a destination is not equal to the distance between these nodes in the graph representing the grid. Kleinberg's result states that
This result is often interpreted as follows: shortcuts can turn graphs of large diameter into navigable small-worlds, but this works only if the shortcuts follow a precise distribution.
Your mission: validate this result through simulations. The questions below aim at helping you to identify the difficulties of the problem and to develop solutions. For this assignment, we expect that you send us
The report can be either included into the notebook (recommended) or written in an external pdf file.
You will not be judged on your raw programming skills but on the following criteria:
Even if Python 3.X is recommended, you can use other languages if your choice is justified and the code is extensively commented.
Last remarks and hints:
Random number generation has a much lower time complexity per sample when executed in bulk, especially for custom distributions (using for instance $\sf np.random.choice$). More precisely, if you draw $k$ values in bulk from a random variable which can take $n$ distinct values, the cost is $O(n + k\log(k))$. If you plan to use a given distribution a lot, it is best to draw $k$ values at once (say $k =$ 1,000,000) and to draw them again anytime you stock is depleted.
1. What is the time and the space complexity to draw and memorize all the shortcuts in the grid? Discuss this considering the values indicated above (10,000 runs with $n =$ 10,000).
Answer:
2. What would the time complexity become if we substituted the grid with a torus as a first approximation?
Answer:
The space complexity can be made constant by applying the principle of deferred decisions:
" When there are several random variables [...], it often helps to think of some of them as being set at one point in the algorithm with the rest of them being left random - or deferred - until some further point in the analysis. Formally, this corresponds to conditioning on the revealed values; when some of the random variables are revealed, we must condition on the revealed values of the rest of the analysis." Probability and Computing: Randomized Algorithms and Probabilistic Analysis by Mitzenmacher and Upfal (Cambridge University Press, New York, NY, USA, 2005)
With the decentralized routing algorithm described above, the distance between the current node and the destination strictly decreases at each step. In particular, each node can be visited at most once during the routing, so that we don't need to memorize the shortcut of a node once we have used it. Thus, instead of drawing and memorizing all shortcuts at the beginning, we can thus draw them "on the fly" as we visit the nodes.
In order to keep both the space and the time complexity low, we decide to draw at once a large number $k$ of shortcut offsets which fits into memory. We redraw it any time the shortcut offsets have all been used. The time complexity will be kept low by applying the following method.
We will use a simple version of the rejection sampling method, explained on this Wikipedia page. It consists in drawing shortcut offsets in a grid which is larger than the initial one, and to reject them afterwards if it turns out that the shortcut they produce for the node considered is not in the initial grid. With an appropriate choice of the covering grid, it is possible to draw in a bulk a large number of shortcut offsets (all with the same probability distribution) and to use a rejection criterion adapted to the node considered as we do the routing.
After recalling the longest possible shortcut offset(s) in the $n \times n$ grid and an example of situation where it can arise, give the smallest covering grid we can use to implement this method.
Answer:
Following on from the method proposed in Question 2, we consider a covering grid which is strictly larger than the smallest covering grid but has the advantage of significantly facilitating the drawing of shortcut offsets. Specifically, we want to draw points in a ball with some radius $R$ for the Manhattan distance, so that a node $a = (a_x, a_y)$ with norm $|a| = |a_x| + |a_y| \le R$ is drawn with a probability which is proportional to $1 / |a|^r$.
1. What is the smallest value we can use for $R$?
Answer:
2. Give the number of nodes with norm $i$, for each $i = 1,\ldots,R$.
Answer:
3. Considering some discretised version of the polar coordinates in $\mathbb{R}^2$, explain how you we can efficiently draw points in a ball of radius $R$ for the Manhattan distance, so that a node $a$ is drawn with a probability which is proportional to $1 / |a|^r$.
Answer:
The distribution of the radii is a power law. Even though the function $\sf random$.$\sf choice$ is faster when we draw radii in bulks, it may be interesting to use even more efficient solutions in order to reach higher values of $n$. Below we propose two such solutions.
1. Rejection sampling method: Here we consider only the method of Question 3 with $r > 1$. The distribution of the shortcut radii is proportional to $$ a_i = \frac1{i^{r-1}}, \quad \forall i = 1,\ldots,R. $$ Denote by $f$ the function defined on $[1,R]$ by $$ f(x) = \frac1{x^{r-1}}, \quad \forall x \in (0,R]. $$ For each $i = 2,\ldots,R$, we have $a_i \le f(x)$ for all $x \in [i-1,i]$ with an equality when $x = i$.
Using this observation, explain how you can apply the method of rejection sampling to draw efficiently a large number of radii. You can distinguish the case $i = 1$ since the area under the curve of function $f$ is not finite on $(0,1]$.
A similar approach can be applied when $r \ge 1$.
Hint: You can use the method of inversion sampling to draw a random variable $X$ with probability distribution function defined on $[1,R]$ by $$ x \mapsto \frac{f(x)}{\int_1^R f(t) dt}. $$ This method consists in drawing a random variable $U$ uniformly distribued on $[0,1]$ and computing $$ X = F^{-1}\left( U \times \int_1^R f(t) dt \right), $$ where $F$ is the primitive of $f$ such that $F(1) = 0$. The random variable $X$ has the desired probability distribution function.
More details about this method are provided in "Inverse Transform Method" by Sigman (2010) and "Intro to Sampling Methods, Collins (2010)". The first resource gives rigorous details whereas the second is more graphical.
Answer and code:
2. Alias method: This second approach doesn't use the explicit expression of the radii distribution but it turns out to give much better results than the first one. The following resource "Darts, Dice, and Coins: Sampling from a Discrete Distribution", Schwarz (2011) explains the details of the method and gives an algorithm to implement it.
Answer and code:
1. Using the insights given in the previous questions, write a function $\sf make$_$\sf shortcut$_$\sf offsets$ which computes $k$ shortcut offsets in bulk in a ball with the radius given in Question 3. It is strongly recommended to use the rejection sampling-based method introduced in Exercices 2 and 3. If you decide not to apply it, you will need to find another solution to reduce the time complexity of your simulator. Approximating the grid with a torus, as discussed in Question 1.2, is an option. If you do so, you are expected to compare the results you obtain with the ones you would have expected for the initial grid.
Answer and code:
2. Write a function $\sf kleinberg$_$\sf distance$ which returns the mean number of hops of the decentralized routing algorithm over $runs$ realizations of Kleinberg's grid, for some size $n$ of the grid and exponent $r$ of the shortcut distribution which are fixed. Each run corresponds to an independent realization of Kleinberg's grid. Hence, the shortcut of a node is redrawn independently at each run, which spares you from memorizing the shortcuts once they are used. The departure and arrival nodes are also drawn uniformly and independently at random at each run.
Answer and code: