Configuration Model

• Motivation: The basic ER model has a binomial/Poisson degree distribution. How do we generate a network with any degree distribution/tail behavior?
• Model: graphic sequences $(d_i{)}_{i=1}^n$ converging to a degree distribution $(p_d{)}_{d\in \mathbb{N}}$
  • i.e., $(p_d^{(n)})\to (p_d)$, so we can use the Local Branching property
  • We use $⟨d^k⟩$ to denote the $k$-th moment of the degree distribution, i.e., $⟨d^k⟩={\sum }_d{d}^k{p}_d$
• Basic properties
  • Expected excess degree: $⟨\tilde{d}⟩=⟨d^2⟩/⟨d⟩-1$
  • Local Clustering: $\mathbb{E}{C}_i=\frac{1}{n}\frac{(⟨d^2⟩-⟨d⟩{)}^2}{⟨d{⟩}^3}$
• Phase transitions
  • Giant component: $⟨d^2⟩>2⟨d⟩$
    • Small component size: $1+\frac{⟨d{⟩}^2}{2⟨d⟩-⟨d^2⟩}$
  • Connectivity for power law: $\gamma \le 2$
    • General: $g_1(0)=0$, where $g_1$ is the PGF of the excess degree distribution
• Diameter: $\ln n/\ln ⟨\tilde{d}⟩$ when $⟨\tilde{d}⟩>1$

Degree specification

Given $n$ nodes, we can specify their degrees with three levels:

1. a fixed degree sequence $(d_i{)}_{i=1}^n$ such that $D_i=d_i$ (Algorithm 1 Uniform Stub-Matching);
2. a degree expectation sequence $(d_i{)}_{i=1}^n$ such that $\mathbb{E}{D}_i=d_i$ (Chung–Lu Model); and
3. a degree distribution $(p_d{)}_{d\in \mathbb{N}}$ such that $\mathbb{P}(D_i=d)=p_d$ (Algorithm 2 Sampling).

Generally, the configuration model is the family of random graph models that generate networks from any degree specification above. People also categorize the models into microcanonical and canonical (soft) configuration models, referring to the first and second degree specification levels respectively. Chung–Lu Model is the canonical canonical configuration model. Customarily, the configuration model refers a specific process of generating a random graph with a fixed degree sequence, which is the focus of this note. The properties in this note also hold in expectation when the fixed degree sequence is a realization of a degree distribution (the third specification).

Graphic sequence

Given a degree sequence $(d_i{)}_{i=1}^n$ with $d_1\ge d_2\ge \cdots \ge d_n$ WLOG, a graph with this degree sequence exists if and only if ${\sum }_{i=1}^n{d}_i$ is even and for all $k\in [n-1]$,

$$\sum _{i=1}^k{d}_i\le k(k-1)+\sum _{i=k+1}^n(d_i\wedge k).$$

A degree sequence satisfying these two conditions is called a graphic sequence.

Algorithm 1: Uniform Stub-Matching

1. List all nodes, each with $d_i$ stubs (half-edges).
2. Uniformly randomly match two stubs and form an edge, and delete the two stubs.
3. Repeat step 2 until no stubs are left.

• Possible to generate a multigraph with self-loops and multiple edges.
• Cumbersome to generate and does not scale with $n$.

Multi-edges and Self-loops

Under suitable assumptions on the degree sequence and as $n$ grows, we can work directly with the generated multigraph, and show it has essentially the same properties as a randomly selected graph with the same degree sequence; or we can delete self-links and duplicate links in the generated multigraph, and show the proportion of deletions is suitably small, and we end up with a graph with a degree distribution close to the specification.

The justification is the following two propositions.

Prop

Consider an infinite degree sequence $(d_1,d_2,\dots )$ such that ${\max }_{i\le n}{d}_i=o(n^{1/3})$. Then

$$\underset{n\to \infty }{\lim }\underset{i\le n}{\max }P(i\text{ has a self-loop or a multiple edge})=0.$$

