Little Problem About Small World Graphs

Consider a graph $G := (V, E)$ with $\lvert V \rvert = n$ and $uv \in E$ if and only if $\lvert u - v \rvert = 2^k$ for some $k \in \mathbb{N}_0$. What is $E\left[d\big(u, v) \mid n\right]$? I was interested in showing that this is in fact a “small-world” graph, i.e. that $L \propto \log\big(n)$. This is not so difficult, as the maximum distance between two nodes $u$ and $v$ cannot exceed $\log_2\big(n)$.

My first attempt to find the average involved bounding the average as follows. In this setting, there’s no trip with greater distance than from a node to the node directly behind it, i.e. $d_{n}\big(0, n - 1) \geq E[d_{n}\big(0, v)]$. But this is just a minor improvement over the maximum.

$$\begin{equation} \int_{0}^{n}\frac{\ln\left(u\right)}{n \ln\left(2\right)}\ du = \log_2\big(n) - \frac{1}{\ln\big(2)} \end{equation}$$

Instead, notice that the distance between nodes indexed $u$ and $v$ is equal to the number of bits set in $u \ \text{xor} \ v$. This gives us an expected distance of $0.5 \cdot \log_2\big(n)$ and a distribution of distances that’s very roughly $\operatorname{N}\big(\log_2\big(n)/2, \log_2\big(n)/4)$.