The infection time of graphs (Q858307)

Consider a graph with \(n\) vertices and \(k\leq n\) particles performing \(k\) independent random walks on the graph. Initially, one particle is red and all the others are white, and each vertex of the graph has at most one particle. When a red particle meets one or more white particle(s) then the white one(s) turn(s) red. This is an infection rule and is a model for several real life phenomena, like the spread of a virus in a computer networks, information spreading (rumor, gossip) and mobile communication. For an initial distribution \(\varphi_k\) of the particles, let \(T_{\varphi_k}\) be the first time at which all particles are red. The infection time \(T_k\) is the worst expected value \(E(T_{\varphi_k}| \varphi_k)\) over all distributions \(\varphi_k\) such that each particle is assigned to a single vertex with probability 1. The authors study the infection time for various families of unweighted, undirected finite graphs. First of all, they prove the following upper bound (valid for all graphs): \(T_k\leq em^*(2+\log k)\), where \(m^*=\max_{i,j}M_{i,j}\), and \(M_{i,j}\) is the first time that two independent random walks on the graph meet if they start from positions \(i\) and \(j\) (that is, \(m^*\) is the expected meeting time). They also show that this bound is tight for a family of lollipop graphs. Then they give more tight bounds for two special classes of graphs: cliques and expander graphs. In the last part of the paper, the authors discuss several computer simulations that, in particular, show that their results for expander graphs are tight. A final conjecture is that good expanders have small infection time. Future work in this direction might lead to a characterization of expansion through infection time.