No entiendo el algoritmo de generación rápida de grafos estocásticos de Kronecker

Question

He estado leyendo este documento y usando esto enlace como referencia al leer sobre Gráficos estocásticos de Kronecker y no entiendo el algoritmo que genera dicho gráfico de forma recursiva y en $O(n)$ tiempo ( $n = \text{number of edges}$ )

Para resumir, esto es lo que dice el algoritmo (puede encontrar más detalles en la sección 3.6 del documento referido):

Para cada arista, elegimos recursivamente subregiones de la gran matriz estocástica con probabilidad proporcional a $p_{uv} _1$ hasta descender a una sola celda de la gran matriz estocástica. Allí colocamos el borde. Para un gráfico de Kronecker de $k^{\text{th}}$ poder, $_k$ El descenso se llevará a cabo $k$ pasos.

Sería genial si alguien pudiera explicar esto en detalle, posiblemente trabajando con un ejemplo o de otra manera. No puedo entender cómo se hace exactamente la selección recursiva de subregiones, y en qué se basa la colocación del borde finalmente. Además, no veo por qué es $O(n)$ en la complejidad del tiempo.

Muchas gracias de antemano.

Answer 1

Empecemos por la matriz del iniciador $$\mathcal P_1 = \begin{bmatrix}a & b \\ c & d\end{bmatrix}$$ como ejemplo. A continuación, $\mathcal P_2, \mathcal P_3, \dots, \mathcal P_k$ se definen recursivamente mediante la fórmula $$\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}.$$ Cuando muestreamos una arista, nuestro objetivo es elegir la arista $(v_i, v_j)$ con probabilidad proporcional a $(\mathcal P_k)_{ij}$ . La probabilidad exacta es $\frac{(\mathcal P_k)_{ij}}{(a+b+c+d)^k}$ ya que $(a+b+c+d)^k$ es la suma de las entradas de $\mathcal P_k$ .

Para hacer esto recursivamente, nosotros:

1. En primer lugar, elija uno de los cuatro $2^{k-1} \times 2^{k-1}$ bloques de $$\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}$$ con probabilidades $\frac{a}{a+b+c+d}, \frac{b}{a+b+c+d}, \frac{c}{a+b+c+d}, \frac{d}{a+b+c+d}$ respectivamente.
2. Este bloque se divide en cuatro $2^{k-2} \times 2^{k-2}$ bloques proporcionales a $\mathcal P_{k-2}$ . Elegimos uno de esos cuatro bloques con las mismas probabilidades: $\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. Elija repetidamente uno de los cuatro subbloques del bloque que miramos con estas cuatro probabilidades, hasta que terminemos en una sola entrada.

Por ejemplo, en el $k=3$ caso, tenemos $$\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}$$ Terminamos eligiendo el borde $(v_2, v_3)$ si elegimos la parte superior izquierda $4\times 4$ bloque, con probabilidad $\frac{a}{a+b+c+d}$ , luego la parte superior derecha $2 \times 2$ subbloque de ese bloque, con probabilidad $\frac{b}{a+b+c+d}$ entonces la entrada inferior izquierda de ese bloque, con probabilidad $\frac{c}{a+b+c+d}$ . La probabilidad de que esto ocurra es $\frac{abc}{(a+b+c+d)^3}$ que es exactamente la probabilidad que queríamos, ya que $(\mathcal P_3)_{23} = abc$ .