Demand-Aware Small-World Networks on Clustered Demands

We start by considering clusters as supernodes and say that the routing starts in cluster $I_u$ and terminates in cluster $I_v$. Let $J$ denote the set of clusters in the $|J|$-neighborhood of $I_v$. Assume further that source cluster $I_u$ is exactly $|J|$ cluster hops away from cluster $I_v$. We first show that it takes $O(p\cdot \log (x)+q\cdot \log (y))$ rounds in expectation for the greedy routing from $I_u$ to $I_v$ to end up in $J/2$, i.e. inside the $|J|/2$-neighborhood of $I_v$.

There are at least $|J|$ clusters that any node in $I_u$ can connect to in $J/2$. The probability for a node $u$ to have a direct link to a cluster in $J/2$ is at least

where $I_w$ is the farthest cluster at distance $3|J|/2$. That is,

Here, we lower bounded the probability assuming that the largest cluster hop distance is $3|J|$. Recall that this is possible since any node that draws its long-range edge to another cluster considers the cluster as a supernode. This view helps us to deal with the fact that we may iterate over nodes from the same cluster for many steps.

Let $X_i$ be a random variable denoting the number of rounds for the greedy routing to reach a cluster in $J/2$. The probability that a node $u$ does not reach a node in $J/2$ within $r$ rounds is

Here we used the fact that all clusters have the same size and thus every node uses the same probability distribution for its long-range edges. Next, we bound the expected value of $X_i$, i.e. the expected time (number of steps) to half the distance to the destination cluster:

This results in $E[X_i]=3(p\cdot \log (x)+q\cdot \log (y)+c^{\prime }).$

Let $X$ denote the number of rounds to reach the destination cluster. Since we half the cluster distance until we end up in the destination cluster, we have $X=X_1+X_2+\mathrm{\dots }+X_{\log y}$. Then,

$◀$

Similarly, we can derive the number of rounds that a node needs to route inside the cluster.

We omit the proof of this lemma as it is analogous to the analysis in [13], with the exception that the normalization factor from Lemma 1 is applied. By summing up the expected number of steps from Lemma 1 and 2.

Observe that this bound corresponds to the upper bound of [13] when the matrix is dense, like for example in the stochastic block model [1] where all nodes belong to some cluster. In that case $\log (x)+\log (y)=\log (xy)=\log (n)$. When the demand matrix is sparse, i.e., $xy\ll n$, the average distances become much smaller than in the demand-oblivious model.

In the following, we use Stirling’s approximation $k!\approx \sqrt{2\pi k}{\left(\frac{k}{e}\right)}^k$ to approximate the factorial. We set $\lambda =c^{\prime }\log n$, where $c^{\prime }>c$.

For Equations (3.2) and (3.2), we assume that $c^{\prime }\gg C^2$.

Note that the number of clusters is upper bounded by $n$ by definition. Using union bound, we can show:

Analogously, we can prove the other side:

This concludes the proof of the lemma. $◀$

Note that for the last inequality, we assume that $C>4$. As in the proof of Lemma 5, we can use the union bound together with the fact that there can be at most $n$ clusters to prove the Lemma statement:

$◀$

Next, we reformulate the numerator ${\lambda }^{C\log n}=2^{c^{\prime }\log n}$ for some constant $c^{\prime }=C\log \lambda$ and receive

For the denominator, we can write

for $c^{\prime \prime }=C^{\frac{\log n}{\log \log n}\cdot {\log }_n{C}^{\frac{\log n}{\log \log n}}}$. Thus,

for a sufficiently large value of $n$.

As before, we apply the union bound together with the fact that there can be at most $n$ clusters to show the theorem statement:

$◀$

Using the above bounds, we can now prove Theorem 4:

As in the proof of Lemma 1, we consider the clusters as supernodes and let $J$ denote the $|J|$-neighborhood of the destination cluster $I_v$. We first show that it takes $O(p\cdot \log (\lambda )+q\cdot \log (y))$ steps in expectation for the greedy routing starting in $u$ to reach a node in $J/2$, i.e. inside the $|J|/2$-neighborhood of $I_v$.

Node $u$ can connect to at least $|J|$ clusters in $J/2$. The probability for $u$ from cluster $I_u$ to have a direct link to a cluster in $J/2$ is at least

where $I_w$ is the farthest cluster at distance $3|J|/2$. That is,

Let $Y_i$ be a random variable denoting the number of steps for a node $u$ to reach a cluster in $J/2$. Note that $Y_i$ depends on the cluster size of the nodes that are visited on the path from $u$ to $v$. To upper bound the expected number of steps, we do a case distinction depending on the size of $\lambda$:

We can bound the term in Equation (1) w.r.t. the average cluster size using Jensen’s inequality for concave functions:

Here, the clusters $I_k$ represent the clusters of the nodes visited within $r$ steps. In the following, we will focus on bounding the average $\frac{1}{r}{\sum }_{k\in [r]}|I_k|$. In the case $\lambda >c\log n$, the cluster sizes are concentrated in $[\lambda -C_1\sqrt{\lambda \log n},\lambda +C_1\sqrt{\lambda \log n}]$ (see Lemma 5). Due to $r\le n$ and the union bound, the probability that this sum contains a cluster outside of the interval is less than $1/n^2$. Thus, with probability st least $1-1/n^2$ we have

and also $\mathrm{Pr}[Y_i>r]\le {\left(1-{\displaystyle \frac{1}{3(p\cdot \log (\lambda +C_1\sqrt{\lambda \log n})+q\cdot \log (y)+c^{\prime })}}\right)}^r.$

From here on, we can now apply

This is because, among all $n$ clusters, w.h.p., there will be no cluster outside of the concentration bounds.

