La teoría de grafos ayudó a desinfectar Londres

La teoría de grafos ayudó a los británicos a ser menos apestosos

Este es el segundo de una serie de artículos que explican los principios de la teoría de grafos para quienes pueden usarlo en un contexto de ciencia de datos. El primer artículo, que se centra en los orígenes de la teoría de grafos y las propiedades básicas de los grafos, se puede encontrar aquí.

Keith McNulty | Towards Data Science


Una mañana de julio a mediados del siglo XIX, la gente de Londres se despertó con un hedor repugnante y retorcido. No podían salir de sus casas sin estar enfermos. Los más acomodados se ataban los pañuelos con perfume y caminaban cubriéndose permanentemente la cara. Muchos de los pobres abandonaron la ciudad para buscar trabajo en el campo porque simplemente no podían soportarlo. Fue sin duda el incidente más oloroso de la historia británica.

Fue el comienzo de lo que se conoció como la Gran Peste de 1858. El río Támesis, lleno hasta el tope de siglos de desechos humanos que habían sido vertidos directamente del sistema de alcantarillado de madera medieval, finalmente se estaba vengando. El lavado en las orillas del río, el lodo plagado de cólera se deleitaba con las temperaturas inusualmente cálidas del verano y formaba un hedor miasmático que era ineludible por millas.

La Corporación de la Ciudad de Londres, desconocida en ese momento por ser particularmente proactiva en materia de salud pública, se dio cuenta de que ya era suficiente e invitó a enviar propuestas para el diseño de un nuevo plan de alcantarillado para la ciudad. El hombre cuyos planes fueron aceptados, Joseph Bazalgette, ahora es considerado uno de los principales héroes cívicos del pasado de Londres. Ingeniero civil talentoso, supervisó un proyecto monumental de obras públicas que transformó los niveles de higiene y la calidad de vida en Londres. La red de alcantarillado de Bazalgette es ampliamente considerada como el primer paso en la creación de la ciudad moderna de hoy, así como el comienzo del fin del cólera en Londres.

La Gran Peste de 1858 se resolvió con la ayuda de la teoría de grafos.

La red de alcantarillado de Bazalgette seguía siendo fuerte, llevando los desechos de millones de personas hacia el este a las instalaciones de procesamiento hacia la desembocadura del Támesis. Como proyecto de ingeniería, fue un ejemplo asombroso de esfuerzo humano: 22,000 kilómetros de alcantarillas, 318 millones de ladrillos, 2,7 millones de metros cúbicos de tierra excavada.

Bazalgette era conocido por lo duro que trabajaba. No dejó piedra sin remover al hacer este esfuerzo masivo a prueba de futuro. La gravedad y la pendiente de la red para garantizar el flujo del agua, los diámetros de los túneles, todos eran detalles que él obsesionaba. Pero hubo dos preguntas que fueron cruciales de responder desde el principio para hacer el proyecto manejable y sostenible: primero, ¿cómo minimizamos la ruta de alcantarillado entre dos puntos cualquiera de la red y segundo, cuáles son los puntos de conexión más importantes?

La hazaña de ingeniería de Bazalgette es un ejemplo de algunos de los primeros usos del campo emergente de la teoría de grafos e ilustra la importancia de dos conceptos que observamos todo el tiempo hoy en relación con las redes: la distancia entre vértices y la importancia de los vértices.


 

Medición de distancia en un grafo

La distancia es un concepto bastante simple en teoría de grafos, pero extremadamente útil en la práctica. Recuerde del artículo anterior de esta serie que un grafo consiste en un conjunto de vértices y un conjunto de aristas que vinculan pares de vértices. Dado dos vértices, la distancia entre ellos se define como el número de aristas en el camino más corto entre ellos. Esto también se denomina a veces "distancia geodésica" y, por convención, se describe como "infinito" si no existe una ruta entre los vértices. Por ejemplo, en el grafo simple anterior, la distancia entre el vértice 2 y el vértice 6 es 3 (hay dos caminos de esta longitud que pueden llevarlo allí).

La distancia es un concepto extremadamente útil porque a menudo querremos optimizarlo. Minimizar la distancia es un requisito extremadamente común en redes complejas para fines de ingeniería. En el estudio de las personas, la distancia mínima también es una cuestión de interés común. La cuestión de los seis grados de separación, que sostiene que dos personas en el mundo se pueden conectar entre sí por un máximo de seis vértices intermedios o siete bordes, es una cuestión de distancia mínima en una red de grafos. Estudios recientes en Facebook muestran que la distancia mínima promedio entre individuos en esa red es 4.57.

Pero la distancia máxima también puede ser de interés, porque implica desconocimiento y diferencia. Por ejemplo, puede ser posible utilizar ciertos datos de la compañía para desarrollar un grafo que represente la colaboración anterior entre los empleados. Luego, en eventos de la compañía en los que organiza personas en grupos de discusión, si desea maximizar la formación de nuevas conexiones y una diversidad de puntos de vista, puede hacer preguntas como: ¿cómo dividimos estas 100 personas en diez grupos de diez? , para que estos grupos tengan la distancia promedio máxima y, por lo tanto, ¿es menos probable que hayan trabajado entre ellos antes? Utilizada de esta manera, la teoría de grafos puede tener un impacto significativo en la experiencia de las personas dentro de una organización.

Midiendo la importancia de los vértices en un grafo

En cualquier grafo, algunos nodos son más importantes. En la red de alcantarillado de Bazalgette, por ejemplo, habrá algunos cruces que requieren una mayor supervisión porque cualquier falla o fuga tendrá un mayor impacto en toda la red. Del mismo modo, en una red de personas, ciertas personas tienen una mayor influencia debido a su posicionamiento y conectividad en relación con otros en la red.

Una medida simple de importancia es la valencia de un vértice. Ese es el número de bordes diferentes que se conectan al vértice. En Facebook, por ejemplo, su valencia es la cantidad de conexiones que tiene. Pero eso no comprende completamente el concepto de influencia o importancia, ¿verdad? No todos los que tienen una gran cantidad de conexiones están jugando un papel realmente importante en la red.

En mi experiencia, la mejor medida de importancia en una red es la centralidad de la intermediación. En pocas palabras, la centralidad de intersección de un vértice dado es el número de veces que se ve que el vértice está en el camino más corto entre los otros dos vértices de la red. Los vértices con altos grados de centralidad intermedia influyen en la difusión de la información en mayor medida, y su pérdida de la red tiende a tener un impacto mucho más significativo en su conectividad general. En el grafo anterior, los vértices rojos tienen el menor grado de centralidad de intermediación, mientras que los vértices azules tienen el mayor.

Comprender la centralidad de la intermediación puede ser muy importante en las redes de personas. Puede ayudar a identificar en qué personas invertir para garantizar que un determinado mensaje se difunda lo más ampliamente posible. Puede ayudar a que los nuevos miembros de una red estén más conectados mediante presentaciones a las personas adecuadas. Puede ayudar a determinar cuánta preocupación debería tener con respecto a la pérdida de un individuo de la red y su posible impacto en otros.

La centralidad de la interconexión es complicada de medir porque necesitas calcular las rutas entre todos los pares de vértices en una red. Para redes grandes, esto puede ser altamente computacionalmente intensivo. Sin embargo, existen excelentes paquetes de ciencia de datos para calcular las características de la red, incluida la centralidad de intersección. En el ecosistema R, en el que trabajo, el igraphpackage es particularmente útil.