El Mundo es Pequeño

Siempre se habla de la aldea global y de lo pequeño que es el mundo en la actualidad. Pero, ¿Cuán pequeño es?. Muchas veces ya no nos extrañamos de que al conocer a alguien, exista una persona en común que ambas partes conocen. En cambio, cuando uno está en otro país, eso es más raro, pero a mi ya no me sorprende. De hecho, una vez mi compañero de asiento de avión, el cual no era chileno, era pariente político directo de un amigo mío (!). El tema de este mes trata de cómo se puede medir esta conectividad mundial.

Modelos basados en Grafos

Imaginemos que por cada persona que conocemos existe una conexión directa entre ella y nosotros. Por ejemplo, un número telefónico. Si hacemos esto para todas las personas del mundo, tenemos un grafo muy grande. En ese grafo podemos ahora medir "distancias" entre dos personas usando el número mínimo de llamadas telefónicas que necesita una persona para contactar con otra. Por ejemplo, si la persona que quiero contactar está en China, es posible que si yo conozco una persona que conoce a una persona en China, el número de llamadas sea pequeño (en el mejor caso, sólo tres llamadas). La distancia máxima entre dos personas se llama el diámetro del grafo, usando una analogía geométrica. A mediados de los sesenta, Milgram realizó un famoso experimento usando paquetes de correo y estimó que el diámetro dentro de Estados Unidos era 6.

Para que un grafo tenga un diametro pequeño, debe tener muchas conexiones. Si todas las conexiones existen, el diámetro es 1. Por otra parte, un grafo aleatorio tiene un diametro mucho mayor. Un modelo de grafo que representa bien este fenómeno, es el de un grafo en el que cada persona está conectada con todas las personas cercanas (geográficamente) y sólo con algunas lejanas de manera aleatoria y con una distribución de probabilidad uniforme. Este modelo se llama small-world o mundo pequeño, valga la redundancia, y también representa bien la red neuronal de un gusano y la red eléctrica del oeste de Estados Unidos, entre otros casos.

El Tamaño de la Web

El año pasado, Albert, Jeong y Barabási midieron la distancia (numero mínimo de enlaces para llegar de una página a otras) entre 330 mil páginas de Internet. Con esto aproximan el diámetro con una función logarítmica en el número de páginas. Extrapolando esta función, considerando que el número de páginas Web es de más de mil millones de páginas, obtuvieron que el diámetro de la Web es aproximadamente 19. Es decir, con 19 clicks del ratón, llegamos a cualquier página Web del planeta. Ellos y otros autores sugieren que un buscador podría aprovechar esto para encontrar rápidamente la página deseada. Sin embargo, esto significa saber que enlace seguir, un problema que no es trivial.

Aunque el modelo de mundo pequeño es válido en la Web, este modelo no explica como una persona que sólo tiene conocimiento local puede saber a quién contactar para encontrar a otra persona. Recientemente, Kleinberg ha modificado el modelo original, de tal modo que las conexiones lejanas no son con una distribución uniforme, sino que con una distribución inversamente proporcional al cuadrado de la distancia. Esta distribución es óptima en el sentido que minimiza el número promedio de llamadas que haría una persona para contactar a otra y explica lo que ocurre en la práctica.


Nota:

Les invito a leer algunas reflexiones sobre la computación. Algunas son obvias, otras son polémicas, pero no quedarán indiferentes y agradeceré sus comentarios. Están disponibles en http://www.dcc.uchile.cl/~rbaeza/manifest/manifest.html.

Si tiene preguntas o sugerencias, envíe e-mail a rbaeza@dcc.uchile.cl