¿Cómo encontrar el camino más corto en una red de la que no se conocen todas las conexiones, como Internet o las vías de las proteínas en el cuerpo? Los científicos han estado buscando la respuesta a esa pregunta durante décadas. Investigadores de TU Delft, entre otros, ahora han encontrado una solución para ciertas redes.
Encontrar la ruta más rápida en una red es un problema bien conocido que puedes resolver si conoces todos los nodos y conexiones. Una solución a esto llegó en 1959 en la forma de la Algoritmo de Dijkstra, desarrollado por el informático holandés Edsger Dijkstra. Este algoritmo se utiliza, por ejemplo, en sistemas de navegación.
«Pero tan pronto como no sabemos todo sobre la red, el problema del camino más corto rápidamente se vuelve muy difícil», dice el científico de redes. maxim kitsak, de TU Delft. Desarrolló con colegas un nuevo método que puede calcular el camino más corto entre dos nodos en ciertas redes. Esto resulta posible incluso si el 90 por ciento de las conexiones en la red están ocultas o si la red contiene enlaces falsos.
LEA TAMBIÉN
Las aplicaciones de entrenamiento mental carecen de respaldo científico
Muchas aplicaciones afirman que sus usuarios son más inteligentes. Estas aplicaciones de entrenamiento mental no solo son bastante aburridas, sino que su efecto en nuestro rendimiento es…
Confía en internet
Este método tiene una gran demanda. La mayoría de las redes a gran escala están incompletas. Tomemos como ejemplo las redes sociales. Durante la crisis de la corona, el gobierno intentó mapear los contactos sociales de las personas. Esa es una red incompleta, porque es imposible, e indeseable desde el punto de vista de la privacidad, conocer todos los contactos de todos.
«Otro ejemplo es Internet», dice Kitsak. «La gestión de esto está en gran medida en manos de empresas que se ocupan de parte de la red». Esas empresas no revelan mucha información. Además, los cambios ocurren cada pocos minutos.
Por el momento, Internet funciona sobre la base de la confianza. Los enrutadores, los nodos de Internet, les dicen a sus vecinos a qué otros nodos tienen líneas cortas. Los vecinos transmiten esto y queda claro a través de qué nodos puede comunicarse con alguien.
Kitzak: ‘Imagina: estoy en contacto con un gran estudiante de doctorado y te lo cuento. Luego puede compartir esa información con otros y decirles: si tiene un mensaje para este gran candidato a doctorado, hágamelo saber, se lo pasaré a Maksim y él se lo pasará a ese candidato a doctorado.’
En este escenario, debe confiar en que todos dicen la verdad y que nadie está enviando su correo electrónico confidencial más allá de una agencia de inteligencia o tabloide.
El camino más corto en Manhattan
El método desarrollado por Kitsak y sus colegas puede hacer que Internet sea más seguro al detectar y eliminar rutas de comunicación fraudulentas. Esto puede permitirnos evitar situaciones en las que el tráfico de Internet se redirige indeseablemente a través de Rusia o China, por ejemplo.
El método funciona de la siguiente manera: los investigadores primero buscan una representación geométrica de la red. Esta representación distribuye los nodos sobre un espacio geométrico. Dependiendo de la red, esto puede ser un ordinario (euclidiana) ser plano o algo complejo, como un hiperbólico disco de Poincaré. La distribución de los nodos en ese espacio representa sus distancias mutuas. Luego dibuja la línea más corta entre los dos nodos que desea conectar, los llamados geodésico. Si el espacio geométrico es un plano, entonces es una línea recta. Los nodos más cercanos a esa línea probablemente formen el camino más corto entre los dos puntos.
Este método demuestra que funciona bien, incluso si no conoce muchas conexiones entre los nodos. Kitsak y sus colegas pudieron encontrar las rutas más cortas en Internet incluso cuando hasta el 90 por ciento de las conexiones se cortaron al azar.
«Se puede comparar con encontrar el camino a un rascacielos en el Manhattan de Nueva York», dice Kitsak. Las calles allí forman un patrón de cuadrícula. Y si quieres caminar hasta el Empire State Building, por ejemplo, lo verás elevándose por encima de los demás edificios. Ahora puedes caminar fácilmente hasta ese edificio porque sabes cómo están dispuestas las calles. Llegas allí eligiendo siempre una calle que discurra lo más lejos posible en dirección al rascacielos.
No hay talla única para todos
“Nuestro trabajo no ofrece una solución única para todas las redes incompletas”, dice Kitsak. ‘Hacemos dos suposiciones sobre la red. La primera es que puedes hacer una representación geométrica de ella.’ Esto es posible con Internet, pero no es seguro que sea posible con todas las redes.
La segunda suposición es que hay aproximadamente el mismo número de conexiones faltantes en todas partes de la red, y si falta o no una conexión es completamente aleatorio. En realidad, ese es raramente el caso. Por ejemplo, las conexiones a Internet pueden cambiar localmente o desaparecer debido a eventos geopolíticos.
Kitsak: ‘Ahora vamos a averiguar cuáles son los límites de estas suposiciones. Y esperamos que el método siga funcionando si, por ejemplo, las conexiones no se distribuyen de manera completamente aleatoria y uniforme en la red”.