Wait time to grid network disconnection with failing edges

Question

Let $G_n$ be an $n \times n$ planar toroidal grid graph, with each node connected to its four neighbors, with the top row connected to the bottom, and the right column connected to the left. Suppose that, within each unit of time, each edge "breaks" for a randomly placed time interval lasting $\delta \lt 1$; perhaps $\delta \ll 1$ could be assumed. The edge-failures are independent of one another. Let $G_n(t)$ be the graph at time $t$, with, in general, several edges missing.

Q. I would like to know the expected duration $T$ that $G_n(t)$ will remain connected for all $t < T$, i.e., the wait time to the first disconnection of one or more nodes from the remainder.

Although disconnection is likely to be dominated by the probability of single-node isolation, it seems difficult to capture all the different ways that $G_n$ could become disconnected. Below, the three shaded nodes are disconnected by $8$ missing edges.

---

     

---

One could of course ask the same question for grid graphs based on $\mathbb{Z}^d$ rather than $\mathbb{Z}^2$ as above. It seems likely this has been studied for network robustness. Thanks!

Answer 1

This is an approximation of the answer. The main message is that, indeed, the probability of disconnection is dominated by isolated vertices.

I will assume that $\delta=1/m$, for some large positive integer $m$. I will also assume a discrete model, where in each basic interval $[i/m, (i+1)/m]$, every edge breaks independently with probability $p=\delta=1/m$.

Now I estimate the probability $q$ that at one basic interval, the graph gets disconnected.

Edit: According to the comments below, a disconnected subgraph of the torus grid has a component with at most two boundary components. Moreover, the boundary is either a contractible curve, in which case the component is shaped like a polyomino, or, the boundary consist of two parallel noncontractible curves, each of lenght at least $n$.

For every $k$, there are at most $3^k$ fixed polyominoes with perimeter of length $k$, and each can be positioned in $n^2$ ways. Also, every polyomino has perimeter of length at least $4$. Similarly, up to translation, there are at most $3^k$ noncontractible curves of length $k$, and a pair of such curves may be placed in at most $n^4$ different ways. Therefore,

$$q\le n^2\sum_{k=4}^{2n^2}3^kp^k + n^4\sum_{k=2n}^{2n^2}3^kp^k \le n^2 (3p)^4/(1-3p) + n^4 (3p)^{2n}/(1-3p).$$ If we assume that $p=o(1)$, then for $n$ sufficiently large, we have $q\le n^2 \cdot 82p^4$; the contribution of noncontractible separators is exponentially small.

Now we may estimate the expected time when the graph is connected as follows: $$T\ge\frac{1}{m}\sum_{i=1}^{\infty}i(1-q)^i=p\frac{1-q}{q^2}\ge\frac{1-q}{82^2n^4p^7}.$$

If $q$ is very small, that is, if $p\le c/n^2$ for a very small constant $c$, then we may write $$T\ge\frac{1}{6725n^4p^7}\ge\frac{n^{10}}{6725c^7}.$$

For the lower bound on $q$, we may consider $n^2/2$ independent vertices (if $n$ is even). Each gets separated with probability $p^4$, so $$q\ge 1-(1-p^4)^{n^2/2}\ge 1-e^{-n^2p^4/2}\ge n^2p^4/4$$ for $n$ sufficiently large.

If we still assume that $p\le c/n^2$, then $$T\le\frac{p}{q^2}\le\frac{16}{n^4p^7}\le \frac{16n^{10}}{c^7}.$$

Answer 2

Instead of answering the question, I will suggest some modifications that should make the model easier to analyze.

I will denote the number of vertices as v, and the number of edges as dv for the d-dimensional torus. Let us discretize time and assume that edge failure occurs from k/q to (k+1)/q, or at f-many such intervals, per unit time, where we have integers f,k and q with 0 less than f and k and both less than q. I set f=1 and let others deal with larger values of f. k is actually uniformly distributed feom the set 0,1,...,q-1.

The second change is to analyze only small components disconnecting. According to this model, only dv/q edges are missing at any time, (with some small variation which you can tune with the choice of probability distribution) and the question now becomes : how likely does this set contain a small disconnecting set of edges?

If b is the number of edges in a disconnecting set (so b is at least 2d), the chance that all of them become disconnected in a particular second is q^{1-b}. We can treat the O(v^j) many such configurations as independent, where for small values of b j is 1. Thus if v is larger than q^{b-1}, disconnection is very likely to occur.

In this model, disconnection is roughly proportional to v and to 1/q to an appropriate power. The likelihood of a large component disconnecting before a small component is small, and will likely not affect mean time to disconnection.