Let the random variable $Y=Y_1+Y_2+\mathrm{\dots }+Y_{\log y}$ denote the number of rounds to reach the destination cluster. Then,

We will derive the upper bound on the expected number of rounds analogously to the previous case. The average cluster size of the visited clusters is upper bounded by

with probability $1/n^2$. By plugging in this value into Equation (3.2), we get

For the expected number of rounds holds

In this case, the average cluster size of the visited clusters is upper bounded by

with probability $1/n^2$. Plugging in this value into Equation (3.2) results in

And finally, the expected value is

with high probability.

$◀$

The expected number of steps when routing within a cluster can be computed for each cluster separately, i.e., the expected number of steps within a cluster of size $x$ is $O\left(\log (x)\cdot (p\cdot \log (x)+q\cdot \log (y))\right)$. Since the expected cluster size under the Poisson distribution is $\lambda$, we have

In total, the expected number of steps for greedy routing is

Let $X$ denote the size of a cluster. We can calculate the probability that this cluster exceeds a certain size $s$ as

Note that this bound is not sufficient to upper bound the number of large clusters.

We therefore divide the $n$ possible cluster sizes into intervals $[2^{i}C,2^{i+1}C]$, where $C$ is a large constant. The probability that the size of a cluster $I$ lies in the interval $[2^{i}C,2^{i+1}C]$ can be upper bounded by

Let $r$ denote the number of clusters traversed by the greedy routing. We can assume that these $r$ clusters are chosen uniformly at random with the probabilities chosen as in Equation (3). The average number of clusters in an interval $[2^{i}C,2^{i+1}C]$ is upper bounded by $\frac{r}{{(2^{i}C)}^{\alpha -1}}$.

Assume first that $r>c^{\prime }{\log }^{2}n$. In this case, we can apply the Chernoff bound to show that the cluster sizes of the intervals containing small clusters, where $c^i\le \log n$, are concentrated around $n/(c^{i+1})$. Let $Z$ be the random variable denoting the number of clusters of size $[2^{i}C,2^{i+1}C]$:

For larger $i$, we can upper bound the number of clusters in an interval by

Finally, we upper bound the number of clusters for any interval in the case where $r\le c^{\prime }{\log }^{2}n$:

In order to calculate the expected number of hops from a start to the destination, we will consider the above cases separately. First observe that in the case $r>c^{\prime }{\log }^{2}n$, where $i$ is large, there are at most $\log n$ intervals with cluster sizes from size $\log n$ up to size $n$, each of which has at most $\log n$ clusters with high probability (probability larger than $(1-\frac{1}{n^4})$).

Recall that the probability that the greedy routing needs more than $r$ hops can be upper bounded as

We will now upper bound $\frac{1}{r}{\sum }_{k\in [r]}|I_k|$ for $r>c^{\prime }{\log }^{2}n$. We therefore split the sum into intervals of size up to $\log n$ and into all larger intervals. Observe that there are at most $\log n-\log \log n$ intervals that each contain less than $\log n$ clusters of size $\log n$ to $n$. It would take less than ${\log }^{3}n$ steps to traverse them in the worst case.

On the other hand, the number of clusters in each small interval is concentrated around $\frac{r}{c^i}$. This can be used to calculate the actual average cluster size.

The average cluster size of the traversed clusters is upper bounded by

with probability $1-\frac{1}{n^3}$, as we can sample up to $r\le n$ clusters in total.

For , we assume that each cluster has a size in the order of $n$, and use the same upper bound as used for clusters of sizes $\log \log n$ to $n$. Note that there are up to such clusters, and therefore the expected number of hops to traverse these clusters is upper bounded by . Then we can calculate the expectation as follows:

In the final step, we again use $Y$ to denote the number of rounds to reach the destination cluster. Since we halve the cluster distance until we end up in the destination cluster, we have $Y=Y_1+Y_2+\mathrm{\dots }+Y_{\log y}$. Then,

$◀$

Note that in the proof of Lemma 10, we accounted for the number of steps needed to traverse large clusters in the analysis. To calculate the expected number of steps for greedy routing, we only need to add the number of steps needed to traverse clusters of size up to $c{\log }^{2}n$. Thus, we have

To prove this statement, we will follow the demand-oblivious analysis on grids by Kleinberg [24]. Let $I_v$ be the destination. We divide the analysis into phases $j$, where a phase is defined as the expected number of steps to half the cluster hop distance to $I_v$. As earlier, we are going to consider clusters as supernodes. We define a ball $B_j(I_v)$ containing all clusters at a cluster distance of at most $2^j$ from $I_v$ in the grid. Note that there are at least ${\sum }_{i=1}^{2^j}i=\frac{(2^j+1)2^j}{2}>2^{2j-1}$ such clusters in $B_j(I_v)$.

The probability that any node in a cluster outside $B_j(I_v)$ has a long-range edge to a cluster in $B_j(I_v)$ is lower bounded by

From here on, the analysis continues as in the case of cycles. Let $X_j$ denote the number of steps to reach $B_j(I_v)$. The expected value of $X_j$ is

Let $X$ denote the number of rounds to reach $I_v$. In every phase, the distance to the destination cluster is halved and thus $X=X_{log(\sqrt{y})}+\mathrm{\dots }+X_2+X_1$. Then

$◀$

The routing within clusters can be computed similarly to Section 3.1, with an adapted normalization factor. By summing up the expected number of steps between and within the clusters, we receive the following result:

Also in this case, clusters of different size following the Poisson or the power law distribution can be considered. The main difference in the analysis between the case of cycles and grids lies in the first step where the long-range edges are added to the graph. Observe that the rest of the analysis as well as the normalization factor chosen by the nodes almost does not change. The same analysis can therefore be performed with Poisson and power law distributed cluster sized also on grids, resulting in similar bounds on the expected number of steps.