De dónde viene todo esto …

El escritor húngaro  Frigyes Karinthy publicó en 1929 un volumen de relatos cortos con el título «Everything is Different», entre los cuales se encuentra uno titulado «Eslabones». En él, uno de los personajes, alentado por la idea de que, debido a la rapidez de las comunicaciones de la época, el mundo se ha vuelto más pequeño, propone a los demás participar en un juego: les pide que elijan aleatoriamente un individuo del millón y medio de millones de habitantes de la Tierra y apuesta a que, usando no más de cinco personas intermedias, será capaz de contactar con él.

Posiblemente fue esta idea la que dio origen al concepto moderno de los seis grados de separación y, por extension, a los estudios sobre redes sociales.

Por otro lado, como vimos en la anterior entrada, los grafos constituyen una herramienta útil para el análisis de esta cuestión, véase [1]. El punto de partida de la teoría de grafos se sitúa en 1736, cuando Leonard Euler resolvió el problema de los puentes de Königsberg.

El problema era el siguiente:

“Teniendo en cuenta la disposición de los siete puentes de la ciudad, ¿es posible un recorrido que pase por todas las orillas, empiece y acabe en el mismo punto  y atraviese cada puente una y sólo una vez?”

Con un razonamiento impecable, Euler demostró que no; véase [2] o Los puentes de Koenigsberg.

Más tarde, en 1847, Gustav Kirchhoff introdujo y utilizó grafos para el análisis de redes eléctricas, deduciendo las leyes de cálculo de diferencia de potencial y corriente que llevan su nombre. En 1857, Arthur Cayley recurrió a los grafos para la representación y clasificación molecular de los isómeros y, a mediados del siglo XX, ya eran utilizados para el análisis de las redes sociales.

La teoría fue fundamentada y formalizada en los años 70 del siglo pasado. La motivación principal fue el intento de dar respuesta al problema de los cuatro colores, cuyo enunciado es el siguiente:

“Siempre es posible colorear un mapa con cuatro colores de modo que dos países vecinos nunca tengan el mismo color.”

El problema había sido formulado en 1852 por Francis Guthrie, pero no fue resuelto hasta 1976 por Kenneth Apple y Wolfgang Haken.

El agrupamiento

En los modelos de grafos generados para describir conexiones dentro de una población, cobra importancia no sólo el diámetro y la distancia media, sino también el agrupamiento.

Para determinar el agrupamiento subyacente en un grafo, podemos recurrir a la fórmula   \[C := \frac{3 \times \text{número de ternas tringulares}}{\text{número de ternas conectadas}} \,.\]

Aquí, se dice que una terna de vértices \(\{ a, b, c \}\) está conectada si al menos uno de los vértices es adyacente a los otros dos; se dice que una terna conectada es triangular si los tres vértices son adyacentes a los otros dos. Claramente, podemos interpretar que, cuanto más cerca esté \(C\) de \(1\), más intenso es el agrupamiento de vértices en el grafo.

Watts, Strogatz y las redes de contactos

El modelo de Erdos y Renyi expuesto en la anterior entrada ha sido modificado y mejorado en épocas más recientes por Watts y Strogatz y posteriormente por Kleinberg (véanse [3] y [4]), dando lugar a los llamados grafos de mundo pequeño. Se trata de modelos que ocupan un lugar intermedio entre el grafo regular \(G_0(n)\) y el grafo aleatorio \(G(n)\); véanse las Fig. 4 y 5.

Duncan Watts es actualmente profesor de Sociología en la Universidad de Columbia, autor del libro [5]. A lo largo de su carrera, se ha interesado por varios temas: la ciencia de las redes, la dinámica social y el comportamiento colectivo y el estudio de la desinformación y la desconfianza en los medios digitales.

Steven Strogatz es un matemático aplicado que trabaja en las áreas de la dinámica no lineal y sistemas complejos, a menudo sobre temas inspirados por curiosidades de la vida cotidiana: ¿Por qué es difícil dormir varias horas antes de la hora habitual? ¿Qué información sobre nuestro ADN guarda un objeto cuando los tocamos? O incluso ¿por qué es tan corriente conocer a alguien en un viaje y descubrir conocidos comunes?

En una reciente entrevista, no pudo contener la emoción al hablar sobre los recientes avance de la IA y exclamo: “Ya no podremos aspirar a escalar las montañas más altas, porque las máquinas siempre llegarán primero. Perderemos siempre”. 

En 1998, Duncan J. Watts y Steven Strogatz, por aquel entonces ambos en el Departamento de Mecánica Teórica y Aplicada de la Universidad de Cornell, publicaron el primer modelo de una red de conexiones [3]. Su objetivo era probar que las redes del mundo natural y las del mundo construido por el hombre poseen la llamada propiedad del mundo pequeño. Más precisamente, postularon que, partiendo de una estructura regular, la adición de un pequeño número de vínculos al azar reduce el diámetro de la red de un valor grande a otro mucho menor. La investigación estuvo originalmente inspirada por los esfuerzos de Watts por entender la sincronización de los sonidos emitidos por los grillos, ya que éstos muestran un alto grado de coordinación, como si fuesen conducidos por un guía invisible.

