Return to Question

The high-level question is: can we generate any random graph with size $d$ using a Markov chain?

For example, let $X^{(0)} = (1,0,\ldots,0) \in R^d$ be the initial state, and $X^{(t+1)} = f^{(t)}(X^{(t)}, \epsilon^{(t)})$, where $\{\epsilon^{(t)}\}_{t=0}^\infty$ is a sequence of i.i.d. random variables. After $(d-1)$ iterations, we use $Z = \{X^{(0)},\ldots, X^{(d-1)}\}\in R^{d\times d}$ to construct a graph, whose adjacency matrix is, say, $(Z + Z')/2$.

More specifically, can all random graphs, e.g., Erdos-Renyi graph and stochastic block model, be constructed in this way (ideally, with a relatively simple $\{f^{(t)}\}_{t=0}^\infty$)?

The high-level question is: can we generate any random graph with size $d$ using a Markov chain?

For example, let $X^{(0)} = (1,0,\ldots,0) \in R^d$ be the initial state, and $X^{(t+1)} = f^{(t)}(X^{(t)}, \epsilon^{(t)})$, where $\{\epsilon^{(t)}\}_{t=0}^\infty$ is a sequence of i.i.d. random variables. After $(d-1)$ iterations, we use $Z = \{X^{(0)},\ldots, X^{(d-1)}\}\in R^{d\times d}$ to construct a graph, whose adjacency matrix is, say, $(Z + Z')/2$.

In specific, can all random graphs, e.g., Erdos-Renyi graph and stochastic block model, be constructed in this way (ideally, with a relatively simple $\{f^{(t)}\}_{t=0}^\infty$)?

The high-level question is: can we generate any random graph with size $d$ using a Markov chain?

For example, let $X^{(0)} = (1,0,\ldots,0) \in R^d$ be the initial state, and $X^{(t+1)} = f^{(t)}(X^{(t)}, \epsilon^{(t)})$, where $\{\epsilon^{(t)}\}_{t=0}^\infty$ is a sequence of i.i.d. random variables. After $(d-1)$ iterations, we use $Z = \{X^{(0)},\ldots, X^{(d-1)}\}\in R^{d\times d}$ to construct a graph, whose adjacency matrix is, say, $(Z + Z')/2$.

In specific, can all random graphs, e.g., Erdos-Renyi graph and stochastic block model, be constructed in this way (ideally, with a relatively simple $\{f^{(t)}\}_{t=0}^\infty$)?

The high-level question is: can we generate any random graph with size $d$ using a Markov chain?

For example, let $X^{(0)} = (1,0,\ldots,0) \in R^d$ be the initial state, and $X^{(t+1)} = f^{(t)}(X^{(t)}, \epsilon^{(t)})$, where $\{\epsilon^{(t)}\}_{t=0}^\infty$ is a sequence of i.i.d. random variables. After $(d-1)$ iterations, we use $Z = \{X^{(0)},\ldots, X^{(d-1)}\}\in R^{d\times d}$ to construct a graph, whose adjacency matrix is, say, $(Z + Z')/2$.

More specifically, can all random graphs, e.g., Erdos-Renyi graph and stochastic block model, be constructed in this way (ideally, with a relatively simple $\{f^{(t)}\}_{t=0}^\infty$)?

The high-level question is: can we generate any random graph with size $d$ using a Markov chain?

For example, let $X^{(0)} = (1,0,\ldots,0) \in R^d$ be the initial state, and $X^{(t+1)} = f^{(t)}(X^{(t)}, \epsilon^{(t)})$, where $\{\epsilon^{(t)}\}_{t=0}^\infty$ is a sequence of i.i.d. random variables. After $(d-1)$ iterations, we use $Z = \{X^{(0)},\ldots, X^{(d-1)}\}\in R^{d\times d}$ to construct a graph, whose adjacency matrix is, say, $(Z + Z')/2$.

In particular, can all random graphs, e.g., Erdos-Renyi graph and stochastic block model, be constructed in this way (ideally, with a relatively simple $\{f^{(t)}\}_{t=0}^\infty$)?

The high-level question is: can we generate any random graph with size $d$ using a Markov chain?

For example, let $X^{(0)} = (1,0,\ldots,0) \in R^d$ be the initial state, and $X^{(t+1)} = f^{(t)}(X^{(t)}, \epsilon^{(t)})$, where $\{\epsilon^{(t)}\}_{t=0}^\infty$ is a sequence of i.i.d. random variables. After $(d-1)$ iterations, we use $Z = \{X^{(0)},\ldots, X^{(d-1)}\}\in R^{d\times d}$ to construct a graph, whose adjacency matrix is, say, $(Z + Z')/2$.

In specific, can all random graphs, e.g., Erdos-Renyi graph and stochastic block model, be constructed in this way (ideally, with a relatively simple $\{f^{(t)}\}_{t=0}^\infty$)?