Grandes redes tolerantes a fallos: nuevos modelos, diseño, análisis y algoritmos . MEC-TEC2005-03575 (12/2005 a: 12/2008) Importe: 83.300 € Investigadores: 10 TC

Combinatoria, teoria de grafos y aplicaciones (MA Fiol, JLA Yebra, J Fabrega, O Serra) 22 investigadores, 6 doctorandos.

Grandes grafos y digrafos. Problema (Δ,D) o grado-diámetro

37 tesis desde 1982

http://www-ma4.upc.es/grup_de_grafs/

20 profesores visitantes

en los 2 últimos años

Teoria de grafos y topologia de redes •Grandes grafos: Diseño de grandes redes de interconexión •Redes tolerantes a fallos. •Parámetros: caminos, conectividad, expansión etc. •Redes mundo-pequeño e invariantes de escala

Construcción de grafos con el máximo número de vértices, fijados el grado y el diámetro.

Solo se alcanza para D=2 y D = 3 , 7 y 57 (?)

Teoria algebraica de grafos • Espectro. Digrafos debilmente distancia regulares.

http:/www.caida.org/tools/visualization/plankton/

IP: Francesc Comellas Dep. de Matemàtica Aplicada IV,

[email protected]

Universitat Politècnica de Catalunya

Comunicación en grafos •Algoritmos de enrutamiento y vulnerabilidad •Redes simétricas (grafos de Cayley) •Métodos de optimitzación combinatorica (simulated annealing, algoritmos genéticos, multiagente)

Problema grado-diámetro (Δ,D)

57 67 24 88 58 68 25 89 59 69 26 90 60 70 27 91 61 71 28 92 62 72 29 93 63 73 30 94 48 74 31 95 49 75 16 80 50 76 17 81 51 77 18 82 52 78 19 83 53 79 20 84 54 64 21 85 55 65 22 86 56 66 23 87 8 43 36 63 9 44 37 48 10 45 38 49 11 46 39 50 12 47 40 51 13 32 41 52 14 33 42 53 15 34 43 54

Tabla referenciada, recurso EJC. Desde 1994 http://www-mat.upc.es/grup_de_grafs/grafs/taula_delta_d.html

Algoritmo genético Individuo (posible solución)

Coloreado de grafos

Asignación de frecuencias

012011201020110211012111210120

• Inicialización:

A B

C

2TRX

1TRX

C

B

Algoritmo multi-agente hormigas

grafo

A 2TRX

Algoritmos para optimización combinatoria en grafos

función de coste f(G)=175 MECANISMO DE UN ALGORITMO GENÉTICO individuos

– Se asignan los colores (aleatoriamente) – Se distribuyen las hormigas (aleatoriamente) – Se inicializa la función de coste

1

costes

0

2

E

• Ejecución (cada hormiga):

E

1TRX

D

F

1TRX

3TRX

D

F

generación aleatoria

selección

cruce

mutación

1

0

1

– Moverse al peor nodo vecino (pn) – Cambiar color por mejor color (pc)

0

1

0

0

Problema NP-completo

0

Simulated annealing 1. Generar aleatoriamente una solución inicial. Fijar T0 2. Repetir Nk veces. Modificar ligeramente la solución y calcular la función de coste. Guardarla si es mejor. Si es mejor, aceptarla como nueva solución. Si es peor, aceptarla solamente si e Δf < rand() K Tk 3. Disminuir Tk y repetir 2 hasta que Tk < Tmin

Angeles & Mortales : algoritmo Fijar MaxGeneraciones. Initializar un mundo n x m con A ángeles y M mortales. Asociar una solución aleatória a cada mortal. Asignar la duración de la vida a cada mortal (segun el coste o fitness). Repetir Buscar el mejor mortal. Si es la solución salir. Disminuir los contadores de vida. Eliminar mortales (la guadaña ! ). Mover aleatoriamente todos los ángeles y mortales a una celda vecina. Clonar los mortales que estan a tocar de ángeles. (O bien extender su vida) Mutar mortales. Recalcular costes y asignar nueva vida. Hasta MaxGeneraciones

