Álvaro Martínez SevillaDpto de Álgebra

Grafos: complejidad y redes de mundo pequeño

Estalmat-Andalucía 2011

Sistemas Complejos: modelos y computación en grafos.• Los grafos son una excelente forma de tratar las realidades complejas, por su capacidad de representación de estructuras interconectadas, y también por su facilidad para el cálculo mediante algoritmos. A su vez plantean varios retos, entre ellos:

• ¿Cómo modelar realidades muy complejas mediantes reglas simples y que puedan ser fácilmente desarrolladas y calculadas en un grafo?

• ¿Cómo trasladar algoritmos, que calculan propiedades de esos modelos, con un tiempo-coste excesivamente alto en algoritmos asequibles para su ejecución?

• Estos serán los dos problemas que abordaremos hoy aquí. Son problemas prolíficos y que han resultado en una ingente aportación a las Matemáticas y la Computación, abordaremos algunas cuestiones sobre ellos de entre las más significativas.

• Son cuestiones que están en plena ebullición investigadora y de actualidad. La emergencia de las redes sociales, la necesidad de representar redes complejas y de calcular con ellas para la mejora de la eficiencia de las mismas (neuronales, de transporta, eléctricas, …), el estudio del comportamiento animal como inspiración para aplicar técnicas de cálculo eficiente, el desarrollo de nuevos algoritmos que resuelven grandes problemas, … todo ello para aportar algo de conocimiento en la comprensión de un mundo cada vez más en red, más interconectado y global.

Estalmat 2011

• Por ejemplo, esta misma semana veíamos esta noticia en la prensa, sobre László Barabási, del que hablaremos posteriormente, y que ha visitado España para participar en un curso sobre redes.

•Previos:• Las dos sesiones que tuvisteis en Estalmat 2010 sobre Grafos :

• Definiciones y conceptos básicos en grafos: Nodo, eje, camino,

• Grafos especiales (conexo, completo, bipartido, árbol).

• Isomorfismo entre grafos.

• Caminos Eulerianos.

• Caminos Hamiltonianos.

• Planaridad.

• Coloración de grafos.

• P y NP

Estalmat 2011

• Un esquema que puede guiar las dos sesiones de hoy:

Estalmat 2011

Grafos

ampliación

Resolución de problemas

Complejidad

Estructura

Técnicas Bioinspiradas:Francisco Herrera

Modelos de mundo pequeño:Álvaro Martínez

Grafos aleatorios

Grafos reticulo

Modelo de Watts-StrogatzModelo de Albert-Barabási

1. Grafos como modelos matemáticos.

• En sesiones anteriores habéis estudiado los Grafos como una importante herramienta para visualizar modelos matemáticos de lo que conocemos como redes: objetos o nodos (vértices, V) que se relacionan entre sí a través de acciones o propiedades comunes (ejes, E).

• Por ejemplo, el grafo de la red de metro de una ciudad, el que Euler diseñó para el problema de los puentes de Könisberg, o el de Hamilton para su puzzle Hamiltoniano:

Estalmat 2011

• el de conocidos problemas de asignación de recursos (3 servicios para 3 casas, grafo bipartido K3,3 , no plano) o el de las personas que se relacionan en una red social:

• Estos últimos tienen unas características especiales, por su complejidad, número mínimos de pasos para llegar de un nodo (persona) a otro y agregación (formación de grupos interconectados de forma completa o tribus, etc.): vamos a estudiar como podemos hacer un modelo que trabaje con estos últimos.

Estalmat 2011

2. Grafos y complejidad.

• También habéis visto que existen dos grandes clases de problemas: P y NP, los que se pueden resolver de forma fácil (los primeros, en tiempo polinomial) o de forma difícil (los segundos en tiempo exponencial).

• Por ejemplo el problema del camino euleriano (grafo 2) es P, mientras que el del camino hamiltoniano (grafo 3) es NP.

• El instituto Claymath expuso uno de los grandes retos pendientes de las Matemáticas, el Cuarto Problema del MIlenio: Determinar si :

¿ P = NP ?

