I don't understand the fast generation algorithm for Stochastic Kronecker Graphs

Question

I've been reading this paper and using this link as a reference while reading about Stochastic Kronecker Graphs, and I don't understand the algorithm that generates such a graph recursively and in $O(n)$ time ($n = \text{number of edges}$)

To summarize, here's what the algorithm says (you can find more details in Section 3.6 of the referred paper):

For each edge, we recursively choose sub-regions of the large stochastic matrix with probability proportional to $p_{uv} ∈ Θ_1$ until we descend to a single cell of the large stochastic matrix. We place the edge there. For a Kronecker graph of $k^{\text{th}}$ power, $Θ_k$, the descent will take $k$ steps.

It'd be great if someone could explain this in detail, possibly by working through an example or otherwise. I can't understand how exactly the recursive selection of sub-regions is being done, and on what basis the edge is finally being placed. Moreover, I don't see why it's $O(n)$ in time complexity.

Thanks a lot in advance!

Answer 1

Let's start from the initiator matrix $$\mathcal P_1 = \begin{bmatrix}a & b \\ c & d\end{bmatrix}$$ as an example. Then $\mathcal P_2, \mathcal P_3, \dots, \mathcal P_k$ are defined recursively by the formula $$\mathcal P_i = \begin{bmatrix}a \mathcal P_{i-1} & b \mathcal P_{i-1} \\ c \mathcal P_{i-1} & d \mathcal P_{i-1}\end{bmatrix}.$$ When we sample an edge, our goal is to choose edge $(v_i, v_j)$ with probability proportional to $(\mathcal P_k)_{ij}$. The exact probability is $\frac{(\mathcal P_k)_{ij}}{(a+b+c+d)^k}$, since $(a+b+c+d)^k$ is the sum of the entries of $\mathcal P_k$.

To do this recursively, we:

1. First, choose one of the four $2^{k-1} \times 2^{k-1}$ blocks of $$\mathcal P_k = \begin{bmatrix}a \mathcal P_{k-1} & b \mathcal P_{k-1} \\ c \mathcal P_{k-1} & d \mathcal P_{k-1}\end{bmatrix}$$ with probabilities $\frac{a}{a+b+c+d}, \frac{b}{a+b+c+d}, \frac{c}{a+b+c+d}, \frac{d}{a+b+c+d}$, respectively.
2. That block is divided into four $2^{k-2} \times 2^{k-2}$ blocks proportional to $\mathcal P_{k-2}$. We choose one of those four blocks with the same probabilities: $\frac{a}{a+b+c+d}, \frac{b}{a+b+c+d}, \frac{c}{a+b+c+d}, \frac{d}{a+b+c+d}$.
3. Repeatedly choose one of the four subblocks of the block we look at with these four probabilities, until we end up at a single entry.

For example, in the $k=3$ case, we have $$ \mathcal P_3 = \begin{bmatrix} aaa & aab & aba & abb & baa & bab & bba & bbb \\ aac & aad & abc & abd & bac & bad & bbc & bbd \\ aca & abb & ada & adb & bca & bcb & bda & bdb \\ acc & acd & adc & add & bcc & bcd & bdc & bdd \\ caa & cab & cba & cbb & daa & dab & dba & dbb \\ cac & cad & cbc & cbd & dac & dad & dbc & dbd \\ cca & cbb & cda & cdb & dca & dcb & dda & ddb \\ ccc & ccd & cdc & cdd & dcc & dcd & ddc & ddd \end{bmatrix} $$ We end up choosing edge $(v_2, v_3)$ if we choose the top left $4\times 4$ block, with probability $\frac{a}{a+b+c+d}$, then the top right $2 \times 2$ subblock of that block, with probabiity $\frac{b}{a+b+c+d}$, then the bottom left entry of that block, with probability $\frac{c}{a+b+c+d}$. The probability of this happening is $\frac{abc}{(a+b+c+d)^3}$, which is exactly the probability we wanted, since $(\mathcal P_3)_{23} = abc$.