Grafos y RedesGrafos en la Vida Cotidiana

A lo largo de este curso, hemos visto muchas aplicaciones de la teoría de grafos, aunque algunas de ellas fueran algo artificiales. Sin embargo, resulta que los grafos están en el corazón de muchos objetos y conceptos cotidianos.

Internet, por ejemplo, es un inmenso grafo virtual. Cada vértice es una página web individual, y cada arista significa que hay un hipervínculo entre dos páginas. Tenga en cuenta que los enlaces sólo van en una dirección. Por lo tanto, este gráfico es dirigido-multilineado y es muy, muy grande.

Algunos sitios web, como Wikipedia o Facebook, contienen muchos enlaces entrantes, mientras que muchos sitios web más pequeños pueden contener muy pocos enlaces entrantes. Este es el concepto subyacente utilizado por Google para ordenar los resultados de búsqueda.

Los sitios web con más enlaces entrantes tienden a ser de mayor calidad y deberían aparecer en la parte superior de los resultados de búsqueda. Por ejemplo, al buscar «Londres», los sitios oficiales de información turística aparecen antes que las pequeñas tiendas londinenses o los blogs de personas que viven en Londres. Esta simple idea de la teoría de los grafos, el algoritmo Page Rank, ha hecho que Google sea significativamente mejor que otros motores de búsqueda.

Internet es la mayor red jamás creada por la humanidad. Esta imagen muestra una proporción muy pequeña de todos los servidores conectados a Internet:

© LyonLabs, LLC y Barrett Lyon, 2014

Mientras que los sitios web y los hipervínculos forman un gráfico virtual, también existe la red física, que incluye ordenadores, servidores, routers, líneas telefónicas y cables.

Cada vez que se realiza una llamada o se carga un sitio web, los operadores de red deben encontrar la forma de conectar al emisor y al receptor, sin superar la capacidad de cada cable o conexión. La teoría de los grafos y la probabilidad ayudan a garantizar un servicio fiable, por ejemplo, encontrando desvíos cuando una determinada conexión está ocupada.

Los grafos también desempeñan un papel importante en el transporte y la navegación. Todas las redes de vuelos, trenes y metros forman gráficos que pueden utilizarse para crear horarios eficaces. Uno de los gráficos más reconocibles es el mapa del metro de Londres:

Todas las carreteras y autopistas forman también una amplia red, que es utilizada por servicios de navegación como Google Maps para elaborar la ruta más corta entre dos puntos determinados.

En el futuro, los sistemas de transporte inteligentes reducirán la congestión y los accidentes al dirigir los coches de forma más eficiente, utilizando los datos de localización recogidos de los smartphones y los coches autónomos. Esto ahorraría millones de horas perdidas en la carretera cada año, reduciría significativamente la contaminación y permitiría a los servicios de emergencia viajar más rápido.

Esta imagen muestra la red de vuelos de las aerolíneas comerciales en el norte de Europa.

Hay otros innumerables gráficos en la ciencia, la ingeniería o la vida cotidiana:

Los enlaces entre los átomos de las moléculas y las rejillas de los cristales forman un gráfico.

La propagación de enfermedades y epidemias se puede modelar utilizando una red.

En Biología, los árboles evolutivos que muestran la ascendencia de las especies forman un gráfico.

Los distintos componentes de los circuitos eléctricos y los chips de ordenador forman una red.

La estructura gramatical de las lenguas puede modelarse mediante grafos, por ejemplo para crear algoritmos de traducción.

Los grafos también tienen muchas aplicaciones en probabilidad, teoría de juegos y matemáticas financieras.

Redes sociales

Por último, pensemos en un ejemplo especialmente interesante de grafos existentes en la vida cotidiana: las redes sociales. Aquí, los vértices representan peoplefriendsnetworks y las aristas representan amistades, likes, suscripciones o seguidores.

Cuando empezamos a dibujar gráficos en las redes sociales, podemos ver claramente ciertos grupos de amigos comunes, que pueden haber ido al mismo colegio o vivir en la misma ciudad. También podemos determinar la centralidad de una persona, que depende de lo conectado que esté un top y puede ser un indicador de la popularidad de una persona en las redes sociales.

En 2014, Facebook tenía 1.400 millones de usuarios activos y más de 200.000 millones de amistades. La mitad de los usuarios de Facebook tienen más de 200 amigos, y como la mayoría de nuestros amigos tienen el mismo número de amigos, podríamos tener fácilmente decenas de miles de amigos de amigos.

Ahora una pregunta apasionante sería: si eliges dos usuarios de Facebook al azar, ¿cuántos «enlaces de amistad» tienes que seguir para llegar de uno a otro? Por ejemplo, la distancia entre amigos es , la distancia entre amigos de amigos es , etc.

Según un estudio realizado por Facebook en 2016, estás conectado de media con cualquier persona en Facebook a través de un máximo de 3,57 personas: decimos que hay 3,57 grados de separación.

En otras palabras, si eliges a cualquiera de los miles de millones de usuarios de Facebook en todo el mundo, tendrán un amigo de un amigo que conoce a un amigo de un amigo tuyo. Y eso incluye a los famosos, los políticos o la realeza…

Visualización geográfica de todas las amistades de Facebook en 2010.

En 1929, cuando el autor húngaro Frigyes Karinthy propuso por primera vez la idea de los «seis grados de separación», Internet y las redes sociales no existían, pero el mundo ya había empezado a estar más interconectado.

En 1967, Stanley Milgram realizó un experimento empírico temprano en el que se pidió a 296 participantes de Nebraska y Kansas que entregaran una carta a alguien que vivía en Boston, Massachusetts. Todos tenían que elegir a un amigo para enviarle la carta, que a su vez elegía a otro amigo. A cada paso, la carta se acercaba más a Boston. Milgram descubrió que sólo había una media de 5,2 amigos intermedios, es decir, 5,2 grados de separación.

Hoy en día, cada uno de nosotros forma parte de innumerables gráficos invisibles, que subyacen a nuestras interacciones sociales, a los viajes, a Internet y a la tecnología, a la ciencia y a mucho más.

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *