This is exercise 16.3 from Newman's Networks: An Introduction. I'm trying to find the critical vertex occupation probability, $\phi_c$, of a configuration model network that only has vertices with degree 1, 2, and 3. There are $p_1$ with degree 1, $p_2$ with degree 2, and $p_3$ with degree 3 where $p_j$ is the fraction of total vertices with that degree. The critical occupation probability is defined as:

$$\phi_c = \frac{\langle k \rangle}{\langle k^2 \rangle - \langle k\rangle} $$

which is the minimum fraction of vertices that must be present in the configuration model network for a giant cluster to exist.

If there are $n$ vertices in the network, that means:

$$ n = p_1n + p_2n + p_3n$$

I think the fact that $\langle k \rangle = \frac{1}{n} \sum_i k_i$ and $\langle k^2 \rangle = \frac{1}{n} \sum_i k_i^2$ can be used such that:

$$ \phi_c = \frac{\frac{1}{n}\sum_i k_i}{\frac{1}{n}\sum_i k_i^2 - \frac{1}{n}\sum_i k_i}$$ $$ \frac{p_1n+2p_2n+3p_3n}{(p_1n+2p_2n+3p_3n)^2 - (p_1n+2p_2n+3p_3n)} $$ $$ \frac{p_1n+2p_2n+3p_3n}{(p_1n+2p_2n+3p_3n)((p_1n+2p_2n+3p_3n) - 1)} $$ $$ \frac{1}{(p_1n+2p_2n+3p_3n) - 1} $$

I'm not sure this is the right way to go since the second part of the question requires showing that there is no giant cluster for any value of the occupation probability $\phi$ if $p_1 > 3p_3$ and I'm not seeing a bridge from what I get above or how to approach part c?

Any direction is greatly appreciated.


Your derivation goes wrong in the step $$ \frac{\frac{1}{n}\sum_i k_i}{\frac{1}{n}\sum_i k_i^2 - \frac{1}{n}\sum_i k_i} = \frac{p_1n+2p_2n+3p_3n}{(p_1n+2p_2n+3p_3n)^2 - (p_1n+2p_2n+3p_3n)} $$ Assuming that $k_i$ denotes the degree of node $i$, it's true that $\frac1n \sum_i k_i = \frac1n (p_1n + 2p_2n + 3p_3n)$, but it's not true that $\frac1n \sum_i k_i^2 = \frac1n (p_1n + 2p_2n + 3p_3n)^2$. That's the expression for $\frac1n \left(\sum_i k_i\right)^2$.

Instead, to find the average squared degree $\langle k^2\rangle$, notice that a squared degree is $1$ with probability $p_1$, $4$ with probability $p_2$, and $9$ with probability $p_3$, so we should have $\langle k^2\rangle = p_1 + 4p_2 + 9 p_3$ just as we have $\langle k \rangle = p_1 + 2p_2 + 3 p_3$. Therefore $$ \frac{\langle k\rangle}{\langle k^2\rangle - \langle k \rangle} = \frac{p_1 + 2p_2 + 3 p_3}{(p_1 + 4 p_2 + 9 p_3) - (p_1 + 2p_2 + 3 p_3)} = \frac{p_1 + 2p_2 + 3 p_3}{2p_2 + 6 p_3}. $$ A hint for part (b) of the problem is to write this as $$1 + \frac{p_1 - 3p_3}{2p_2 + 6p_3}.$$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.