Para lo que ofrece 1.000.000 de $ de recompensa en http://www.claymath.org/millennium/P_vs_NP/

• Aunque nadie ha dicho una palabra sobre esto, a mi se me ocurre al menos una respuesta parcial:

si N = 1, entonces P = NP. Nota: visto escrito en una pizarra del MIT

Estalmat 2011

• Al margen de esta respuesta, hay muchos problemas interesantes en grafos que son NP:

o Problema de la k colorabilidad de grafos. ¿Se puede colorear un grafo con k colores de forma que dos vertices conectados por un eje no tengan un color común?. Este problema se puede resolver facilmente para k = 2 colores en un grafo plano, pero para k = 3 colores es difícil (NP) incluso en grafos planos. El problema es equivalente a colorear un mapa con k colores de forma que dos de ellos con frontera común no tengan el mismo color.

En 1879 Kempe “demostró” que cualquier mapa plano podía colorearse con 4 colores, pero en 1890 Heawood contraargumento que su demostración era falsa con el siguiente mapa. El problema era más correoso de lo que parecía inicialmente, pues hasta 1976, Appel y Haken no lo resolvieron de forma definitiva.

Estalmat 2011

Estalmat 2011

• Sin embargo, en otras superficies, ¡con 4 colores no basta!. ¿Podrías dibujar un mapa sobre el toro que necesitase de al menos 5 colores?, ¿y de 6 colores ?, ¿y de 7?

• Sugerencia: trabajar con el grafo asociado al mapa: Un vértice por cada región y un eje entre vértices por cada dos regiones con frontera común. Poner en la lista de sospechosos a grafos que no son planos, pero que pueden dibujarse sin cruces de ejes sobre el toro.

¿Y sobre la banda de Möebius, cuál es el mínimo de colores necesario?

¡es adictivo!: Heawood empleó 60 años de su vida trabajando sobre este problema.

o Problema del Isomorfismo de grafos : Determinar si dos grafos son isomorfos

o Problema del ciclo simple máximo en un grafo: Consiste en encontrar el ciclo de mayor longitud de un grafo en el que no haya vértices repetidos.

o El problema del Conjunto Independiente (IS): Se trata de encontrar el mayor subconjunto del conjunto de vértices de tal forma que no exista un eje que conecte dos vértices del conjunto independiente. ¿Cual es el tamaño del IS (Número de independencia) en el caso de un grafo completo?, ¿Y en el caso de un grafo bipartido?

Estalmat 2011

• Para todos estos problemas, el comprobar que una solución dada lo es efectivamente es fácil (esta en P), mientras que el encontrar una solución requiere un esfuerzo alto, es difícil (está en NP).

Un cálculo práctico.

Por ejemplo, si tratamos de encontrar un camino hamiltoniano de mínima distancia entre el conjunto de los 18 pueblos del Poniente Granadino (Traveling Salesman Problem, o TSP), supuestos que estos están conectados todos entre sí por caminos directos, que no pasan por otros, entonces deberemos verificar todas las posibles soluciones que son exactamente

factorial(17) = 355687428096000

Estalmat 2011

Es decir, un número del orden de 10 14. Supuesto que podemos verificar por ordenador cada una de estas soluciones en 0,1 sg. (generación del camino, computo de la distancia y comprobación con la menor distancia precedente), entonces, ya que en un año hay 3´15 x 10 7 sg, excluyendo tiempos muertos, tardaríamos en hacer el computo completo aproximadamente ¡1 millón de años!.

¡Imagina si a nuestro viajante se le encarga recorrer la Alpujarra de Granada con 82 pueblos!

3. Mas definiciones de grafos.

• En un grafo G, se define la distancia entre dos vértices de G como el menor número de ejes que hay que recorrer para llegar de un vértice a otro.

•Y se define el Diámetro de G como la mayor distancia posible entre vértices de G. Nos da una medida de lo alejados que pueden estar los vértices en un grafo. Por ejemplo en un grafo completo D = 1, y si el grafo es bipartido, entonces D = 2.

