Un tipo de red con muchos ejemplos y aplicaciones

Redes libres de escala

Vamos a comenzar con un ejemplo, tomado del área de redes sociales. En la siguiente figura, hemos dibujado la red de amistades entre 6 personas. Cada círculo o nodo representa una persona, y cada línea o arco representa que esas dos personas son amigos. Observamos que no todos tienen la misma cantidad de amigos, lo cual es normal en el tipo de redes que armamos en sociedad.

Ahora, vamos a dibujar un gráfico. En este gráfico vamos a omitir las particularidades como quién es amigo de quién, y nos centraremos en las estadísticas; sólo nos importará cuántas personas tienen una determinada cantidad de amigos. Por ejemplo, con 2 amigos, hay 3 personas; con 3 amigos, 2 personas y con 4 amigos, 1 persona. El gráfico queda como en esta figura:

Claramente, la distribución de amigos es bastante dispareja: la mayoría tiene sólo 2 amigos, pero Ana tiene 4. Además, en el gráfico hemos encontrado una línea recta; una pregunta que nos hacemos es si esto ocurre siempre. Para comprobarlo, este ejemplo nos queda un poco chico. Es necesario examinar casos con más nodos para poder ver las cosas con más claridad. Veamos una red de 12 personas y su respectivo gráfico.

Ya no aparece una línea recta, sino que al parecer hay una curva. La causa es lo disparejo de la repartición de amistades, por ejemplo, el nodo que tiene más enlaces (9), tiene más de el doble que el nodo que lo sigue. Para observar bien la forma de esta curva, dibujaremos un gráfico más, esta vez con 21 nodos.

El dibujo de la izquierda, con sus nodos y sus arcos, se está poniendo mucho más complicado y llegados a este punto es difícil saber exactamente quién es amigo de quién. Sin embargo, en el gráfico de la derecha se empieza a ver un fenómeno con bastante claridad: aparece una curva que sigue una ley de potencias porque el número de personas decae siguiendo matemáticamente una potencia del número de amigos.

Nota matemática: a esto también se le llama ley de potencias (power-law) y la ecuación que describe este histograma es y=C x^-alfa . El parámetro "alfa", que es el exponente de la ley de potencias, es un número mayor que cero que describe que tan rápido decae la frecuencia.

Este tipo de distribución estadística es muy frecuente, y la encontramos en todo orden de cosas. Fue observada por el lingüista George K. Zipf en 1940 al estudiar el uso de las palabras en textos. Zipf descubrió que tendemos a usar muchísimo unas pocas palabras al escribir, mientras que la enorme mayoría de las palabras las usamos muy poco. A esto se le llama Ley de Zipf, y él mismo más tarde la llamó Principio del Mínimo Esfuerzo. Si te interesa este tema, mira el artículo sobre Recuperación de Información y Procesamiento de Texto.

Un comportamiento estadístico similar fue observado antes por el economista Wilfredo Pareto en 1890 para la distribución de la riqueza en la población. Pareto observó que el 20% de la población era dueño del 80% de la riqueza, una regla que se conoce como Regla del 80-20, entre otros nombres.

En cuanto a las redes que estamos analizando, el nombre "red libre de escala" proviene de que en estos tipos de redes, a menudo se observa que un nodo crece (en términos de enlaces) proporcionalmente al tamaño que tiene, sin que haya un parámetro de escala que indique, por ejemplo, que dado un cierto número de enlaces ya no se pueden ganar más enlaces o se deben agregar más lentamente. Otra explicación del nombre proviene de que no existe algo "típico" en esta red. Si bien podemos sacar un promedio, el promedio no sirve para nada porque estas redes tienen elementos con muchísimas relaciones y elementos con muy pocas relaciones, sin que exista una escala característica de la red completa.

Hay una cantidad enorme de ejemplos de redes libres de escala, éstas son algunas:

• La red de amistades entre personas, como hemos visto. Esto también se puede extender a las redes de llamadas telefónicas, de envíos postales y de correo electrónico, por ejemplo.