Pf

Fix $n$. Let ${\bar{d}}_n,{\hat{d}}_n$ be the average and maximum degree in the first $n$ nodes, respectively. Consider an equivalent procedure that first matches all stubs of an arbitrary node $i$, and then move on to the next node, and so on. In this procedure, the probability of the first edge being a self-loop or a multiple edge is $\frac{d_i-1}{n{\bar{d}}_n-1}\le \frac{{\hat{d}}_n}{n{\bar{d}}_n-{\hat{d}}_n}$. Then, suppose the the first edge goes to node $j$. The probability of the second edge being a self-loop or a multiple edge is $\frac{d_i-2}{n{\bar{d}}_n-2}+\frac{d_j-1}{n{\bar{d}}_n-2}\le \frac{2{\hat{d}}_n}{n{\bar{d}}_n-{\hat{d}}_n}$. By induction, the probability of node $i$ having no self-loop or multiple edge is at least

$$\prod _{k=1}^{d_i}\left(1-\frac{j{\hat{d}}_n}{n{\bar{d}}_n-{\hat{d}}_n}\right)\ge {\left(1-\frac{{\hat{d}}_n^2}{n{\bar{d}}_n-{\hat{d}}_n}\right)}^{{\hat{d}}_n}\approx \exp \left(-\frac{{\hat{d}}_n^3}{n{\bar{d}}_n-{\hat{d}}_n}\right)\to 1.$$

The above proposition does not imply that the process will generate no self-links or duplicate links. When one aggregates across many nodes, there will tend to be some duplicate and self-links in this process, except under more extreme assumptions on the degree sequences. We now calculate the expected total number of multi-edges and self-loops.

Prop

The expected total number of self-loops is $\frac{⟨d^2⟩-⟨d⟩}{2⟨d⟩}$ and the expected total number of multi-edges is $\frac{1}{2}{\left(\frac{⟨d^2⟩-⟨d⟩}{⟨d⟩}\right)}^2$.

Pf

For node $i$, the probability it has a self link is $\left(\genfrac{}{}{0ex}{}{d_i}{2}\right)\cdot \frac{1}{2m-1}$. Thus, the expected total number of self-loops is

$$\sum _i\frac{\left(\genfrac{}{}{0ex}{}{d_i}{2}\right)}{2m-1}\approx \frac{{\sum }_i{d}_i(d_i-1)}{4m}=\frac{⟨d^2⟩-⟨d⟩}{2⟨d⟩}.$$

Note that under the uniform stub-matching process, the probability of a link between two nodes $i$ and $j$ is $\frac{d_i{d}_j}{2m-1}$, where $m=\frac{1}{2}{\sum }_i{d}_i$ is the total number of edges. Conditioned on that $i,j$ are connected by a first link, they form a second link with probability $\frac{(d_i-1)(d_j-1)}{2m-3}$. The product of the two probabilities is the probability of a multi-edge between $i$ and $j$ (more than two links count as one multi-edge). Suppose $m\gtrsim n\to \infty$. Then, the expected number of multi-edges is

$$\sum _{i<j}\frac{d_i{d}_j(d_i-1)(d_j-1)}{(2m-1)(2m-3)}\approx \frac{({\sum }_i{d}_i(d_i-1))({\sum }_j{d}_j(d_j-1))-{\sum }_i{d}_i^2(d_i-1{)}^2}{8m^2}\approx \frac{1}{2}{\left(\frac{⟨d^2⟩-⟨d⟩}{⟨d⟩}\right)}^2,$$

where we assumed that all involved moments exist and grow slower than $n$.

Algorithm 2: Sampling

1. Input: a degree specification $(p_d{)}_{d\in \mathbb{N}}$ of the second type, a size $n$.
2. Generate $D_i\stackrel{\text{i.i.d.}}{\sim }(p_d)$ for $i=1,\dots ,n$.
3. If $(D_i{)}_{i=1}^n$ is not a graphic sequence, go back to step 2.
4. Generate a uniform random match of stubs as in Algorithm 1.
5. If the generated graph has self-links or duplicate links, go back to step 4.

• Re-sampling introduces correlations across nodes and edges, but negligible as a higher-order effect.
• One can show that as $n$ grows:
  • $\#\text{self-loops}\stackrel{d}{\sim }\mathrm{Poisson}({\lambda }_{\mathrm{self}})$ with ${\lambda }_{\mathrm{self}}=O(1)$,
  • $\#\text{duplicate edges}\stackrel{d}{\sim }\mathrm{Poisson}({\lambda }_{\mathrm{dup}})$ with ${\lambda }_{\mathrm{dup}}=O(1)$,
  • $\#\text{self-loops}$ and $\#\text{duplicate edges}$ are asymptotically independent with high probability, and thus
  • the success rate of Algorithm 2 is $\exp (-{\lambda }_{\mathrm{self}}-{\lambda }_{\mathrm{dup}})=O(1)$.

Local Branching

Configuration models including Chung–Lu Model generalize Erdos-Renyi Random Graph to accommodate arbitrary degree distributions. In all these models, the local graph structure is Tree-like, as the probability of an edge linking back to a previously visited node is negligible as $n$ grows.

The local tree structure can be thought of as generated by a Branching process, as all neighbors of a node are generated i.i.d. (not true when correlation exists, see e.g., Problem 3)

Formally, consider a local connected subgraph or a small component of size $s$. Since it’s connected it has at least $s-1$ links. If the degree distribution (or Excess Degree Distribution) has a constant mean w.r.t the graph size $n$, the probability of having an additional link is

$$\left(\left(\genfrac{}{}{0ex}{}{s}{2}\right)-(s-1)\right)\cdot \frac{⟨d⟩}{n}=o(1),$$

where $⟨d⟩/n$ (or $⟨\tilde{d}⟩/n$) is the average probability of a link between two nodes, which is $p$ in ER.

Excess Degree Distribution

To utilize the local branching property, we need to know that is the degree distribution of a neighbor of a node to figure out the offspring distribution. Since this neighbor already has one link to the node, we are interested in the number of its other neighbors, which is called the excess degree. For the following generation, the number of offsprings is specified by the excess degree distribution.

Suppose we have a graph generated by a configuration model and has a degree distribution $D_i\stackrel{\text{i.i.d.}}{\sim }(p_d{)}_{d\in \mathbb{N}}$. According to the process in Algorithm 1 Uniform Stub-Matching, the probability of a node being $i$‘s neighbor is proportional to its degree, so the excess degree a neighbor follows

$$P({\tilde{D}}_j=d)=\frac{(d+1)p_{d+1}}{{\sum }_{d^{\prime }}{d}^{\prime }{p}_{d^{\prime }}}=\frac{(d+1)p_{d+1}}{\mathbb{E}{D}_i},\forall d\in \mathbb{N},$$

which is independent of node $i$. Thus, the extinction probability of this branching process depends on $⟨\tilde{d}⟩=⟨d^2⟩/⟨d⟩-1$.

Random node vs random link

Randomly picking a node from a network vs. randomly following the end of a link, are two very different exercises. The latter is much more likely to find a high degree node.

Friendship paradox

The expected average neighbor degree is hence $\mathbb{E}{D}_i^2/\mathbb{E}{D}_i$, which is no smaller and can be much larger than $\mathbb{E}{D}_i$.

This gives the following phase transition:

A Giant Component appears if $⟨\tilde{d}⟩>1$, i.e., $⟨d^2⟩>2⟨d⟩$. When $⟨\tilde{d}⟩<1$, a component has an expected size of $1+\frac{⟨d{⟩}^2}{2⟨d⟩-⟨d^2⟩}$.