• Un clique en un Grafo G, es un subconjunto de vértices del mismo de forma que estan todos conectados por ejes. En otras palabras, un clique es el conjunto de vértices de un subgrafo completo de G. Podemos hablar de un clique maximal si el subgrafo completo es maximal (no hay otro de mayor número de vértices).

•El número de clique de G es el tamaño (número de vértices de un clique maximal.

.

Estalmat 2011

• Un clique en un grafo G, está relacionado con un conjunto independiente, ya que si existe el primero, entonces existe un conjunto independiente (IS) de igual tamaño en el grafo complementario (el que resulta de tomar los vértices de G y añadirle justamente los ejes que no están en G, quitándole lo que si lo estaban).

Estalmat 2011

Estalmat 2011

4. El experimento de Milgram.

• En 1960, el sociólogo Stanley Milgram ideó un experimento sobre la estructura de las redes sociales. Se trataba de determinar si un cierto número de cartas dirigidas a una persona en Boston podían llegar a ella siendo depositadas sin dirección postal, pero con el nombre del destinatario y profesión. Las cartas fueron dejadas a personas seleccionadas aleatoriamente en Wichita (Kansas) con la instrucción de hacerla llegar al destinatario, pero enviándola sólo si se le conocía directamente. En otro caso, se debía enviar a una persona igualmente conocida que se pensase que tenía más oportunidad de tener éxito en la misión.

• El resultado fue sorprendente: muchas de las cartas no fueron enviadas, pero un porción significativa sí, y alcanzaron su destino con un número de pasos medio de 6. Esto confirmó observaciones previas sobre que la distancia típica en una red social tiene “6 grados de separación”.

• La conclusión es inesperada ya que se tiende a pensar que los amigos de uno están localizados en la vecindad de donde vive: supongamos 100 km. Por tanto en un grafo con conexiones locales como este, la longitud de los caminos debería ser proporcional a la distancia entre los nodos. En la hipótesis de vecindad anterior, ya que Wichita está a cerca de 3000 km de Boston, el número de reenvíos debería haber sido de cerca de 30, ¡no de 6!.

• El experimento de Milgram se ha popularizado como “los 6 grados de separación”. Puede que quepan pequeños ajustes en el experimento, pero hoy es ampliamente aceptado que dos humanos escogidos al azar en el mundo pueden conectarse directamente por una cadena de intermediarios de longitud corta: esto es lo que se llama “efecto de mundo pequeño”.

• Por ejemplo, al trasladar este concepto al mundo de la coautoría en las Matemáticas, aparece el número de Erdös, la distancia de coautoría con Paul Erdös (1913-1996), un genial y prolífico matemático (1500 artículos, 500 coautorias) que era fiel a sus propias palabras: “Un matemático es una máquina que convierte café en Teoremas”. Su propia biografía y estilo de vida es muy peculiar.

• Grafos colaborativos: Calculemos este número para algún matemático cercano conocido aquí

• Importancia de la estructura de las redes sociales: * difusión de las comunicaciones

* difusión de las epidemias

* Economía global

* Redes neuronales, redes en ciencia

Estalmat 2011

5. Modelo de Erdös-Renyi - ER (grafos aleatorios).

• El modelo más inmediato para explicar el efecto de “mundo pequeño” son los grafos aleatorios:

• Si N es el número de personas en la red social, que en media tiene cada una z conocidos, entonces el grafo tiene N*z / 2 ejes entre los vértices. z se llama número de coordinación de la red. La probabilidad de que haya un eje entre dos nodos arbitrarios está dada por la porción:

p = z / (N-1) ≈ z / N para N grande.

• Erdös y Renyi estudiaron estos grafos para diversos casos obteniendo que:

Si N*p < 1, entonces muy probablemente el grafo no tendrá componentes conexas de tamaño mayor que O(log N).

Si N*p = 1 , entonces casi seguramente el grafo tendrá la componente mayor de tamaño O(N 2/3 )

Si N*p → k > 1, entonces probablemente el grafo contiene una componente gigante con una fracción de los vértices. Ninguna otra componente tendrá más de O(log N) vértices.

Estalmat 2011

• Una representación de este tipo de grafos se tiene con N vértices y dibujando aleatoriamente los lados con probabilidad p.

• Estos grafos muestran el efecto de mundo pequeño: Si una persona tiene z vecinos, y cada uno de los vecinos tiene otros z, entonces tiene z2 vecinos de segundo orden, z3 vecinos de tercero, . . .

• El diámetro D del grafo está dado por zD = N, con lo que D = (log N)/ (log z): es decir la distancia entre nodos y el diámetro crece logarítmicamente según el tamaño de la población, lo cual es típico de los modelos de mundo pequeño, que dejan las distancias muy cortas incluso en sistemas muy grandes (¡6 grados!)

Estalmat 2011

• Sin embargo estos grafos no mantienen otra característica de los modelos de mundo pequeño: los círculos de vecinos tienden a extenderse mucho, lo cual no es así en la realidad, ya que las redes están localmente ordenadas: si A es amigo de B, y B es amigo de C, entonces es muy probable que C sea también directamente amigo de A. Esto se llama clustering (agrupamiento). En una red social real el número de segundos vecinos o amigos es mucho menor que z2 , ya que la mayoría de ellos serán a a su vez primeros vecinos.

• El coeficiente de clustering, C, se define como la proporción de parejas de vecinos de un nodo que son también a su vez vecinos entre ellos. Si el grafo es completo, entonces C = 1.

Problema: Determinar el coeficiente C para un grafo bipartido. ¿ Y para un árbol ?.

• En un grafo aleatorio no hay clustering y C = p, no se incrementa la probabilidad de ser vecinos por tener un vecino común, mientras que en las redes sociales reales, aunque es mucho menor que 1, es bastante más alto que p.

•Un ejemplo de cálculo de grafos aleatorios los tenemos aquí

Estalmat 2011

6. Grafos reticulados ordenados.

• Lo contrario a un grafo aleatorio es un grafo correspondiente a un retículo ordenado: conectamos cada nodo del grafo a h nodos cercanos a él. Así se tiene que los vecinos más inmediatos son también vecinos entre ellos, y por tanto el grafo muestra agregación (clustering).

• En este caso el retículo es de dimensión 1 (circular) y el número de vecinos es z = 6, y el coeficiente de clustering puede calcularse que tiende, para z grande, a 3/4. Esto es un comportamiento típico de mundo pequeño.

• Sin embargo, el diámetro del grafo, o la distancia media entre ellos, crece linealmente con el número de nodos, lo cual no es un comportamiento de mundo pequeño. Por tanto este modelo tampoco es adecuado para nuestros propósitos.

Estalmat 2011

7. Modelo de Watts-Strogatz - WS.

• Examinando los dos modelos anteriores, estos autores propusieron un modelo que podría funcionar para mundo pequeño. Tomar un grafo reticulado, y hacer que disminuyese su diámetro cambiando (revirando) algunos ejes por ejes aleatorios con una probabilidad p: es decir tomando uno de sus extremos y asignándolo a otro vértice de forma aleatoria.

• El número de coordinación todavía es z, pero se decrementa el diámetro del grafo de forma dramática cuando crece sólo un poco p. Esto tiene un paralelismo con la realidad: mientras que la mayoría de nuestros amigos suelen vivir cerca, puede haber una pequeña porción que están lejos, por diversas razones.

Estalmat 2011

• Las propiedades estructurales del grafo cambian con p: el coeficiente de clustering C(p) y la longitud de camino media L(p) . Si el grafo es reticulado (p = 0), entonces está altamente agregado y L crece linealmente con N, por el contrario si es aleatorio (p = 1), está muy poco agregado, pero es mundo pequeño, con L creciendo logarítmicamente con N.

• La gráfica muestra que la transición a mundo pequeño es “casi” indetectable a nivel local. Este modelo tiene las dos características deseadas: agregación y mundo pequeño.

Grafica de L(p) y C(p) para una familia de grafos revirados aleatoriamente con N = 1000 y z = 10. Medida tomada para 20 procesos de revirado.

• En la página de Wolfram podemos ver un CDF sobre los grafos de mundo pequeño.

Estalmat 2011

• La comparativa con grafos aleatorios y reticulados en iguales tamaños de vértices y ejes (N = 1000, z = 10) es elocuente:

• Pero incluso a tamaños mucho más bajos de p es patente la diferencia.

8. Ejemplos para redes del mundo real.

• Para ejemplificar las anteriores ideas Watts y Strogatz tomaron 3 redes del mundo real de las que había datos disponibles: El grafo colaborativo de actores en películas, la red eléctrica del oeste de los Estados Unidos, y la red neuronal de un nematodo (C. elegans). En los 3 casos hay comportamiento de mundo pequeño: C red >> C aleatorio , pero L red ~ L aleatorio .

Estalmat 2011

Reticulado Watts - Strogatz Aleatorio

p = 1/4 L = 50 L = 3.6 L = 3.2

Red L red L aleatoria C red C aleatoria

Actores 3.65 2.99 0.79 0.00027

Red eléctrica 18.7 12.4 0.08 0.005

lombriz 2.65 2.25 0.28 0.05

9. Modelo de Albert-Barabási - BA.

• En muchas redes empíricas se observa un fenómeno que no reproducen los modelos ER ni WS: la distribución de grados crece según una función potencial que depende del número de nodos. Esto se denomina ser libre de escala. Tratando de modelizar este hecho Albert y Barabási idearon integrar en el diseño del modelo 2 características:

Propiedad de crecimiento: Las redes tienen un número de nodos creciente cada vez, lo que además lleva aparejada la emergencia: la red cambia con el tiempo y se adapta.

Conexión Preferencial: Los nuevos nodos se añaden uno a uno a la red y se conectan con una probabilidad que es proporcional al grado de cada nodo existente, es decir hay una probabilidad mayor de conectarse a los nodos ya muy enlazados.

• Y aquí podemos ver un CDF sobre la ceación de grafos libres de escala.

Estalmat 2011

• La red comienza con m0 nodos conectados aleatoriamente. La conexión preferencial se explicita asignando una probabilidad de conexión de un nuevo nodo a m ≤ m0 nodos en la red de forma que depende del grado de cada nodo, ki para el i-ésimo nodo:

pi = ki / ∑j kj

• Así los nodos con muchas conexiones o “hubs” tienden a acumular mas enlaces (“la riqueza llama a la riqueza”), mientras que los poco conectados tienen menos probabilidad de adquirir un nuevo enlace. De esta manera habrá nodos cada vez más conectados en el tiempo, aunque existe la posibilidad para algunos nodos de introducir un parámetro de modificación de la conexión preferencial con el tiempo.

• La distribución de grados sigue una ley potencial del tipo P(k) = k – γ , 2 ≤ γ ≤ 3, con lo que sigue una ley potencial, que en representación en escala log-log resulta:

Estalmat 2011

• La longitud media de los caminos (el grado de separación) en esta red es de ℓ = ln (N) / ln(ln (N)).

Problema: Dar una definición matemática para grado de separación y calcularlo para el caso de grafos de tipo especial: completos, bipartidos completos, estrellados, cíclicos de orden n, …• El coeficiente de Clustering es C ~ N – ¾ , en este caso calculado empíricamente no existiendo hasta ahora un cálculo analítico del mismo. Este coeficiente es mayor que en el caso de grafos aleatorios y crece también según una ley potencial según crecen los nodos en la red.• Muchas redes siguen este modelo de Albert-Barabási, entre ellas:• Las redes de citas en artículos científicos, estudiadas en primer lugar por Derek de Solla Price en 1965. El llamo a la asignación preferencial “ventaja acumulativa”.• Las redes de vuelo de las líneas aéreas.• Los modelos de seguridad de nodos en la red, en donde los nodos objetos de ataque son los nodos “hub”• Las redes de interacciones proteína-proteína:

Estalmat 2011

• Los webgraphs, o redes de internet:• Y por supuestos, los modelos más conocidos de todos, las redes sociales:

Estalmat 2011