CS代写|PCS810 Complex Networks

The cluster size distribution in Erdos Renyi is described by expression
$$
c_k(t)=\frac{k^{k-2}}{k !} t^{k-1} e^{-k t},
$$
where $t=p N$ is the average degree in a network of $\mathrm{N}$ nodes.
A) (3 points) Study this distribution asymptotically at $k \rightarrow \infty$ and $t=1$.
Show that the infinite cluster is formed at this point: distribution moments diverge starting from the $2 \mathrm{nd}$.

B) (2 points) Study this distribution asymptotically at $k \rightarrow \infty$ and $t=1-\epsilon$
$(\epsilon<1)$. Show that the distribution looks like $c_k(t)=k^{-\alpha} \exp (-k / f(\epsilon))$. Find $\alpha$ and $f(\epsilon)$.

C) (1 points) Define the scaling behavior of the average cluster size in vicinity $t=1$ (as a function of $\mathrm{N}(N>>1$ )). The average cluster size is defined as the 2nd distribution moment.

Consider a regular graph of $N$ nodes and the degree $k$ ( $k$-regular graph).
A) (2 points) Show that the average path length:
$$
l=\frac{N}{2 k} .
$$
B) (2 points) Show that the clustering coefficient (the average local clustering coefficient):
$$
C=\frac{3(k-2)}{(k-1)}
$$

Extension of the small-world result to an infinite lattice: One of the limitation of the above proof is to deal frequently with normalizing constant and finite networks. In this exercise we prove that for at least two cases of the one studied above, a formulation using an infinite lattice can be drawn. In an infinite lattice, one cannot hope to have any bound on the time to connect two arbitrarily far away nodes. On the other hand, one may hope that on an infinite lattice that starting from a node at a fixed distance $D$ from the target, greedy routing finds a path whose length grows slowly with $D$.
(A) Assuming $r>k$, can you prove that Kleinberg’s model extends naturally without modification to an infinite lattice? Why is that impossible when $r \leq 1$ ?
(B) Assuming $r>k$, quickly justify why there exists a constant $C>0$ and $\eta>0$ such that, in expectation, the path found by greedy routing requires at least $C D \eta$ steps when starting from a node at distance $D$ from the target.

We will now prove that Kleinberg model can be modified so that the proof of the critical case $r=k$ applies to an infinite lattice.
(C) For any $\varepsilon>0$, let $f(x)=1 / \log ^{\varepsilon}(x)$. What is $\lim _{x \rightarrow \infty} f(x)$ ? What is $f^{\prime \prime}$ ?
(D) Prove that for any $\varepsilon>0$, one can naturally extend the Kleinberg model to an infinite lattice for $r=k$, assuming that the probability to have a shortcut $u \rightsquigarrow v$ is
$$
\mathbb{P}(u \rightsquigarrow v)=\frac{1}{|u-v|^k \log ^{1+\varepsilon}(|u-v|)} .
$$
(E) From that greedy routing in the above model uses at most $O\left(\log ^{2+\varepsilon}(D)\right)$ steps when starting at distance $D$ from the target.