El modelo matemático desarrollado por Watts y Strogatz para explicar este fenómeno ha sido aplicado desde entonces con relativo éxito en un amplio rango de áreas diferentes.

Obsérvese que en una red social no es aceptable suponer que la probabilidad de que dos personas del mismo vecindario se conozcan sea la misma que la probabilidad de que se conozcan Pepito Pérez (de Mairena) y Oliver Jones (de Melbourne). Por tanto, parece adecuado buscar un punto intermedio entre grafos regulares (que se asemejan al mundo real en lo que se refiere al agrupamiento) y grafos aleatorios (que comparten con el mundo real la propiedad de pequeña distancia media).

La idea desarrollada por Watts y Strogatz tiene en cuenta que, si bien la mayoría de contactos de una persona suelen estar entre los que desde un punto de vista geográfico, social o laboral son sus “vecinos”, es muy frecuente que exista un número reducido de contactos “lejanos”. Y éstos juegan el papel de puentes sociales que reducen la distancia de separación considerablemente.

Basándose en esta premisa, diseñaron el siguiente algoritmo:

ALG 1:

1. Inicialización – Comenzamos considerando un grao regular de \(n\) nodos, cada uno de los cuales es adyacente a los \(s\) vértices más cercanos.
2. Aleatorización – Dado un vértice, cada segmento que le afecta es “redirigido” de manera aleatoria con probabilidad \(p\) a otro vértice (no adyacente) aleatoriamente elegido, evitando bucles y aristas duplicadas.

Obsérvese que el procedimiento no cambia el número de vértices ni de segmentos.

Con multitud de simulaciones y argumentos analíticos, Watts and Strogatz mostraron que este algoritmo permite generar una gran familia de grafos intermedios para los cuales el agrupamiento está bien presente y, al mismo tiempo, la distancia media entre nodos decrece: \(C_p\) se mantiene positivo y la distancia media \(L_p\) decrece rápidamente cuando \(p\) crece a \(1\); véase la Fig. 6, donde se han representado las cantidades normalizadas respecto de los valores correspondientes al grafo regular, i.e. para \(p = 0\).

Kleinberg

Jon Kleinberg (Boston, octubre de 1971) es un Profesor de Ingeniería Informática de la Universidad de Cornell. Es conocido sobre todo por inventar el algoritmo HITS, una alternativa al algoritmo del PageRank de Google y por haber escrito, junto a Éva Tardos, el libro [6]. Fue galardonado con el Premio Rolf Nevanlinna en 2006 durante el Congreso Internacional de Matemáticos celebrado en Madrid. La Unión Matemática Internacional (IMU) le otorgó este reconocimiento por «sus profundas y creativas contribuciones matemáticas al análisis del entorno de la información global».

Kleinberg fue más allá que Watts y Strogart. Propuso la siguiente variante de ALG 1:

ALG 1’:

1. Inicialización – Como en ALG 1.
2. Aleatorización – Dado un vértice \(u\), añadir un arista de extremos \(u\) y \(v\) de manera aleatoria con probabilidad proporcional a \(d(u,v)^{-2}\), de nuevo evitando bucles y aristas duplicadas.

La idea es, evidentemente, conectar los vértices con nodos lejanos de forma ocasional, de manera que el agrupamiento no se vea seriamente afectado y, al mismo tiempo, la distancia media disminuya satisfactoriamente.

El resultado siguiente muestra la utilidad de ALG 1’:

Teorema: Aplicado el algoritmo ALG 1’ a una malla inicial regular \(n \times n\), se tiene que la distancia media verifica \(L \leq K (\log n)^2\), donde \(K\) es independiente de \(n\).

Para terminar, indiquemos que existe todavía la posibilidad de mejorar aún más el modelo. En efecto, muchas redes reales presentan con frecuencia agrupaciones relevantes que nada o poco tienen que ver con la distancia entre individuos; véase por ejemplo el modelo de Barabási-Albert en [7], en donde el mecanismo principal es la llamada conexión preferencial.

Referencias:

1. S. Leonesi, The mystery of the six degrees of separation, parts I and II: from order to random, Lett Mat Int (2015) 3:121–127;  The mystery of the six degrees of separation, part II: navigability and small worlds, Lett Mat Int (2015) 3:215–220.
2. L. Euler, Solutio problematis ad geometriam situs pertinentis, Comment. Acad. Sci. U. Petrop 8, 128-40 (1736), Reimpreso en Opera Omnia Series Prima, Vol. 7. pp. 1-10, 1766.
3. D.J. Watts, S.H. Strogatz, Collective dynamics of ‘small-world’ networks. Nature 393, 440–442 (1998).
4. J. Kleinberg, The small-world phenomenon: an algorithmic perspective. In: Proceedings 32nd ACM Symposium on Theory of Computing (2000) (also in Cornell Computer Science Technical Report, 99–1776, 1999).
5. D.J. Watts, Seis grados de separación: la Ciencia de las redes en la era del acceso, Ed. Paidós, 2006.
6. J. Kleinberg, E. Tardos, Algorithm design, Pearson, 2005.
7. L. Barabási, R. Albert, Emergence of scaling in random networks, Science, Vol. 286, 5439 (1999).