The Central Limit Theorem

A familiar start

• There is a criticality condition of $\mathbb E[X_i] = 0$
• We have moment conditions in that the second moment must be finite
• We scale the sum by $n^{-1/2}$
• The limit is universal, depending only on $\sigma^2$

Degrees

Some graph theory

Let $\digr$ be a directed graph (digraph) on the vertex set $\{1, \ldots, n\}$ and let $v$ be a vertex of $\digr$.

• Let $d^-(v)$ be the in-degree of $v$
• Let $d^+(v)$ be the out-degree of $v$
• The degree sequence of $\digr$ is given by $(\vd_1, \ldots, \vd_n) \in (\N \times \N)^n$ where $\vd_i = (d^-(i), d^+(i))$

This has degree sequence $((1, 2), (2, 1), (1, 2), (2, 1))$

Strong Connectivity

Some more graph theory

• Two vertices $v$ and $w$ are strongly connected, written $v \leftrightarrow w$, if there exists a directed cycle containing both $v$ and $w$
• The strongly connected components (SCCs) are the equivalence classes of $\leftrightarrow$
• The condensation is the digraph obtained by collapsing the SCCs of $\digr$ and $\digr$

A graph (with blue vertices) separated into SCCs. The yellow graph is then the condensation.

Random digraphs with i.i.d. degree sequences

Let $\nu$ be a distribution on $\N \times \N$ and $(D^-, D^+) \sim \nu$. We assume $\E[D^-] = \E[D^+]$. We sample $\digr_n(\nu)$ by:

• Sampling $\vD_1, \ldots, \vD_n \overset{i.i.d.}{\sim} \nu$
• Repeating the sampling until $\sum_{i=1}^n D_i^- = \sum_{i=1}^n D_i^+$, where $\vD_i = (D_i^-, D_i^+)$
• Pick a digraph with vertex set $\{1, \ldots, n\}$ and degree sequence $(\vD_1, \ldots, \vD_n)$ uniformly at random

Question: Why consider this model?

• The degrees of vertices in a network are often easy to access
• Simplest model given the degree sequence
• Can serve as null hypothesis for additional graph structure

Question: Given a degree sequence, how do we sample a digraph uniformly with a given degree sequence?

The directed configuration model (DCM)

Suppose we are given a degree sequence $(\vd_1, \ldots, \vd_n)$ such that $\sum_{i=1}^n d_i^- = \sum_{i=1}^n d_i^+$. To sample a graph uniformly with this degree sequence we:

• Attach $d_i^-$ in-half-edges and $d_i^+$-out-half-edges to the vertex $i$
• Take a uniform pairing of the in- and out- half edges
• Repeat until the resulting multigraph is simple

For example consider the sequence $((1, 2), (1, 2), (1, 1), (3, 1), (1, 1))$.

Depth First Exploration / Construction

Depth First Exploration / Construction

Depth First Exploration / Construction

Depth First Exploration / Construction

Depth First Exploration / Construction

Depth First Exploration / Construction

Depth First Exploration / Construction

Depth First Exploration / Construction

Depth First Exploration / Construction

Depth First Exploration / Construction

Depth First Exploration / Construction

Depth First Exploration / Construction

Depth First Exploration / Construction

Description of exploration

• If the stack is empty
  • Pick a new vertex and add its out-half-edges to the stack
• Else
  • Pick a unpaired in-half-edge uniformly at random
  • Pair it to the last out-half-edge on the stack, and remove it from the stack
  • Add any new out-half-edges discovered to the end of the stack

Criticality

$\E[Z^+] = 1$ is equivalent to $\E[D^- D^+] = \E[D^{\pm}]$.

What do critical SCCs look like?

Kernels of digraphs

Metric Multi-Digraphs (MMDs)

and their associated pseudo-metric

• The kernel of a digraph is a weighted multi digraph, or metric multi-digraph (MMD)
• These are easy to scale! (Scale the edge lengths)
• Two MMDs $M_1$ and $M_2$ are isomorphic if their graph structure is the same up to relabelling of vertices and edges
• Can define a pseudometric $d_{\digr}(M_1, M_2)$ by taking
  • $d_{\digr}(M_1, M_2) = \infty$ is $M_1$ and $M_2$ are not isomorphic
  • $d_{\digr}(M_1, M_2)$ is the $\ell_{\infty}$ distance between the edge lengths if $M_1$ and $M_2$ are isomorphic, where we take the isomorphism which minimises this distance

Assumptions

Suppose $\nu$ is a measure on $\N \times \N$ and $(D^-, D^+) \sim \nu$. We assume the following holds:

• $E[D^-] = E[D^+]$
• $D^+$ and $D^-$ are non-constant and $\mathbb P(\sum_{i=1}^n D_i^- = \sum_{i=1}^n D_i^+)$ for all sufficiently large $n$
• $\E[D^- D^+] = \E[D^{\pm}]$ (criticality condition)
• $\E[(D^-)^i (D^+)^j] < \infty$ for $i + j \leq 3$, $(i, j) = (1, 3)$ and $(j, i) = (3, 1)$ (moment conditions)

Our result