# What is a stochastic graph?

Consider a population of $N(t)$ individuals, each of which are either infected with Disease X or not. On day $t \in \mathbb N$, individual $i$ has probability $\beta_{ij}(t) \in [0, 1]$ of infecting individual $j$ with Disease X. Besides, individual $i$ was a probability $c_i(t)$ of death, which depends on the age of $i$ and his state of infection. New healthy individuals enter into the population at a rate $\psi(t)$.

This came up as a proposed model for studying the spread of HIV when I was at the San Diego State REU last summer. We considered drawing a graph whose nodes represent individuals, such that an edge $(i,j)$ existed if individual $i$ was infected with HIV and in sexual contact with individual $j$.

We never went through with this model, for lack of time (and because we feared that if $N(t)$ was large enough to be realistic, computation time on MATLAB would become rather intractable for our resources); we were also unsure of how to prove theoretical results about such a model, such as the basic reproduction number $\mathcal R_0$ (defined to be the expected number of new infections from infected individual $i$ when $i$ is introduced to an otherwise perfectly susceptible population) and the expected prevalence, defined to be the expected number of infected individuals $I(t)$ divided by $N(t)$. I am not familiar with work on problems such as this, but let me record a few prospective definitions for my own amusement.

Let $T$ be an index set $\ni 0$ (which we shall assume $\subseteq \mathbb N$ for simplicity) and let $\Sigma,\Phi,\Psi$ be probability spaces.

Let’s say that a graph $G = (V, E)$ (whose vertices are indexed by $\mathbb N$) is decorated by $(\Sigma,\Phi,\Psi)$ if for the graph $G$, each node $i \in V$ and each edge $(i,j) \in E$ we associate random variables $X: \Sigma \to \mathbb R$, $X_i: \Phi: \mathbb R$, $X_{ij}: \Psi \to \mathbb R$.

Let $\Omega = \Sigma \times \Phi^{\mathbb N} \times \Psi^{\mathbb N^2}$, the product taken in the sense of measure spaces. Then a decoration is nothing more than a random variable $\Omega \to \mathbb R$. We interpret decorations as referring to the variables $\beta_{ij}, c_i, \psi$, etc. described above.

Let $\mathcal{RG}_{\Sigma,\Phi,\Psi}$ be the category of random graphs which have been decorated by $(\Sigma,\Phi,\Psi)$.

A map $\mathbf G: T \to \text{Hom}(\Omega,\mathcal{RG}_{\Sigma,\Phi,\Psi})$ is a stochastic graph if $\mathbf G(0)$ is deterministic (i.e. there is a fixed graph $\mathbf G_0$, which we call the initial data, such that for each $\omega \in \Omega$ $\mathbf G(0)(\omega) = \mathbf G_0$ almost surely).

We interpret a map $\Omega \to \mathcal{RG}_{\Sigma,\Phi,\Psi}$ as an assignment which takes the decoration $\omega_t$ of $\mathbf G(t)(\omega_{t-1})$ and returns the random graph $\mathbf G(t+1)(\omega_t)$ (so that at time $t+1$, the random graph is “parametrized by the decorations of time $t$“).

As it is, it seems like I’ve written down a very broad definition, and I’m not sure if it’s actually useful. Indeed, I’m not too sure how to restrict this definition to particularly useful cases. It’ll be an interesting problem to keep in the back of my head, until I grow bored of it or find some literature on the matter.