CS代写|PCS810 Complex Networks

Clustering in the small-world model: Consider the Watts-Strogatz small-world model, given by a ring lattice in which each node is connected to all nodes within distance $k$. Let $p$ be the rewiring probability.

(A) Show that when $p=0$, the overall clustering coefficient of this graph is given by
$$
C=\frac{3 k-3}{4 k-2} .
$$
*(B) Show that when $p>0$, the clustering coefficient is $C=\frac{3 k-3}{4 k-2}(1-p)^3$.

Norm and number of neighbors on lattices in dimension $k \geq 1$ : This exercise establishes an important step to ansewr the question in following exercises. It does not directly related to the proof seen in lecture but it deals with a fundamental property of lattices that is well worth learning.

A norm on the vector space $\mathbb{R}^k$ is any function $|\cdot|: \mathbb{R}^k \rightarrow[0, \infty)$ such that for all scalars $a \in \mathbb{R}$ and vectors $x, y \in \mathbb{R}^k$,
$$
\begin{aligned}
& |a x|=|a||x| \
& |x+y| \leq|x|+|y| \
& |x|=0 \Longleftrightarrow x=0 .
\end{aligned}
$$
It is classical that all norms on finite-dimensional spaces are equivalent-that is, for any two norms $|\cdot|_A$ and $|\cdot|_B$ there exists $c_1, c_2>0$ such that for all $x \in \mathbb{R}^k$,
$$
c_1|x|_A \leq|x|_B \leq c_2|x|_A
$$

The following functions are all norms:

$l_p$-norm, $1 \leq p<\infty$ :
$$
|x|_p=\left(\sum_{i=1}^k\left|x_i\right|^p\right)^{1 / p} .
$$
In particular, $p=1$ and $p=2$ give the $l_1$ – and $l_2$-norm, respectively:
$$
|x|_1=\sum_{i=1}^k\left|x_i\right|, \quad|x|_2=\sqrt{\sum_{i=1}^k\left|x_i\right|^2} .
$$

$l_{\infty}$-norm:
$$
|x|_{\infty}=\max \left{\left|x_1\right|, \ldots,\left|x_k\right|\right}
$$
(A) Show that in a lattice $\mathbb{Z}^k$ of dimension $k \geq 1$ and for any norm $|\cdot|$, the following holds: there exists $c_1>0$ and $c_2>0$ such that for all $u \in \mathbb{Z}^k$, we have
$$
c_1 j^k \leq\left|\left{v \in \mathbb{Z}^k:|u-v| \leq j\right}\right| \leq c_2 j^k
$$
for every $j>0$.
Hint: The key to answer this easily is to first show it in a well-chosen norm, and then to use the equivalence of norms on finite-dimensional spaces.
(B) Similarly, show that there exists $c_1>0$ and $c_2>0$ such that for all $u \in \mathbb{Z}^k$,
$$
c_1 j^{k-1} \leq\left|\left{v \in \mathbb{Z}^k:|u-v|=j\right}\right| \leq c_2 j^{k-1}
$$
for every $j>0$.
(C) We have essentially proven that in a lattice or grid, the number of points at distance $j$ grows polynomially in $j$ (for any distance such as, for example, the number of edges to traverse in the grid). Does the same hold for any graph (where the distance is again given by the number of edges on a path)?

1-D analogue of Kleinberg small-world model: Nodes are ordered on a line and each node $u$ has a single shortcut, which links it with a node $v$ with probability $\mathbb{P}(u \rightsquigarrow v)$ proportional to $|u-v|^{-\alpha}$. Redo the heuristic given the lecture notes (i.e., no need to give a proof) to determine the navigation times for different values of the clustering exponent $\alpha$. What is the critical value of $\alpha$ that allows greedy routing to work efficiently?

Analysis of Kleinberg small-world model in $\mathbb{Z}^k, k \geq 1$ : A good way to obtain a rigorous proof for the behavior of greedy routing in the Kleinberg model is to study it for different graphs. This exercise is a complement to the rigorous proof of the case $k=1$ given in the notes, which we will complete step by step. Here, the probability $\mathbb{P}(u \rightsquigarrow v)$ of a shortcut from $u$ to $v$ is proportional to $|u-v|^{-r}$ for some constant $r>0$ (note that we are now using $r$ instead of $\alpha$ to denote this exponent!). You may wish to start this exercise immediately after reading the proof in the lecture notes for the three separate cases $r<1, r=1$, and $r>1$ when $k=1$.
(A) Deduce from the previous exercise that for a finite lattice of dimension $k$ (with length $L-1$, containing $N=L^k$ nodes) there exists $\alpha>0$ and $\beta>0$ independent of $N$ such that
$$
\alpha \sum_{j=1}^{\lfloor L / 2\rfloor} \frac{1}{j^{r-(k-1)}} \leq \sum_{v \neq u} \frac{1}{|u-v|^r} \leq \beta \sum_{j=1}^{\lfloor L / 2\rfloor} \frac{1}{j^{r-(k-1)}} .
$$
(B) From this inequality can you briefly justify why the value $r=k$ is critical for dimension $k$ ?
(C) Assuming $r0$ and a constant $c_1>0$ such that
$$
\mathbb{P}(u \rightsquigarrow v) \leq c_1 N^{-\delta} .
$$
(D) Let us denote by $I_l$ the set of nodes at distance at most $l$ from the target $t$ :
$$
I_l={u \in V:|u-t| \leq l} .
$$
Which one of the following is an upper bound on the probability that at least one of the first $n$ shortcuts met by the walk drawn using greedy routing connects to a node within $I_l$ ? (i) $2 c_1 n l / N^\delta$, (ii) $2 c_1 n l^k / N^\delta$, (iii) none of the above.
(E) Conclude that greedy routing needs in expectation at least a constant multiplied by $N^{\frac{k-r}{(k+1)}}$ steps to succeed.
(F) We now assume $r>k$. Prove that the probability that $u$ shortcuts has length greater than $m$ is less than $c_3 / m^{r-k}$. Conclude that greedy routing needs in expectation at least a constant time $N^\eta$ steps for $\eta>0$.
(G) Assuming $r=k$, what can you deduce on the normalizing constant? Prove that the probability for a node in phase $j$ to be connected to a node in phase $j^{\prime}<j$ does not depend on $j$ and becomes small slowly with $N$. This will conclude the proof.