3
$\begingroup$

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$)?

Improve this question
$\endgroup$
9
  • $\begingroup$ I'm not quite sure what you mean. The correspondence between $X^{(t)}$ and $f$ and $\varepsilon$ is a bit unclear to me. But this seems to be the edge-exposure model, which is very important for a lot of applications. In particular, you can use this sort of model to cook up lots of useful martingales. Alon and Spencer has a good bit on this. For instance, see the sections on concentration of chromatic number. $\endgroup$
    – Pat Devlin
    Commented Nov 29, 2016 at 3:39
  • $\begingroup$ @PatDevlin Thanks a lot for the pointer! So basically $X^{(t)}$ corresponds to a column in the adjacency matrix (before post-processing), $f^{(t)}$ is the "generator" for the column-wise generation, and $\epsilon^{(t)}$ is the injected randomness. $\endgroup$
    – Minkov
    Commented Nov 29, 2016 at 4:33
  • $\begingroup$ Then in that case, if you're building the matrix one column at a time, this is the vertex-exposure model. $\endgroup$
    – Pat Devlin
    Commented Nov 29, 2016 at 5:20
  • $\begingroup$ @PatDevlin I checked out the vertex-exposure model. It seems very related. Thanks again for the pointer! $\endgroup$
    – Minkov
    Commented Dec 1, 2016 at 7:53
  • $\begingroup$ You can get Erdos-Renyi graphs by making $f^{(t)}$ ignore its first argument and generate a random 0/1 partial column by ignoring all but the first $t$ entries of a random $d$-vector $\epsilon^{(t)}$. $\endgroup$
    – Brendan McKay
    Commented Dec 3, 2016 at 6:16

0

Reset to default

You must log in to answer this question.