La idea de las pruebas grupales es un enfoque eficiente para la identificación de infecciones basado en la agrupación de muestras de prueba de un grupo de individuos, lo que resulta en una identificación con un menor número de pruebas que al probar individualmente a la población. En nuestro trabajo, proponemos un nuevo modelo de propagación de infecciones basado en un grafo de conexiones aleatorias que representa las conexiones entre n individuos. La infección se propaga a través de las conexiones entre individuos, lo que resulta en una estructura de formación de clústeres probabilística, así como en estados de infección no i.i.d. (correlacionados) para los individuos. Proponemos una clase de algoritmos de pruebas grupales muestreadas en dos pasos donde aprovechamos el modelo de propagación de infecciones probabilístico conocido. Investigamos las métricas asociadas con los algoritmos de pruebas grupales muestreadas en dos pasos. Para demostrar nuestros resultados, para árboles de formación de clústeres exponencialmente divididos que son analíticamente tratables, calculamos el número requerido de pruebas y el número esperado de clasificaciones erróneas en términos de los parámetros del sistema, e identificamos la compensación entre ellos. Para tales árboles de formación de clústeres exponencialmente divididos, para la construcción sin error, demostramos que el número requerido de pruebas es O(log2n). Así, para tales árboles de formación de clústeres, nuestro algoritmo supera cualquier prueba grupal no adaptativa sin error, algoritmo de división binaria y el algoritmo de división binaria generalizado de Hwang. Nuestros resultados implican que, al aprovechar la información probabilística sobre las conexiones de los individuos, las pruebas grupales pueden utilizarse para reducir significativamente el número de pruebas requeridas incluso cuando la tasa de infección es alta, contrastando con la creencia prevalente de que las pruebas grupales son útiles solo cuando la tasa de infección es baja.