I consider a graph that changes randomly over (discrete) time denoted by $(G_t)_{t=0}^{\infty}$ where I call $G_0=(V_0, E_0)$, $V_0$ being the vertex and $E_0$ the edge set my initial condition where $\mathrm{card}(V_0)=n$.

Assuming that the dynamics preserve the vertex set and the number of edges, i.e., $V_t=V_0$ and $\mathrm{card}(E_t)=\mathrm{card}(E_0)=m$ for all $t$, and that $G_0$ is a $\mathcal{G}(n,m)$ graph can I say that $G_t$ at any time $t$ is also a $\mathcal{G}(n,m)$ graph and therefore apply results from theory of $\mathcal{G}(n,m)$ graphs? In particular, I would like to employ results on the largest connected component.

The dynamics itself consists of deleting and rewiring edges.

Right now I am torn between the fact that my dynamics give me a "trajectory" in $\mathcal{G}(n,m)$ and every $G_t$ could therefore be seen as a $\mathcal{G}(n,m)$ graph but $G_t$ is not just some random graph drawn from $\mathcal{G}(n,m)$ but the result of the dynamics started at $G_0$. I am not sure which one of the two is the right view on $G_t$.

Thanks in advance for your help!

  • 1
    $\begingroup$ It depends on how exactly you "delete" and "rewire" edges. For example: if $G_t$ is obtained from $G_{t-1}$ by deleting a randomly chosen edge and adding another randomly chosen edge, then $G_t \sim \mathcal G(n,m)$. If $G_t$ is obtained from $G_{t-1}$ by deleting an edge from a higher degree vertex and joining two random low-degree vertices instead, this introduces a bias. $\endgroup$ – Misha Lavrov Nov 30 '18 at 18:19
  • $\begingroup$ I color my vertices with two colors and delete edges that are incident to two vertices, say $i$ and $j$, with different colors. For the rewiring I pick uniformly one of the two vertices, say $i$, and draw uniformly from the vertices that are not adjacent to $i$. This will most likely introduce a bias, doesn't it? $\endgroup$ – Jfischer Dec 18 '18 at 6:52
  • $\begingroup$ It seems like if you keep doing this for long enough, you will only be left with edges between vertices of the same color, which is very unlike a random graph, so yes. $\endgroup$ – Misha Lavrov Dec 18 '18 at 6:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.