7
$\begingroup$

Consider the following stochastic process.

We begin with an undirected graph on $n$ vertices, exactly one of which is ''infected.'' Now at every time step, each infected node infects one of its non-infected neighbors uniformly at random. For example, if a given node has $3$ neighbors that are infected and $5$ that are not, then it infects exactly one of those latter $5$, each of which has probability $1/5$ of being the one chosen.

Now its clear that after $n-1$ steps every node becomes infected, since at every step at least one non-infected node becomes infected. However, I suspect that the infection actually spreads faster, because as the number of infected nodes grows, more and more non-infected nodes become infected at every stage.

My question: Is it actually true that every node is infected after $O(D)$ steps, where $D$ is the diameter of the graph?

2 Answers 2

6

Consider a tree of $n$ layers where each node at layer $n$ (up to $n-1$)has $n$ branches leading upward. The last node will be infected after $1+2+3 \ldots +(n-1)=\frac{n(n-1)}{2}$, but the diameter is $2n-2$

6

Consider a starlike graph of n+1 nodes in which every node except node A is adjacent to A and only to A.

If A is infected, exactly one of its neighbors becomes infected at each step until all are. So the number of steps until every node is infected is n, not O(D) since D = 2.

  • 0
    @Ross: No, you had the answer first. I only posted because I thought I could add something.2011-06-22