A random walk model for infection on graphs: spread of epidemics \& rumours with mobile agents (Q633812): Difference between revisions

This paper deals with the spread of viral epidemics in environments where carriers are moving around. Somewhat more precisely, the model is as follows. There is a finite connected undirected graph \(G=(V,E)\) on which individuals perform independent random walks in continuous time. The rate transition matrix of the random walk is \(Q\), with \(q_{i,j}>0\) whenever \(i-j\) is an edge of \(G\). The infection can pass from an infected to a susceptible individual only if they are both at the same vertex. The probability that the virus will be passed over a time interval of length \(\tau\) is \(1-\exp(-\beta \tau)\) where \(\beta>0\) is a parameter called the infection rate. The focus is on a particular susceptible individual and the question is about the probability they become infected by time \(t\). The special case of a complete graph was studied by \textit{N. Datta} and \textit{T.C. Dorla} [J. Appl. Probab. 41, No. 4, 1008--1021 (2004; Zbl 1068.60070)]: here a more general class of graphs is considered. In more detail, it is assumed that the random walk is reversible. Two independent walkers \((X_{t})\) and \((Y_{t})\) are cosidered and the coincidence time up to time \(t\), \(\tau(t)\), is examined, defined to be \(\int_{s=0}^{t}I_{X_{s}=Y_{s}}ds\), where \(I_{A}\) denotes the indicator variable of the event \(A\). Thus \(\tau(t)\) is the total time up to time \(t\) during which the walkers are at the same vertex. The main focus is on \(\mathbb{E}(\tau(t))\). The main results are that for regular graphs on \(n\) nodes (including complete graphs), \(\mathbb{E}(\tau(t))=t/n\). If the graph is an Erdős-Rényi random graph \(G(n,p)\) conditioned to be connected and to have \(np\geq c\log(n)\) for some \(c>1\), again \(\mathbb{E}(\tau(t))\sim t/n\). A contrasting case is a power-law graph of the \textit{F. Chung} and \textit{L. Lu} kind [Internet Math. 1, No. 1, 91--114 (2003; Zbl 1065.05084)], where each vertex \(v\) has a positive weight \(w_{v}\) and the probability that each edge \(uv\) is present is \(w_{u}w_{v}/\sum_{x\in V}w_{x}\) (it is insisted that \(\sum_{x\in V}w_{x}\geq \max_{i} w_{i}^{2}\) to make this a probability distribution) and \[ w_{i}=m(1+i/i_{0})^{-1/(\gamma-1)},\quad \text{where}\;i_{0}=n(d\gamma-2)/m(\gamma-1))^{\gamma-1}. \] Here \(d\) is the average degree, \(m\) is the maximum degree and \(\gamma>2\) is the exponent of the weight distribution, and some further assumptions on these parameters are made. The result in this case is that now \(n\mathbb{E}(\tau(t))/t\) is asymptotically \(c\) if \(\gamma>3\), \(c\log(m)\) if \(\gamma=3\) and \(c(m.d)^{3-\gamma}\) if \(2<\gamma<3\). Here \(c>0\) is a constant that may depend on \(\gamma\) but not on \(n\). The proof for regular graphs is rather straightforward, linking the expectation of \(\tau(t)\) to the stationary distribution of the random walk. Otherwise, the basic strategy is to consider \(D\), the sum of the degrees, and \(D_{2}=\sum_{v\in V}d(v)(d(v)-1)\). The first and second moments of these two variables are obtained, which allows to use Chebychev to show that they are concentrated, and thus an estimate of the concentration time which holds whp (i.e., with probability tending to 1 with \(n\)) is obtained. For \(G(n,p)\), this leads to \(\mathbb{E}(D)=n^{2}p\) and the variance \(V(D)\sim 2n^{2}p(1-p)\). Similarly, with some more computations, it leads to a result for the power-law graph. The case of regular graphs is discussed in more detail.