• La red de contactos sexuales entre personas. Hay unas pocas personas que tienen muchas parejas a lo largo de su vida, mientras que la mayoría de las personas tiene unas pocas parejas.

• Las redes del crimen organizado, en los cuales unos cuantos "peces gordos" ordenan la actuación de muchos "peces chicos".

• La red de distribución eléctrica, en que existen estaciones enormes que abastecen a zonas enormes, y al mismo tiempo una miríada de transformadores pequeños.

• Las redes de comercio internacional, dado que los países desarrollados, que son la minoría, concentran la mayor cantidad de intercambio de bienes, mientras que en los países no desarrollados, que son la mayoría, el intercambio comercial es relativamente menor. Esto se aplica también a las redes de comercio entre empresas dentro de cada país.

• La red de páginas web, puesto que unos pocos sitios reciben gran cantidad de enlaces, mientras que la mayoría no recibe ninguno. También las redes de citaciones bibliográficas incluyen unos pocos libros o escritos muy citados, mientras que la mayoría de los libros reciben pocas o incluso ninguna citación.

• Las redes de neuronas en los organismos dotados de sistema nervioso, lo que significa que permanentemente usamos mucho una fracción de las neuronas, mientras que la mayoría de las neuronas las ocupamos muy poco.

• Las redes de interacción de proteínas en el metabolismo celular, con unas pocas proteínas que aparecen en la mayoría de las reacciones, mientras que la mayoría de las proteínas aparecen sólo en situaciones muy específicas.

• Las redes de caminos, pues la mayoría de los caminos llegan a unas pocas ciudades muy grandes, mientras que de la mayoría de ciudades pequeñas salen unos pocos caminos. Lo mismo es válido para las rutas marítimas y los puertos, las rutas aéreas y los aeropuertos.

Esto último tiene una explicación bastante sencilla: si tenemos un presupuesto que alcanza para construir una cantidad limitada de kilómetros, no podemos pretender hacer caminos directos entre cada ciudad y todas las otras. Resulta mucho más eficiente hacer algunas grandes rutas que conecten los núcleos de población más importantes, desde donde salen rutas más pequeñas para las ciudades y pueblos de
menor tamaño.

Un fenómeno que se ha estudiado mucho en estas redes es el fenómeno del mundo-pequeño o small-world, que la sabiduría popular recoge con el dicho en "el mundo es un pañuelo". En un experimento muy importante que se realizó en los años 1960s, el sociólogo Milgram les entregó cartas a distintas personas en Nebraska (en el centro de Estados Unidos) para que las entregaran a una persona que vivía en Massachusets (en la costa este, a cientos de kilómetros).

Obviamente, no se trataba de llevar las cartas hasta allá. Si uno conocía a la persona, le podía entregar la carta directamente. Si no la conocía, tenía que pasar la carta a alguien que uno conociera personalmente y que uno creyera que tendría mejores posibilidades de dar con el destinatario final. El resultado de este experimento fue sorprendente: muchas de las cartas llegaron a destino, y de las que llegaron a destino, en promedio pasaron por seis personas. De ahí que se ha popularizado el concepto de seis grados de separación, que significa que cada persona en EEUU puede llegar a cualquier persona con menos de seis intermediarios. Ahora bien, esto normalmente se malinterpreta: no significa que estemos todos conectados con todos, porque no es así, de los 6 mil millones de personas del mundo o más, nosotros conocemos a muy pocas como para pretender eso. Tampoco significa que nuestro tejido social sea muy cohesionado, simplemente, significa que hay personas muy bien conectadas.

Por ejemplo: yo no conozco personalmente al presidente o presidenta de Chile. Pero quizás conozco a alguien que lo conoce. Si quisiera averiguar cuántos "intermediarios" hay entre yo y él o ella, entonces lo que debería hacer para encontrar el camino más corto, es buscar gente con posiciones importantes dentro del gobierno. Si una profesora en un pueblo pequeño quisiera llegar al presidente, tendría que seguir un camino más o menos así:

