Bienvenido al Visualizador de Búsqueda en Redes con incertidumbre
Explora cómo los algoritmos de muestreo greedy identifican nodos críticos en grafos dirigidos acíclicos.
💡 Motivación
Durante el brote de COVID-19, la vigilancia de aguas servidas se convirtió en una herramienta crucial para detectar y monitorear la propagación del virus en comunidades. Sin embargo, las redes de alcantarillado son complejas y a menudo inciertas, lo que dificulta la identificación rápida de fuentes de infección. Limitado por recursos, es esencial desarrollar estrategias eficientes para muestrear estas redes y localizar nodos infectados con el menor número de exploraciones posibles, tanto en cantidad de muestras como en tiempo.
📰 Noticias y Contexto
Exitoso plan piloto en Chillán: Detectan presencia de COVID-19 en aguas servidas
En los laboratorios de la Universidad de Concepción se obtuvieron los primeros resultados positivos del análisis de aguas servidas en Chillán para la detección temprana de posibles focos de COVID-19.
Ver video completoInnovador proyecto que analizó aguas residuales mostró las variantes que más circulan en Chile, cómo es capaz de detener brotes y anticipar hasta en cinco días aparición de síntomas
Las aguas servidas que corren bajo nuestros pies contienen información importante que hoy permite detectar la presencia de Sars-CoV-2 en una zona determinada y dirigir la pesquisa con test PCR hacia ese sector adelántandose al brote. El objetivo final de la iniciativa es crear una red de laboratorios en el país, para hacer vigilancia activa de virus, bacterias, fármacos y drogas.
Leer noticia completa
¿Para qué sirve el monitoreo de aguas residuales?
Los análisis de aguas residuales aportan datos importantes sobre agentes patógenos. En Alemania, por ejemplo, se descubrió recientemente el virus de la polio gracias al monitoreo. ¿Por qué es un método eficaz?
Leer noticia completa
¿Qué es la Incertidumbre Estructural?
😶🌫️ Incertidumbre
En muchas redes reales, no estamos 100% seguros de si todas las conexiones están operativas en un momento dado.
Muchas de ellas están solo para raros casos de lluvias intensas o mantenimiento, y no siempre sabemos si están abiertas o cerradas.
Ejemplificamos este fenómeno en la siguiente visualización interactiva de la red de San Pedro de la Paz (SPPD). Donde las líneas rojas representan posibles conexiones adicioneles.
Haz clic en los botones para simular cómo la incertidumbre afecta la estructura de la red.
Búsqueda de infecciones
🎯 Objetivo
Una estrategia que minimice el número de días para detectar un brote en una red de alcantarillado, bajo un presupuesto limitado de exploraciones.
🧠 Asunciones
- La red se represenseta con un grafo dirigido $G = (V,E)$ con raíz en la planta de tratamiento de aguas servidas.
- Hay un solo nodo infectado.
- El presupuesto limita la cantidad de muestras $k$ que podemos hacer cada día.
Conceptualización
🤔 ¿Cómo se encuentra un nodo infectado?
- Al muestrear un nodo $v$, si el resultado es positivo, sabemos que el nodo infectado está en el subgrafo $J_v$ (todos los nodos que pasan estrictamente por $v$). Si el resultado es negativo, descartamos $J_v$ del espacio de búsqueda.
- El objetivo es maximizar la incertidumbre resuelta en cada muestreo, es decir, reducir el espacio de búsqueda a la mitad en cada ronda.
- Necesitamos selecciona nodos que cubran la mayor cantidad de nodos no cubiertos previamente, dentro de un corte ideal que no exceda $B$.
Ejemplo Conceptual
Visualiza la correspondencia entre la exploración del grafo y la toma de decisiones. Lo siguiente es un caso en el que se hacen muestras, y dependiendo de su resultado nos movemos por su árbol de desición.
Grafo de Búsqueda
Hay un nodo infectado que no sabemos dónde está.
Árbol de Decisión
¿Fluye la infección por este nodo?
Eficiencia de la búsqueda conceptual
La eficiencia de una búsqueda realizada con la idea anterior no demora más de:
Donde $\Delta$ es el grado máximo del grafo y $n$ el número de nodos. Pero se puede mejorar aún más usando un algoritmo greedy que minimice la profundidad del árbol de decisión.
Algoritmo Greedy
A continuación, se presente una visualización interactiva del algoritmo greedy propuesto para la selección de nodos a muestrear. Observa cómo se actualizan las variables internas y cómo se modifica el grafo a medida que avanzas en los pasos del algoritmo. Por el momento no nos preocupamos del cálculo de $B$, solo del funcionamiento del algoritmo greedy con un $B$ fijo (para más información, revisa Cálculo de $B$).
\begin{algorithm}
\caption{Greedy Sampling Algorithm}
\begin{algorithmic}
\INPUT A directed acyclic graph $G = (N,F)$ with root $r$, a natural number $k$ and a natural number $B$.
\OUTPUT A set $S$ of $k+1$ nodes to sample with $S \ni r$
\STATE $S = \{r\}$
\WHILE{$|S| \leq k+1$}
\STATE aux = -1
\STATE auxv = $-\infty$
\FOR{$v$ in $N \setminus S$}
\STATE $J = |J_v(G) \setminus \bigcup_{u \in (S \setminus \{r\})} J_u(G)|$
\IF{auxv $\leq J \leq B$}
\STATE aux = $v$
\STATE auxv = $J$
\ENDIF
\ENDFOR
\IF{aux $\neq -1$}
\STATE $S = S \cup \{\text{aux}\}$
\ELSE
\STATE break
\ENDIF
\ENDWHILE
\RETURN $S$
\end{algorithmic}
\end{algorithm}
🔍 Monitor de Variables
Resultados Experimentales
Evaluación del desempeño del algoritmo propuesto en redes de alcantarillado reales y sintéticas.
Distribución de Tiempos de Detección en SPPD
Experimento 1
💡 Interpretación de los datos
La figura muestra la distribución del número de días necesarios para detectar el brote en la red completa de San Pedro de la Paz. Se comparan tres métricas (Media, Percentil 90 y Máximo) variando el número de muestras ($k=1, 5, 10$).
- Reducción de Tiempos: Se observa una reducción considerable en el número de días necesarios para hallar el nodo infectados mientras mayor es el número de muestras.
- Reducción de Varianza: Al aumentar el número de muestras a 10, la dispersión de los días disminuye significativamente comparado con una sola muestra.
- Peores casos: En la salud pública nos interesa mucho el manejo del peor caso. Aquí, al aumentar $k$, el máximo número de días para detectar el brote disminuye drásticamente, pasando de $\ge 70$ con $k=1$, a $\le 10$ con $k=10$.
Comparación de la eficiencia con y sin incertidumbre en SPPD
Experimento 2
💡 Interpretación de los datos
La figura muestra la comparación del desempeño del algoritmo greedy en la red de San Pedro de la Paz bajo dos escenarios: con incertidumbre estructural (5% de arcos extra) y sin incertidumbre. Se presentan tres métricas (Media, Percentil 90 y Máximo) con un número de muestras fijo ($k=5$).
- Medias similares: Se observa que las medias de los tiempos de detección son bastante similares entre ambos escenarios (diferencia de 0.04 días), indicando que el algoritmo mantiene su eficiencia promedio incluso con incertidumbre.
- Variación del peor caso: El peor caso (máximo) muestra una diferencia más notable, la media varía aproximadamente en 2.5 días. Esto sugiere que la incertidumbre puede afectar la robustez del algoritmo en situaciones extremas.
Diferencia absoluta para una red aleatoria con y sin incertidumbre
Experimento 3
💡 Interpretación de los datos
La figura muestra la diferencia absoluta en días para detectar el nodo infectado en una red aleatoria con 4000 nodos y varios niveles de incertidumbre (5, 10 y 20%). Se presentan tres métricas (Media, Percentil 90 y Máximo) con un número de muestras fijo ($k=5$).
- Robustez: De forma similar al experimento anterior, las medias de los tiempos de detección muestran diferencias pequeñas entre los escenarios con y sin incertidumbre. Para 5% de incertidumbre, la diferencia de medias es solo de 0.33 días, es decir, solo unas cuantas horas. Sugiriendo que el algoritmo es robusto en promedio.
- Tope en la incertidumbre: Al aumentar la incertidumbre estructural, las estadísticas no empeoran significativamente. El cambio entre 10 y 20% de incertidumbre es mínimo, indicando que el algoritmo puede manejar niveles moderados de incertidumbre sin una degradación sustancial en el desempeño.
- El algoritmo funciona: Estos resultados proporcionan evidencia suficiente de que el algoritmo greedy propuesto es efectivo incluso en presencia de incertidumbre estructural en la red, muy cercano a como si fuera una red sin incertidumbre.
Referencias
Identifying outbreaks in sewer networks: An adaptive sampling scheme under network’s uncertainty
Searching for infections: algorithms for multiple sampling on trees and planar graphs
Complexity, lower bounds, and algorithms for searching infected nodes in uncertain trees
Covid-Sewage-Search
Cálculo Dinámico de $B$
Estrategia de limitación del espacio de búsqueda para garantizar eficiencia logarítmica.
📉 El Problema de un límite superior
Si elegimos un $B$ muy alto, el algoritmo selecciona nodos que cubren casi toda la red, descartando muy pocos candidatos en cada iteración en caso de que la infección se encuentre lejos de la raíz. Si $B$ es muy bajo, la cobertura es insuficiente para avanzar rápido.
⚖️ La Solución: Bisección
Buscamos reducir el espacio de candidatos realizando una búsqueda binaria sobre los posibles valores de $B$. Esto garantiza que en cada ronda se descarte aproximadamente la mitad de los nodos restantes, optimizando la eficiencia de la búsqueda.
Pseudocódigo para B
\begin{algorithm}
\caption{Cálculo Dinámico de B}
\begin{algorithmic}
\INPUT Grafo $G = (N,F)$ dirigido acíclico con raíz $r$ de los candidatos no descartados para una ronda dada.
\OUTPUT Mejor $B$ para la ronda actual
\STATE $l = 0$
\STATE $r = |N|$
\WHILE{$l < r$}
\STATE $mid = \lfloor (l + r) / 2 \rfloor$
\STATE Ejecutar Greedy con $B = mid$ para obtener conjunto $S$
\IF{$|I_r(G) \setminus (\bigcup_{u \in S} J_u(G))| \leq mid$}
\STATE $r = mid$
\ELSE
\STATE $l = mid + 1$
\ENDIF
\ENDWHILE
\STATE $B = l$
\RETURN $B$
\end{algorithmic}
\end{algorithm}
Nota: Es posible fijar $B = |N|/2$, para simplificar la implementación del algoritmo. Sin embargo, el enfoque de bisección encuentra el valor óptimo para cada ronda, mejorando la eficiencia en cada paso considerablemente.
Trabajo Futuro
Adaptación a múltiples nodos infectados
Actualmente, el algoritmo asume que sólo hay un nodo infectado. Una extensión natural es considerar múltiples nodos infectados simultáneamente. Esto requeriría adaptar la estrategia de muestreo para identificar todas las fuentes de infección en la red, lo que conlleva desafíos adicionales en la optimización del presupuesto de muestreo.
Adaptación a infecciones dinámicas
En escenarios reales, las infecciones pueden propagarse y cambiar con el tiempo. La infeccion puede moverse a otro nodo o desaparecer por completo, lo que requiere un enfoque dinámico para la detección. Adaptar el algoritmo para manejar infecciones dinámicas implicaría desarrollar estrategias de muestreo que consideren la evolución temporal de la infección en la red.
Ruido de las muestras
Una de las asunciones del modelo actual es que las muestras son perfectas, es decir, que no hay falsos positivos ni falsos negativos, por lo que las muestras siempre son confiables. La física/biología del problema puede introducir ruido en las muestras, lo que afectaría la precisión de la detección. Incorporar modelos de ruido en las muestras y adaptar el algoritmo para manejar esta incertidumbre adicional es otro gran paso para hacer el modelo más realista y aplicable a situaciones del mundo real.
