Glosario

Seleccione una de las palabras clave de la izquierda ...

Gráficos y RedesGráficos en la vida cotidiana

Tiempo de leer: ~20 min

Hemos visto muchas aplicaciones diferentes de la teoría de grafos en los capítulos anteriores, aunque algunas de ellas fueron un poco artificiales. Sin embargo, resulta que los gráficos son la base de muchos objetos, conceptos y procesos en la vida cotidiana.

Internet, por ejemplo, es un vasto gráfico virtual. Cada vértice es una página web individual, y cada borde significa que hay un hipervínculo entre dos páginas. Tenga en cuenta que los enlaces solo van en una dirección, por lo que este gráfico está , y que este gráfico es muy, muy grande .

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

Los sitios web con más enlaces entrantes tienden a ser de mayor calidad y deben mostrarse en la parte superior de los resultados de búsqueda. Por ejemplo, cuando se busca "Londres", los sitios oficiales de información turística se muestran antes de pequeñas tiendas en Londres, o blogs de personas que viven en Londres. Esta idea simple de la teoría de gráficos, el algoritmo de rango de página , hizo que Google sea significativamente mejor que otros motores de búsqueda anteriores.

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

© LyonLabs, LLC and Barrett Lyon, 2014

Si bien los sitios web y los hipervínculos forman un gráfico virtual , también existe la red física de computadoras, servidores, enrutadores, líneas telefónicas y cables.

Cada vez que realiza una llamada telefónica o carga un sitio web, los operadores de red tienen que encontrar una manera de conectar el remitente y el receptor, sin exceder la capacidad de ningún cable o conexión individual. La teoría de gráficos y la probabilidad hacen posible garantizar un servicio confiable, por ejemplo al encontrar desvíos cuando una conexión particular está ocupada.

Los gráficos también juegan un papel importante en el transporte y la navegación. Todas las redes de vuelo, tren y metro forman gráficos, que pueden usarse al crear horarios eficientes. Uno de los gráficos más reconocibles es el mapa del metro de Londres:

Todas las carreteras y autopistas también forman una gran red, que es utilizada por los servicios de navegación como Google Maps al calcular la ruta más corta entre dos puntos dados.

En el futuro, los sistemas inteligentes de transporte reducirán la congestión y los accidentes al enrutar los automóviles de manera más eficiente, utilizando los datos de ubicación recopilados de los teléfonos inteligentes y los vehículos autónomos. Esto podría ahorrar millones de horas perdidas en la carretera cada año, reducir significativamente la contaminación y permitir que los servicios de emergencia viajen más rápido.

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

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

Los enlaces entre los átomos en las moléculas y las rejillas de cristal 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 diferentes componentes de circuitos eléctricos y chips de computadora forman una red.

La estructura gramatical de los idiomas se puede modelar mediante gráficos, por ejemplo, para crear algoritmos de traducción.

Los gráficos también tienen muchas aplicaciones en probabilidad , teoría de juegos y matemática financiera .

Redes sociales

Finalmente, pensemos en un ejemplo particularmente bueno de gráficos que existen en la vida cotidiana: las redes sociales. Aquí, los vértices representan y los bordes representan amistades, me gusta, suscripciones o seguidores.

Cuando dibujamos gráficos de redes sociales, podemos ver ciertos grupos de amigos en común, que pueden haber ido a la misma escuela o vivir en la misma ciudad. También podemos determinar la centralidad de las personas, que depende de qué tan bien conectado esté un vértice, y que puede ser una medida de la popularidad de una persona en las redes sociales.

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

Una pregunta emocionante ahora sería: si eliges dos usuarios aleatorios de Facebook, ¿cuántos “límites de amistad” necesitarías seguir para pasar de uno a otro? Por ejemplo, la distancia entre amigos es , la distancia entre amigos de amigos es , y así sucesivamente.

En 2016, Facebook realizó un estudio para determinar cómo sus usuarios están conectados entre sí. Descubrieron que, en promedio, está conectado a cualquier otra persona en Facebook a través de, como máximo, 3.57 personas más. ¡Y esto incluye celebridades, políticos o incluso realeza!

En otras palabras, si elige cualquiera de los miles de millones de usuarios de Facebook en todo el mundo, probablemente tendrán un amigo de un amigo que conozca a un amigo de uno de sus amigos. Decimos que hay 3.57 grados de separación .

Geographic visualisation of all Facebook friendships in 2010.

En 1929, cuando el autor húngaro Frigyes Karinthy propuso por primera vez la idea de "seis grados de separación", no había Internet ni redes sociales, pero el mundo ya había comenzado a estar más interconectado.

En 1967, Stanley Milgram realizó un primer experimento empírico, donde se pidió a 296 participantes que vivían en Nebraska y Kansas que entregaran una carta a una persona en particular que vivía en Boston, Massachusetts. Todos tuvieron que elegir un amigo para enviarle la carta, quien luego eligió a otro amigo. A cada paso, la carta se acercaba a Boston. Milgram descubrió que, en promedio, solo había 5.2 amigos intermedios, 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, viajes, Internet y tecnología, ciencia y mucho más.

Archie