• When $D\sim \mathrm{Poisson}(\lambda )$, we have $\mathbb{E}{D}_i=\lambda$ and $\mathbb{E}{D}_i^2/\mathbb{E}{D}_i=1+\lambda$, so the phase transition occurs at $\lambda =1$, which is consistent with the ER model.
• When $D$ follows a Power Law Distribution with exponent $\gamma$, then $⟨d^2⟩=\zeta (\gamma -2)$ and $⟨d⟩=\zeta (\gamma -1)$, where $\zeta (\cdot )$ is the Riemann zeta function. Thus, the phase transition occurs at $\zeta (\gamma -2)>2\zeta (\gamma -1)$, which is approximately $\gamma <3.4788$.
• The above approximation applies to both Erdos-Renyi Random Graph and Chung–Lu Model.

Clustering Coefficient

A corollary of Local Branching property is a zero clustering coefficient. Intuitively, your neighbors are much more likely to be connected to other nodes than to each other. We formally calculate the expected clustering coefficient without assuming constant moments of the degree distribution:

$$C=\mathbb{E}[\mathbb{E}[1\{(j,k)\in E\}\mid (i,j),(i,k)\in E]].$$

Note that the excess degrees of $j$ and $k$ are independent of $i$ and they randomly pick from the remaining $2(m-2)$ stubs. Thus,

$$\begin{array}{rl}C=& \mathbb{E}[P((j,k)\in E)\mid {\tilde{D}}_j=d_j,{\tilde{D}}_k=d_k]\\ \approx & \sum _{d_j=0,d_k=0}^{\infty }\frac{d_j{d}_k}{2m}\cdot \frac{(d_j+1)p_{d_j+1}(d_k+1)p_{d_k+1}}{⟨d{⟩}^2}\\ =& \frac{1}{2m}{\left(\frac{⟨d^2⟩-⟨d⟩}{⟨d⟩}\right)}^2\\ =& \frac{1}{n}\frac{(⟨d^2⟩-⟨d⟩{)}^2}{⟨d{⟩}^3}.\end{array}$$

Therefore, if $⟨d^2⟩$ grows with $n$, we could have a non-vanishing clustering coefficient.

Diameter

We calculated that the average number of other neighbors of a neighbor is $⟨\tilde{d}⟩=⟨d^2⟩/⟨d⟩-1$. Thus, the number of neighbors at distance $2$ is $⟨d^2⟩-⟨d⟩$. By induction, we know the number of neighbors at distance $r$ is approximately $⟨d⟩⟨\tilde{d}{⟩}^{r-1}$.

For a shortest path $(i,k_1,\dots ,k_{l-1},j)$ from $i$ to $j$, we know that $k_s$ must be at distance $s$ of $i$ and at distance $l-s$ of $j$, i.e., the path also contains the shortest paths from $i$ to $k_s$ and from $j$ to $k_s$, otherwise we can find a shorter path. Therefore, the distance between $i$ and $j$ is no larger than $l$ if there exists a node $k_s$ at distance $s$ of $i$ and a node $k_{s+1}$ at distance $l-s-1$ of $j$ such that $(k_s,k_{s+1})\in E$. The probability of the existence of such a link is

$$⟨d⟩⟨\tilde{d}{⟩}^{s-1}\cdot ⟨d⟩⟨\tilde{d}{⟩}^{l-s-1}\cdot \frac{⟨\tilde{d}{⟩}^2}{2m}=\frac{⟨d⟩⟨\tilde{d}{⟩}^l}{n}.$$

Thus, with probability at least $1-\delta$, the distance between any two nodes is bounded by

$$\frac{\ln \delta +\ln n-\ln ⟨d⟩}{\ln ⟨\tilde{d}⟩}\asymp \frac{\ln n}{\ln ⟨\tilde{d}⟩}.$$

Thus, Small-World Effect holds if $⟨\tilde{d}⟩>1$.