Ahora daremos un paso importante. Supongamos que esta profesora de un pueblo pequeño en Chile, quiere ver cuál es su distancia desde un médico en Francia en una ciudad pequeña ... ¿qué debe hacer? Obviamente no debe intentarlo al azar, lo interesante es que debería seguir un procedimiento similar para hacer la medición: buscar personas muy conectadas, un ejemplo extremo podría ser este:

Esta es una manera eficiente de buscar el camino más corto entre dos nodos en una red libre de escala: intentar viajar por los nodos mejor conectados. Esto que hemos visto es una propiedad de cualquiera de estas redes, de hecho en general casi todos los caminos más cortos entre dos nodos pasan por alguno de los nodos mejor conectados. Esto es equivalente a decir que para ir de una ciudad pequeña a otra ciudad pequeña, casi siempre hay que pasar por una ciudad grande:

Esto tiene una implicancia importante, si la mayoría de los caminos más cortos pasan por los nodos mejor conectados, entonces remover los nodos más conectados debe afectar mucho a los caminos.

De hecho, en una red libre de escala, si escogemos un nodo al azar y lo quitamos, lo más probable es que no suceda nada de importancia, pero si en vez de eso, escogemos un nodo de los más conectados y lo quitamos, podemos llegar a desconectar una parte importante de la red.

Si en vez de eliminar solamente el nodo más grande, vamos más allá y quitamos unos pocos nodos selectivamente, el efecto es mucho mayor:

Dicho de otra forma, si quitamos un nodo al azar, probablemente nos toque uno "del montón", de los poco conectados, y no tenga efectos en la red. Por otra parte, quitando unos pocos nodos escogidos a mano, muchos nodos se desconectan, los caminos promedio aumentan mucho de largo, y en general la conectividad de la red se ve severamente limitada.

Esto tiene efectos importantes en diversos tipos de redes, veámoslo en detalle en algunas de las redes que hemos examinado hasta ahora:

• Respecto a las redes de amistades, significa que la ausencia de una persona clave puede hacer que un grupo de amigos, por ejemplo, deje de reunirse.

• Respecto a las redes de contactos sexuales, significa que las políticas para evitar por ejemplo enfermedades de transmisión sexual, deben estar focalizadas en quienes tienen más parejas sexuales. Esto es válido para cualquier otro tipo de enfermedad, en que un proceso de vacunación selectivo y de gran cobertura puede resultar mucho más eficiente que uno masivo pero de menor cobertura.

• Respecto a las redes de distribución eléctrica significa que un fallo en una central eléctrica mayor puede generar un apagón de proporciones, y por lo tanto, esas centrales deben estar mejor vigiladas, o evitar que concentren áreas tan grandes.

• Respecto a las redes de crimen organizado, la implicancia es que hay que enfocar los esfuerzos policiales en los "peces gordos", los jefes de las mafias, puesto que su ausencia destruye las organizaciones completas, mientras que políticas por ejemplo, de tolerancia cero contra el microtráfico, producen un gran número de arrestos pero no logran debilitar para nada a las organizaciones criminales.

• Respecto a las redes de comunicaciones como Internet, esto significa que a pesar de que esta red es distribuída, tiene ciertos nodos clave que conectan grandes áreas de la red, y que estos nodos deben estar adecuadamente protegidos.

Lo que hemos visto acá es solamente una pequeña muestra de las ideas que surgen de entender que ciertos fenómenos corresponden a redes libres de escala. Otras áreas de investigación incluyen el desarrollo de métodos (algoritmos) para encontrar los nodos más importantes o para buscar rápidamente caminos cortos, y la búsqueda de técnicas para detener la propagación de virus, entre muchas otras aplicaciones.

Bibliografía recomendada:

• Albert-Laszlo Barabási: Linked, How Everything Is Connected to Everything Else and What It Means for Business, Science, and Everyday Life, Penguin USA, 2003
• Romualdo Pastor-Satorras y Alessandro Vespignani: Evolution and Structure on the Internet, A Statistical Physics Approach, Cambridge University Press, 2004.
  

ChaTo = Carlos Castillo, Ph.D. ::: Acerca de este Sitio