Viral Processes by Random Walks on Random Regular Graphs

Abdullah, Mohammed; Cooper, Colin; Draief, Moez

We study the SIR epidemic model with infections carried by k particles making independent random walks on a random regular graph. We give a edge-weighted graph reduction of the dynamics of the process that allows us to apply standard results of Erdős–Renyi random graphs on the particle set. In particular, we show how the parameters of the model produce two phase transitions: In the subcritical regime, O(ln k) particles are infected. In the supercritical regime, for a constant C determined by the parameters of the model, Ck get infected with probability C, and O(ln k) get infected with probability (1 − C). Finally, there is a regime in which all k particles are infected. Furthermore, the edge weights give information about when a particle becomes infected. We demonstrate how this can be exploited to determine the completion time of the process by applying a result of Janson on randomly edge weighted graphs.