¿Cuánto tiempo tarda para cada nodo de un grafo a infectarse?

Question

Considere el siguiente proceso estocástico.

Comenzamos con un grafo no dirigido en $n$ vértices, exactamente uno de los cuales está "infectado". Ahora en cada paso de tiempo, cada nodo infectado infecta a uno de sus no-infectados vecinos uniformemente al azar. Por ejemplo, si un nodo dado ha $3$ a los vecinos que están infectados y $5$ que no lo son, entonces se infecta exactamente uno de los últimos $5$, cada uno de los cuales tiene probabilidad de $1/5$ de ser uno de los elegidos.

Ahora es claro que después de $n-1$ pasos cada nodo se convierte infectados, ya que en cada paso que al menos una no infectada nodo se infecta. Sin embargo, tengo la sospecha de que la infección realmente se propaga más rápido, porque a medida que el número de infectados nodos crece, más y más personas no infectadas nodos infectados en cada etapa.

Mi pregunta: ¿Es realmente cierto que cada nodo está infectado después de $O(D)$ pasos, donde $D$ es el diámetro de la gráfica?

Answer 1

Considerar un gráfico starlike de n + 1 nodos en que cada nodo excepto el nodo A es adyacente a un y sólo a la A.

Si A está infectado, exactamente uno de sus vecinos se infecta a cada paso hasta que todos se. Por lo que el número de pasos hasta que cada nodo está infectado es n, no O(D) desde D = 2.

Answer 2

Considere un árbol de $n$ capas, donde cada nodo capa $n$ (hasta $n-1$) tiene $n$ sucursales llevando hacia arriba. El último nodo se infectaron después de $1+2+3 \ldots +(n-1)=\frac{n(n-1)}{2}$, pero el diámetro es $2n-2$