Erratum to “More Benefits of Adding Sparse Random Links to Wireless Networks: Yet Another Case for Hybrid Networks”

1. On the Results in the Original Paper

In the original paper, the author proposed and analyzed sparse models of random wired edge additions upon a wireless network modeled as a random geometric graph $G(n,r)$ and proved exponential improvement to average path lengths, diameter, and mixing time for the resulting hybrid graphs $G_{\mathrm{1}}$ and $G_{\mathrm{2}}$ . Experiments on algebraic connectivity were also performed to confirm the mixing time results, based on established connections between the two measures. We see no mistake in the theorems regarding diameter and average path lengths of the hybrid networks. Similarly, the experimental results do confirm the hypothesis that the hybrid networks are rapidly mixing. However, the proof for the theoretical bounds on the mixing time of hybrid networks contains a subtle error in reasoning, affecting only Section  5.1. That result was stated for a model referred to as $G_1^{\prime }$ that was actually more general than $G_{\mathrm{1}}$ and $G_{\mathrm{2}}$ considered throughout the rest of the paper due to its underlying graph being an arbitrary, connected, almost-regular graph rather than a random geometric graph specifically. The adversely affected statement is Corollary  26 as follows.

Corollary 11.

For $k=\text{polylog}(n)$ , $G_1^{\prime }$ is rapidly mixing with high probability.

As the proofs of the related Theorem  24 and Corollary  25 are based on the flawed analysis for the more general model, Section  5.1 must be revised entirely. In the next section, we present corrected results for the less general but more relevant models $G_{\mathrm{1}}$ and $G_{\mathrm{2}}$ .

2. Revised Theorems

The main results of this section are as follows.

Theorem 21.

For radius $r=\mathrm{\Theta }(r_{\text{con}})$ , the conductance of both $G_{\mathrm{1}}$ and $G_{\mathrm{2}}$ is $\mathrm{\Omega }(\mathrm{1}/k^{\mathrm{2}}{\log \hspace{0.17em}}^{\mathrm{2}}n)$ with high probability.

From this main theorem this corollary follows immediately from Remark $\mathrm{12}$ of the original paper.

Corollary 22.

For $k=\mathrm{\Theta }(\text{polylog}(n))$ and radius $r=\mathrm{\Theta }(r_{\text{con}})$ , $G_{\mathrm{1}}$ and $G_{\mathrm{2}}$ are rapidly mixing with high probability.

Now we prove Theorem 21.

Proof.

First we begin observations that apply to both $G_{\mathrm{1}}$ and $G_{\mathrm{2}}$ and indicate when we must refer specifically to one of the models. From the definition of set conductance, consider the conductance measure $\mathrm{\Phi }$ restricted to a given set $X\subset V$ , which we will refer to as ${\mathrm{\Phi }}_X$ , defined as

$$\begin{array}{cc}& {\mathrm{\Phi }}_X=\frac{\left|\text{Cut}\left(X,V\setminus X\right)\right|}{d\left|X\right|}\end{array}$$

(1)

so that the conductance $\mathrm{\Phi }$ can be naturally defined as follows.

$$\begin{array}{cc}& \mathrm{\Phi }=\underset{X\subset V}{\min \hspace{0.17em}}\hspace{0.17em}{\mathrm{\Phi }}_X.\end{array}$$

(2)

Recall that in this scenario, $d=\mathrm{\Theta }(\log \hspace{0.17em}n)$ .

In what follows, we refer to the wired link stations as red nodes and the only-wireless nodes as blue nodes. Now, consider what any set of points X in the plane and the corresponding conductance of such set represents when the underlying graph is smooth (geo-dense) and geometric: Literally, you may draw boundaries around contiguous point subsets in X such that the cut is proportional to the boundary of your drawing multiplied by the average degree whereas the density of the set is proportional to the area. And, that would remain the case if all points were blue. Moreover, in the case that all points are blue, it is also thus well-understood that the set X achieving minimum ${\mathrm{\Phi }}_X$ would correspond to the maximal fat convex contiguous area, as the perimeter to area ratio is thus minimized [1]. But now that we have red nodes as well, does this remain true? We argue that it does remain true.