Parámetros importantes que deben ajustarse: T0, Nk, y tasa de enfriamiento.

Contrato con Airtel (Vodafone)

Desarrollo de software basado en resultados teoria de grafos y algoritmos de optimización (simulated annealing, hormigas) para la assignación de frecuencias en telefonia mòvil.

Internet

C. Elegans

Modelado de grandes redes reales WWW

Grafos mundo-pequeño e invariantes de escala

Número de Erdös Rutas aereas

Fractalidad en grafos. Proteinas Red eléctrica

Sistemas complejos Elementos distintos (nodos) Interacción entre elementos (enlacs)

Redes complejas Modelo matemático: Teoría de Grafos

Las redes reales, en general, son Grandes (enormes) Small-world

La mayoria de redes “reales” son mundo-pequeño invariantes de autosimiliares (small-world) escala (scale-free) (self-similar)

diametro pequeño log(|V|), clustering grande

Scale-free grados segun distribución potencial ( “hubs” )

Autosimilares / fractal Modelos deterministas Basados en cliques (grafos jerarquicos, árboles de cliques recursivos, grafos Apolonios)

Diámetro pequeño Milgram 1967 Grados según Apiñamiento (clustered) ley potencial Watts & Strogatz 1998 Barabási & Albert 1999

Fractales Song, Havlin & Makse 2005, 2006

Propiedades relevantes de una red real Apiñamiento (clustering)

C(v) =

# enlaces entre vecinos n(n-1)/2

Diámetro o distancia media

Retraso máximum en las comunicaciones

Distribución de grados

Redes pequeño-mundo (small-world)

Robustez de la red

Las redes reales presentan apiñamiento C(p) grande, junto con una distancia media L(p ) pequeña. Muy a menudo son también fractales o invariantes de escala (scale-free) Internet AS Actores Red eléctrica

C. Elegans

L 3.1 3.65 18.7 2.65

Lrand 3.35 2.99 12.4 2.25

C 0.11 0.79 0.080 0.28

Crand 0.00023 0.00027 0.005 0.05

diametro pequeño (o dist. media) apiñamiento (clustering) alto

N 153127 225226 4014 282

Grafo small-world Grafo estructurado •clustering elevado Grafo aleatorio • clustering elevado •diámetro pequeño •clustering pequeño •diámetro pequeño •casi regular • diámetro grande • regular

6 grados de separación! Stanley Milgram (1967) 160 cartas Omaha -Nebraska- -> Boston

Número de Erdös http://www.acs.oakland.edu/~grossman/erdoshp.html

1- 509 2- 7494 N= 268.000 |V| = 1000 Δ =10 D = 100 d =49.51 C = 0.67

|V|=1000 Δ =8-13 D = 14 d = 11.1 C = 0.63

Watts & Strogatz, Collective dynamics of “small-world” networks, Nature 393, 440-442 (1998)

number number number number number number number number number number number number number number

0 --1 --2 --3 --4 --5 --6 --7 --8 --9 --10 --11 --12 --13 ---

1 504 6593 33605 83642 87760 40014 11591 3146 819 244 68 23 5

(MathSciNet Jul 2004)

person people people people people people people people people people people people people people

D=23 R=12 D avg = 7.64 δ=1 Δ =509 Δavg = 5.37 C = 0.14

Características mundo-pequeño en redes sociales What a small-world ! Que pequeño es el mundo.

Fields medals Erdös Erdös Erdös Erdös Erdös Erdös Erdös Erdös Erdös Erdös Erdös Erdös Erdös Erdös

Jul 2004

(component conexa)

|V|=1000 Δ = 5-18 D = 5 d = 4.46 C = 0.01

