Riemann surface
matlab

2c. Is the sequence of Erdős-Rényi random graphs $\left(\mathrm{ER}n(\lambda / n)\right){n \in \mathbb{N}}$ small world for all choices of $\lambda \in(0, \infty)$ ?

.

Solution: No, only for $\lambda \neq 1$. For $\lambda<1$, all clusters have size $O(\log n)$, in which case the statement is obvious. For $\lambda>1$, there is one giant component, whose size is $\Theta(n)$, while all other clusters again have size $O(\log n)$. But even within the giant component distances are $O(\log n)$. For $\lambda=1$, there are many components of size $\Theta\left(n^{2 / 3}\right)$, and they have larger distances, namely, $\Theta\left(n^{1 / 3}\right)$.

A real-world network is represented as a simple (i.e., with no multiple edges and self-loops) undirected graph $\mathbf{G}^$ with $n=5$ vertices. Chung and Lu decide they want to compare their model with the real-world network. They define their connection probabilities $\left{p_{i j}\right}$ (with $p_{i i} \equiv 0 \forall i$ ) and, after computing them on the real network, they find that $p_{34}>p_{53}, p_{15}>p_{25}$, $p_{43}>p_{14}, p_{52}=p_{45}$. 4a. Find the degree sequence $\vec{k}\left(\mathbf{G}^\right)$ of the real-world network $\mathbf{G}^*$. Explain your result.

Solution: In the Chung-Lu model, the connection probabilities are $p_{i j}=k_i k_j / 2 L$ for $i \neq j$ and $p_{i i}=0$, where $\left{k_i\right}_{i=1}^n$ are the degrees and $L=\sum_{i=1}^n k_i / 2$ is the total number of links. Therefore $p_{i l}>p_{j l}$ implies $k_i>k_j$, and $p_{i l}=p_{j l}$ implies $k_i=k_j$ (for $l \neq i, j$ ). From the (in)equalities given in the text, we can therefore conclude that
$$k_3>k_1>k_2=k_4>k_5$$
Since the degrees are non-negative integers, it is easy to check that the only set of numbers that satisfies the above (in)equalities in such a way that a simple undirected graph can be realized is
$$4>3>2=2>1 .$$
The corresponding degree sequence is:
$$\vec{k}\left(\mathbf{G}^*\right)=(3,2,4,2,1)$$

E-mail: help-assignment@gmail.com  微信:shuxuejun

help-assignment™是一个服务全球中国留学生的专业代写公司