Note first that we may still represent our cut around any set X via drawing boundaries around the contiguous point subsets in X, except that now there will be some long “short-cut” edges that we also have to consider arising from the red nodes. Note that the red nodes still remain connected to their close neighbors via the wireless edges, of which there are $\mathrm{\Theta }(\log \hspace{0.17em}n)=\mathrm{\Theta }(d)$ for each red node, whereas there are at most $\mathrm{3}$ wired edges going out from it (and at most $\mathrm{1}$ in the case of $G_{\mathrm{2}}$ ). Therefore, it is clear that, for any set X of strictly less than half the total nodes, if there is a red node p near the border of X but excluded from X, the set $Y=X\cup \{p\}$ is such that ${\mathrm{\Phi }}_Y\le {\mathrm{\Phi }}_X$ . In other words, where $\mathrm{\Delta }\ge \mathrm{0}$ is the difference between the number of wireless neighbors of p and the number of wired neighbors of p, we obtain

$$\begin{array}{cc}& {\mathrm{\Phi }}_X=\frac{\left|\text{Cut}\left(X,V\setminus X\right)\right|}{d\left|X\right|}>\frac{\left|\text{Cut}\left(X,V\setminus X\right)\right|-\mathrm{\Delta }}{d\left|X+\mathrm{1}\right|}={\mathrm{\Phi }}_Y.\end{array}$$

(3)

Therefore, it remains true that even in the presence of red nodes we do indeed minimize conductance with contiguous and larger convex point sets. The largest such feasible set is directly any cut that is right down the middle of our unit square. So now that we know what the structure of the set X achieving $\mathrm{\Phi }={\mathrm{\Phi }}_X$ looks like, let us bound ${\mathrm{\Phi }}_X$ .

We know from our model and Coupon Collection that the frequency of red nodes is $\mathrm{\Theta }(\mathrm{1}/k^{\mathrm{2}}\log \hspace{0.17em}n)$ with high probability for any large enough contiguous fat convex region (our model is actually stronger than a model required to guarantee this). Any region containing at least $k^{\mathrm{2}}\log \hspace{0.17em}n\log \hspace{0.17em}\hspace{0.17em}\log \hspace{0.17em}n$ nodes satisfies this criterion with high probability. So, first let us establish our bounds for such large regions, for both models $G_{\mathrm{1}}$ and $G_{\mathrm{2}}$ , and then we consider the expansion of small sets.

First, we make our argument for $G_{\mathrm{1}}$ using the expansion of the red nodes from Remark  15 of the original paper. By definition of expansion, w.h.p.

$$\begin{array}{cc}& \exists c>{\mathrm{0}}_{\ni }\left|\text{Cut}\left(X,V\setminus X\right)\right|\ge \frac{c\left|X\right|}{k^{\mathrm{2}}\log \hspace{0.17em}n}.\end{array}$$

(4)

This bound follows from the expander linked additions alone and immediately allows us to obtain our bound on the conductance for $G_{\mathrm{1}}$ :

$$\begin{array}{cc}& \mathrm{\Phi }={\mathrm{\Phi }}_X\ge \frac{c}{d_{\text{ave}}{k}^{\mathrm{2}}\log \hspace{0.17em}n}=\frac{c}{k^{\mathrm{2}}{\log \hspace{0.17em}}^{\mathrm{2}}n}\end{array}$$

(5)

with high probability.

