
La ciencia de redes o teoría de redes complejas, es la convergencia de diversas disciplinas que incluyen la teoría de grafos de las matemáticas, la mecánica estadística de la física, la minería de datos y la visualización de la información de ciencias de la computación, la estadística inferencial y la estructura social.
Introducción
El objetivo de la teoría de redes es estudiar las llamadas redes complejas. Sean algunos ejemplos:
8.1.- CIENCIA DE REDES COMPLEJAS. TERMINOLOGÍA
La Teoría General de Redes, las Ciencias de Redes, trata de entender la estructura, evolución y comportamiento de una red en cualquiera de sus manifestaciones, así como las propiedades que son comunes a todas las redes complejas.
Todas las redes tienen un fundamento matemático, y también un hito fundacional: el famoso trabajo de Euler, escrito en 1736 sobre los siete puentes de Königsberg. La descripción matemática de vértices y aristas de Euler fue la base de la teoría de grafos, una rama de las Matemáticas que estudia las propiedades de las relaciones en una estructura de red.
8.2.- MEDICIONES EN UNA RED
Las medidas que se realizan en una red permiten su análisis. Estas medidas pueden ser locales, cuando se realizan sobre nodos concretos o globales cuando lo hacen sobre toda la red. Las medidas globales suelen ser los valores promedio de las medidas locales.
Las medidas más importantes de una red son la distribución de grados, las distancias y caminos, locales o globales y el coeficiente de clustering.
8.3.- EL COEFICIENTE DE CLUSTERING
El coeficiente de clustering como medida global que tiene varias interpretaciones:
1ª.- es un valor que mide la densidad total de la red;
2ª.- una medida de la probabilidad de que dos vecinos de un nodo elegido al azar estén conectados entre sí;
3ª.- también es un indicador del tiempo que tarda la información en viajar de una parte de la red.
Referencias y lecturas complementarias
1.- Artículo «Coeficiente de agrupamiento«
8.4.- MODELOS EN LAS CIENCIAS DE REDES COMPLEJAS
Las mediciones, ya sean locales o globales de una red es el primer paso para comprender su estructura. El siguiente paso es, entonces, desarrollar un modelo matemático de la red que proporcione una topología con propiedades estadísticas similares a las reales, obteniendo una plataforma en la que sea posible aplicar diversos métodos matemáticos para analizar comportamientos generales de redes similares. Los modelos que se pueden considerar son:
- Regulares Completas.- Cada nodo está conectado a todos los demás.
- Regulares de Grado k.- Todos los nodos tienen el mismo número k de enlaces
- Aleatorias.- Cada nodo está conectado a otros nodos con una probabilidad
- Mundo Pequeño.- Se pueden considerar intermedias entre las regulares y las aleatorias
- Libres de escala.- Tienen nodos con muchos enlaces, (hubs), junto a nodos de pocos enlaces
Hay dos formas de definir una red aleatoria:
Modelo G(N, L): N nodos etiquetados están conectados con L enlaces colocados al azar.
Modelo G(N, p): Cada par de N nodos etiquetados está conectado con probabilidad p.
El objetivo principal de las redes aleatorias es determinar para qué valores de p aparecerán propiedades específicas en la red. Las redes aleatorias fueron estudiadas por los matemáticos Erdös y Rényi a finales de las década de los 50.
Referencias y lecturas complementarias
1.- Artículo «Modelo Erdös–Rényi»
8.5.- REDES DE MUNDO PEQUEÑO
Las redes aleatorias (redes ER) dominaron el panorama de las ciencias de redes casi durante 40 años. A medida que las redes reales se fueron conociendo de manera más profunda, se ponía de manifiesto que las redes reales no podían ser ni regulares ni aleatorias. Así, las interacciones entre nuestras proteínas se rigen por las estrictas leyes de la bioquímica, para que en la célula funcione su arquitectura química las redes de interacciones proteicas no pueden ser aleatorias.
Duncan Watts y Steven Strogatz propusieron una extensión del modelo de red aleatoria motivado por dos observaciones:
Propiedad del mundo pequeño.- En redes reales, la distancia promedio entre dos nodos depende logarítmicamente de N, en lugar de seguir un polinomio esperado para redes regulares.
Alto agrupamiento.- El coeficiente de agrupamiento promedio de las redes reales es mucho más alto de lo esperado para una red aleatoria de N y L similares.
La propiedad del Mundo Pequeño se puede expresar, haciendo uso de las redes sociales habituales, como Facebook o Twitter, afirmando que hay un camino muy corto (saltos de nodos) entre uno mismo y alguien muy famoso. La razón de esto es que la gente más conocida son los ‘hubs’ (concentradores) en las redes sociales.
Para cuantificar este fenómeno, el fenómeno social Stanley Migram probó en un experimento que, en promedio, había aproximadamente, lo que llamó seis grados de separación.
El proceso de creación de una red de mundo pequeño se basa en redirigir aleatoriamente un numero determinado de enlaces a otros nodos. Hay un modelo al respecto en NetLogo SmallWorldNetworks que puede descargarse aquí. (Transcripción en Modelos para esta unidad: N09.- SmallWorldNetworks)
Referencias y lecturas complementarias
1.- Artículos «Red de mundo pequeño» y «Modelo Watts y Strogatz«
2.- Artículo «Experimento del mundo pequeño«
3.- Artículo «Steven Strogatz«
4.- Artículo «Duncan J. Watts«
5.- Artículo «Stanley Milgram«
8.6.- REDES LIBRES DE ESCALA
En las redes aleatorias y los modelos de mundo pequeño la distribución de grados es homogénea, con un pico en el valor promedio y con un decaimiento exponencial:
Los modelos aleatorio y de mundo pequeño asumen que las redes complejas tienen un número N de nodos que fijo y que la probabilidad p de que dos nodos se conecten es siempre la misma, lo que da lugar a una distribución de grados con decaimiento exponencial.
En 1999 Barabási y Albert estudiaron la red WWW y descubrieron una serie de características fundamentales de las redes complejas de gran tamaño: el número N lejos de ser fijo crece continuamente y las distribuciones de grado siguen leyes de potencia, no leyes exponenciales.
Se estableció un nuevo modelo que tenía en cuenta los descubrimientos de Albert y Barabási: distribución de grado con leyes de potencia y la autoorganización de la red en continuo crecimiento. A estas redes se las conoce como redes libres de escala.
Referencias y lecturas complementarias
1.- Artículo «Ley potencial
La autoorganización de las redes reales de gran tamaño se observa en dos hechos, crecimiento, es decir, son abiertas y tienen una dinámica por la cual se añaden continuamente nuevos nodos a la red y el acercamiento preferencial. Hay un modelo en NetLogo al respecto, preferential-attachment que puede descargarse aquí. (Transcripción en N09.- Preferential attachment)
Una característica de las redes de cola larga es que están estructuradas entorno a grandes concentradores de enlaces (los hubs). Ello tiene ciertas implicaciones:
Referencias y lecturas complementarias
1.- Artículos «Modelo Barabási–Albert» y «Red libre de escala«
2.- Artículos «Réka Albert» y «Lászlo Barabási«
3.- Artículo «Apagón del noreste de Estados Unidos de 2003«
4.- Artículo «Ataque de denegación de servicio«
5.- Un manual muy popular (y muy completo) sobre redes está en formato online. Se llama «Network Science» y está escrito por Réka Albert y Lászlo Barabasi.