I'm teaching a course on complex networks using M.E.J. Newman's Networks: An Introduction. There is a claim in the book that is not really justified, and I don't know how to prove it.

Background and definitions

Let $(p_k)_{k=0}^{\infty}$ be a probability distribution with mean $\mu$. We choose a degree sequence $\mathbf{d}$ of length $n$ according to $(p_k)$. That is, the probability that $(d_i)_{i=1}^{n}$ is chosen is $\prod_{i=i}^n p_{d_i}$. We suppose that $\sum_i d_i$ is even; let $m$ denote the number of edges. (Here, $n$ tends to infinity and $m$ tends to infinity with $n$.) We then generate a (multi)graph $G$ with degree sequence $\mathbf{d}$ using the configuration model.

One might ask about this graph, "Let $v$ be a randomly chosen vertex and let $e$ be an edge incident to $v$ (if one exists). What is the probability that the vertex $w$ at the end of $e$ has degree $k$?" In Newman's book, this probability is calculated as follows: the expected number of vertices of degree $k$ is $n p_k$, so the (expected?) probability that $e$ is attached to such a vertex is $$\frac{k}{2m-1} n p_k \sim k p_k \frac{n}{2m},$$ which has expected value $$\frac{k p_k}{\mu}. \tag*{(1)}$$ (All of the expectations running around make this part a little confusing.)

Define the excess degree of this randomly chosen vertex $w$ to be the number of edges incident to $w$, except for the edge $e$ that we used to reach $w$, i.e., one less than the degree of $w$.

Let $d'_w$ denote the excess degree of $w$. Since the probability that $d'_w = k$ equals the probability that $d_w = k + 1$, we use the expression in $(1)$ to define $$q_k := \mathbb{P}(d'_w = k) = \frac{(k + 1) p_{k + 1}}{\mu}.$$

(N.B.: $(q_k)_{k=0}^{\infty}$ is often called the size-biased degree distribution; hence the title.)

My question

Are the excess degrees of different vertices independent? If the excess degree is somehow an "intrinsic" property of the degree distribution, then it seems that the answer is yes. However, if it depends on the configuration chosen, then it seems that knowing the excess degree of $v$ would tell you something about the excess degree of $w$.

The motivation and specific context

Section 13.4 of Newman's book discusses the clustering coefficient of a graph chosen in the way described above (note that the definition in use here is the one given in the "Transitivity Ratio" section of the linked Wikipedia article).

The calculation proceeds as follows: choose a vertex $u$ of degree at least two and choose two of its neighbors, $v$ and $w$. Since $v$ and $w$ are each at the end of a randomly chosen edge from $u$, the number of other degrees adjacent to each of $v$ and $w$ is given by the size-biased degree distribution $(q_k)$. Let $v \sim w$ denote the event that there is at least one edge between $v$ and $w$. It is not hard to show that the conditional probability that this occurs is $$\frac{d'_v d'_w}{2m - 1} \sim \frac{d'_v d'_w}{2m}.$$ Thus, we have $$\begin{align} \mathbb{P}(v \sim w) &= \sum_{s = 0}^{\infty} \sum_{t = 0}^{\infty} \mathbb{P}(v \sim w \mid d'_v = s, d'_w = t) \mathbb{P}(d'_v = s, d'_w = t)\\ &= \sum_{s = 0}^{\infty} \sum_{t = 0}^{\infty} \mathbb{P}(d'_v = s, d'_w = t) \frac{s t}{2m}. \end{align}$$ So far, mostly so good. However, the author then claims that $$\mathbb{P}(d'_v = s, d'_w = t) = q_s q_t.$$ As stated above, I don't see why that's true.


My first thought was that indeed it should not be true. However, after several attempts to show this, I come up with and indirect argument that it is actually true.

Newman in his book gets the final results that the clustering coefficient is actually $$ C=\frac{1}{n}\frac{\nu^2}{{\rm E}(D)}, $$
where I denote $$ {\rm E}(D)=\frac{\sum_jd_j}{n},\quad \nu=\frac{{\rm E}(D^2)-{\rm E}(D)}{{\rm E}(D)}. $$ Now exactly the same result by using a different argument. Clustering coefficient is equal to the average number of closed paths of length 2 divided by the average number of paths of length 2. First can be found as $$ {\rm E}(T_n)=\sum_{i,j,k}\frac{d_i(d_i-1)d_j(d_j-1)d_k(d_k-1)}{(2m-1)(2m-3)(2m-5)}\sim \nu^3. $$ The second (the number of paths of length 2) is $$ {\rm E}(W_n)=\sum_{i,j,k}\frac{d_id_j(d_j-1)d_k}{(2m-1)(2m-3)}\sim n {\rm E}(D)\nu, $$ which gives exactly the same result.


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.