What happens for $G_{\mathrm{2}}$ ? Here we must make some use of the facts that the set X achieving the conductance contains half of the total nodes, the red nodes in X are distributed evenly throughout X with frequency $\mathrm{1}/k^{\mathrm{2}}\log \hspace{0.17em}n$ , and X is chosen independently of the manner in which the red wired edges are connected. In particular, we wish to use these facts to show that, with high probability, the set of wired edges which cross the cut is of size at least $\mathrm{\Theta }(n/k^{\mathrm{2}}\text{polylog}(n))$ : for any particular red node p, the probability that the wired $\mathrm{1}$ -out neighbor q that p chooses is in $V\setminus X$ is $\mathrm{1}/\mathrm{2}$ . Moreover, over the entire set of red nodes in X, this probability remains independently $\mathrm{1}/\mathrm{2}$ for each node. Thus, this edge selection process may be modeled via Coupon Collection, where the “balls” correspond to red $\mathrm{1}$ -out neighbors chosen by red nodes of X, and there are exactly two “bins” which correspond to the sets X and $V\setminus X$ , respectively. As the number of balls $n/\mathrm{2}{k}^{\mathrm{2}}\log \hspace{0.17em}n$ is incomparably greater than the number of bins (just $\mathrm{2}$ ), the precondition of the Coupon Collection theorem is satisfied, so that we may state this: with very high probability, the number of balls in the first bin is asymptotically the same as the number of balls in the second bin, meaning that both have $\mathrm{\Theta }(n/\mathrm{4}{k}^{\mathrm{2}}\log \hspace{0.17em}n)$ number of balls. Just considering the meaning of the second bin, this means that the number of wired neighbors of red nodes in X that crosses into $V\setminus X$ is $\mathrm{\Theta }(n/\mathrm{4}{k}^{\mathrm{2}}\log \hspace{0.17em}n)$ with high probability. Thus, with high probability,

$$\begin{array}{cc}& \left|\text{Cut}\left(X,V\setminus X\right)\right|\ge \mathrm{\Theta }\left(\frac{\left|X\right|}{k^{\mathrm{2}}\log \hspace{0.17em}n}\right).\end{array}$$

(6)

Plugging this into the conductance equation, we obtain for $G_{\mathrm{2}}$ that

$$\begin{array}{cc}& {\mathrm{\Phi }}_X=\frac{\left|\text{Cut}\left(X,V\setminus X\right)\right|}{d\left|X\right|}\ge \mathrm{\Theta }\left(\frac{\mathrm{1}}{k^{\mathrm{2}}{\log \hspace{0.17em}}^{\mathrm{2}}n}\right).\end{array}$$

(7)

Finally, we consider what happens under both models for small sets X such that $|X|<k^{\mathrm{2}}\log \hspace{0.17em}n\log \hspace{0.17em}\hspace{0.17em}\log \hspace{0.17em}n$ nodes: to obtain a lower bound on ${\mathrm{\Phi }}_X$ of such situations, it suffices to consider the worst case set conductance on the wireless edges alone (as considering wired links would only improve the bound). And, again, as fat convex contiguous regions minimize set conductance for sets of the same size in a geometric setting, we may directly bound the two-dimensional isoperimetric ratio multiplied by the degree to bound the conductance

$$\begin{array}{cc}& {\mathrm{\Phi }}_X\ge \mathrm{\Theta }\left(\frac{d\sqrt{\left|X\right|}}{d\left|X\right|}\right)=\mathrm{\Omega }\left(\frac{\mathrm{1}}{\sqrt{\left|X\right|}}\right)=\mathrm{\Omega }\left(\frac{\mathrm{1}}{k\log \hspace{0.17em}n}\right).\end{array}$$

(8)

In all cases, for both models $G_{\mathrm{1}}$ and $G_{\mathrm{2}}$ and for both large and small sets, we obtain

$$\begin{array}{cc}& \mathrm{\Phi }=\mathrm{\Omega }\left(\frac{\mathrm{1}}{k^{\mathrm{2}}{\log \hspace{0.17em}}^{\mathrm{2}}n}\right).\end{array}$$

(9)

This completes our proof.