Lars Ahlfors Jesse Douglas Laurent Schwartz Atle Selberg Kunihiko Kodaira Jean-Pierre Serre Klaus Roth Rene Thom Lars Hormander John Milnor Michael Atiyah Paul Cohen Alexander Grothendieck Stephen Smale Alan Baker Heisuke Hironaka Serge Novikov John G. Thompson Enrico Bombieri David Mumford

1936 1936 1950 1950 1954 1954 1958 1958 1962 1962 1966 1966 1966 1966 1970 1970 1970 1970 1974 1974

Finland USA France Norway Japan France Germany France Sweden USA Great Britain USA Germany USA Great Britain Japan USSR USA Italy Great Britain

Pierre Deligne Charles Fefferman Gregori Margulis Daniel Quillen

1978 1978 1978 1978

Belgium USA USSR USA

4 4 4 2 2 3 2 4 3 3 4 5 5 4 2 4 3 3 2 2

Alain Connes William Thurston Shing-Tung Yau

1982 1982 1982

France USA China

3 3 2

Simon Donaldson Gerd Faltings Michael Freedman

1986 1986 1986

Great Britain Germany USA

4 4 3

Valdimir Drinfeld Vaughan Jones Shigemufi Mori Edward Witten

1990 1990 1990 1990

USSR New Zealand Japan USA

4 4 3 3

Pierre-Louis Lions Jean Christophe Yoccoz Jean Bourgain Efim Zelmanov

1994 1994 1994 1994

France France Belgium Russia

4 3 2 3

Richard Borcherds William T. Gowers Maxim L. Kontsevich Curtis McMullen

1998 1998 1998 1998

S Afr/Gt Brtn Great Britain Russia USA

2 4 4 3

Vladimir Voevodsky Laurent Lafforgue

2002 2002

Russia France

4 inf

2006 2006 2006

USA USA France

3 3 3

Andrei Okounkov Terence Tao 3 Wendelin Werner 2 4 3

...... Collins, P. J. Colwell, Peter Comellas, Francesc Comets, Francis M. Comfort, W. Wistar Compton, Kevin J. Conder, Marston Conrey, J. Brian CONWAY, JOHN HORTON Conze-Berline, Nicole Cook, Curtis R. Cook, Janice .....

Scalability vs Fractality

Scale-free networks

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

1227 1656 1060 401 252 137 84 46 27 26 11 5 5 3 0 0 0 1 1

7 8 9 10 11 12 13 14

0 5 93 806 90 5 1 0

Power grid

SWCirculant |V|=1000 Δ =8-13 D = 14 d = 11.1 Small World C = 0.63

|V|=4491 δ =1 Δ =19 D = 46 d = 34.54 Small World C = 0.08 A-L. Barabási i R. Albert, Emergence of scaling in random networks. Science 286, 509-510 (1999)

Redes reales de las que conocemos la topologia: P(k) ~ k- γ NO BIOLOGICAs γ > 2 www (in) γ = 2.1 γ = 2.3 actores γ=3 citationes red eléctrica γ=4

P(k) = k - γ A: actors B: WWW C: power grid

Interes de las redes scale-free: Fiabilidad / Supervivencia de la WWW

Albert, Jeong, Barabási Nature 406, 378 (2000)

Fallo aleatorio de nodos

Ataques intencionados a hubs

N=212.250 k=28.78 γ =2.3 N=325.729 k=5.46 γ =2.67 N= 4.94 k=2.67 γ =4

Propagación de virus / “vacunas” WWW, redes sociales R. Cohen, D. ben-Avraham, S. Havlin; Efficient immunization of populations and computers Phys. Rev. Lett. 91, 247901 (2003)

fc umbral λ exponente ley potencial “vacunar” nodos con grado elevado ! arriba– totalmente aleatoria abajo- vacunación conocidos (rojo), doble conocidos. (verde) método: * Seleccionar un nodo aleatoriamente * Buscar un vecino suyo de grado alto y vacunarlo

Search in power-law networks Adamic, Lukose, Puniyani, Huberman; Phys. Rev. E 64, 046135 (2001)

www (out)

γ =2.45

γ