2
$\begingroup$

Short version: Consider the SI model of infectious disease spread on a random graph $G$ with a given degree sequence. Let $j$ be a vertex and let $i$ and $k$ be two of its neighbors. If $G$ contains no short cycles, then, conditioning on $j$ being susceptible at time $t$, it is reasonable to suspect that the states of $i$ and $k$ at time $t$ are close to being independent, since they only interact "at a long distance", as it were. Under what assumptions on the degree distribution of $G$ can this suspicion be made precise?

Long version, with details and definitions: (The derivation of the relevant quantities is a bit lengthy. The calculations given here follow Section 17.10 of M.E.J. Newman's Networks: An Introduction.) In the SI model of infectious diseases, members of a population can be in one of two states, "susceptible" and "infected". Once a member of the population is infected, it remains infected forever.

We consider this model on a random graph $G$ with a given degree sequence (more formally, a sequence of random graphs $G_n$ with a given asymptotic degree sequence). Each infected vertex $v$ infects its susceptible neighbors independently with rate $\beta$--that is, the probability that $v$ infects a susceptible neighbor $w$ at some point in the interval $[t, t + dt]$ is $\beta dt$.

Let $s_i(t)$ denote the indicator function for the event that $i$ is susceptible at time $t$, and let $x_i$ denote the indicator function for the event that $i$ is infected at time $t$. How does $\mathbb{E} s_i(t)$ change with $t$? Well, the expected number of infections that $i$ receives in a time interval $dt$ equals the number of infected neighbors that "fire" during the interval $dt$. Then we have $$\frac{d\mathbb{E} s_i(t)}{dt} = -\beta\sum_{j = 1}^n A_{ij} \mathbb{E} \bigl(s_i(t) x_j(t)\bigr),$$ where $A_{ij}$ denotes the corresponding entry of the adjacency matrix. The expression on the right-hand side does not tell us much, because we don't know the values of the $\mathbb{E} \bigl(s_i(t) x_j(t)\bigr)$. However, with some more thought, one can determine that (suppressing the dependence on $t$) $$\frac{d\mathbb{E} (s_i x_j)}{dt} = \beta\sum_{k \neq i} A_{jk} \mathbb{E} (s_i s_j x_k) - \beta\sum_{\ell \neq j} A_{i \ell} \mathbb{E} (x_{\ell} s_i x_j) - \beta \mathbb{E} (s_i x_j). \tag*{(1)}$$

My question is about computing, e.g., $$\mathbb{E} (s_i s_j x_k) = \mathbb{P}(s_i = 1, s_j = 1) \mathbb{P}(x_k = 1 \mid s_i = 1, s_j = 1). \tag*{(2)}$$ Here, the "moment closure" or "pair approximation" method says that if $G$ is close to being a tree near $i$, then, conditioning on $j$ being susceptible, the states of $i$ and $k$ are close to being independent, because the only interactions between them occur at a long range. (Note that $k$ is a neighbor of $j$, not of $i$.) Since random graphs with a given degree distribution are often locally tree-like (e.g., random $d$-regular graphs), this seems like a very plausible approximation. Then we have, e.g., $$\mathbb{P}(x_k = 1 \mid s_i = 1, s_j = 1) = \frac{\mathbb{E} (s_j x_k)}{\mathbb{E} s_j},$$ which reduces $(2)$ to a combination of one- and two-variable expectations. This, in turn, makes the system of differential equations $(1)$ solvable, albeit complicated.

Can this idea of "near independence" be made precise? If so, how? Under what conditions on the degree distribution of $G$ do we have, for example, that $$\mathbb{E}(s_i x_k) = \mathbb{E} s_i \mathbb{E} x_k + o(1),$$ and why?

$\endgroup$

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.