Chung–Lu Model

The Chung-Lu model generates a graph with potential self-loops given a expected degree sequence as the degree specification.

• Motivation: the Algorithm 2 Sampling is similar to uniformly sampling a graph in the graph space; Chung-Lu model is similar to Erdos-Renyi Random Graph and thus is easier to analyze.
• Model: Fixed $n$, undirected, expected degree sequence $(d_i{)}_{i=1}^n$, $1\{(i,j)\in E\}\sim \mathrm{Bernoulli}\left(\frac{d_i{d}_j}{{\sum }_k{d}_k}\right)$¹
• Phase transitions
  • Connectivity: ${\sum }_k\exp (-d_k)=o(1)$
    • The above threshold ensures no isolated nodes, which is conjectured to be the same threshold for connectivity
  • Giant component: $⟨d^2⟩/⟨d⟩>2$
    • See ^95d986
• Example: $d_i=\frac{\lambda n}{n-\lambda }$ gives ER$\left(n,\frac{\lambda }{n}\right)$
• Remarks:
  • Assumption: ${\max }_i{d}_i^2<{\sum }_k{d}_k$
    • Or just cap the probability to be $p_{ij}=1\wedge \frac{d_i{d}_j}{{\sum }_k{d}_k}$
    • When ${\max }_i{d}_i^2\ll {\sum }_k{d}_k$, the probability of self-loops is of higher-order
  • Typical regime of interest: sparse $m=\Theta (n)$
  • All edges are drawn independently
    • An alternative generation process is place a Poison-distributed number of edges with mean $\frac{d_i{d}_j}{{\sum }_k{d}_k}$ between each pair of nodes, which may generate multi-edges and self-loops
  • An alternative model is to set the probability of self-loops to $0$ and renormalize the probabilities of other edges, which leads to slightly off expected degrees but is asymptotically equivalent
  • The realized degree distribution can differ significantly from the expected degree sequence

Connectivity

Let $\mathrm{vol}:={\sum }_k{d}_k$. Suppose ${\max }_i{d}_i^2\ll \mathrm{vol}$. Then, the probability that node $i$ is isolated is

$$\prod _{j\ne i}\left(1-\frac{d_i{d}_j}{\mathrm{vol}}\right)\approx \exp \left(-\frac{d_i}{\mathrm{vol}}\sum _{j\ne i}{d}_j\right)\approx \exp (-d_i).$$

Thus, the probability of having no isolated nodes is

$$\prod _{i=1}^n\left(1-\exp (-d_i)\right)\approx \exp \left(-\sum _k\exp (-d_k)\right).$$

Footnotes

1. Some definitions model $1\{(i,i)\in E\}\sim \mathrm{Bernoulli}\left(\frac{d_i^2}{2{\sum }_k{d}_k}\right)$ if $(i,i)$ is counted twice in the process, or contributes two degrees to node $i$. ↩