Redes libres de escala

Lucas Lacasa Dpto. Matemática AplicadaETSI Aeronáuticos, UPM

Índice

1. Ausencia de escala: ley de potencias

2. Redes ‘libres de escala’

¿Dónde?

¿Cómo?

3. Redes libres de escala: ¿Y qué?

Aplicaciones prácticas

Redes libres de escala

¿ CÚAL ES LA ALTURA DE UNA PERSONA?

ESCALA CARACTERÍSTICA

Tamaño característico entre 50 cm y 272 cm

La media está alrededor de 180 cm.

LEY DE POISSON

¿ QUE TIENEN EN COMÚN ESTAS DOS FOTOGRAFIAS ?

NO PODEMOS ASEGURAR EL TAMAÑO !!!

...EXISTEN MUCHOS CUERPOS QUE NO TIENEN UN TAMAÑO o ESCALA CARACTERÍSTICA...

Log-log plotDistribución de tamaños de ciudades

NO EXISTE UN `TAMAÑO MEDIO´ DE CIUDAD BIEN DEFINIDO:

hay muchas ciudades pequeñas pero también hay ciudades muy grandes

LEY DE POTENCIAS O ‘LIBRE DE ESCALA’

EXISTE ESCALA CARACTERÍSTICALEY POISSON LEY GAUSS

NO EXISTE ESCALA CARACTERÍSTICA

LEY DE POTENCIASLOG-LOG

¿DÓNDE PODEMOS ENCONTRAR LEYES DE POTENCIA ?

• GEOMETRÍA FRACTAL

UN FRACTAL ES UN OBJETO QUE TIENE EL MISMO ASPECTO VISTO DESDE

CUALQUIER DISTANCIA. TIENE EL MISMO ASPECTO A TODAS LAS ESCALAS.

Zoom

Cambio de escala

=

¿DÓNDE PODEMOS ENCONTRAR LEYES DE POTENCIA ?

• GEOFÍSICA : - TERREMOTOS

- HURACANES

LEY DE GUTENBERG-RICHTER

¡ LA DISTRIBUCIÓN DEL NÚMERO DE TERREMOTOS EN FUNCIÓN DE SU MAGNITUD SIGUE UNA LEY DE POTENCIAS !

Ley de potencias

¿DÓNDE PODEMOS ENCONTRAR LEYES DE POTENCIA ?

• SOCIOLOGÍA: DISTRIBUCIÓN DEL TAMAÑO DE CIUDADES

• ECONOMÍA: DISTRIBUCION DE LA RIQUEZA, BOLSA

• FÍSICA, BIOLOGÍA, QUÍMICA, MATEMÁTICAS, ETC.

ES UNA LEY QUE APARECE DE FORMA UBICUA

DEBE RESPONDER A MECANISMOS MUY GENERALES

• AUSENCIA DE ESCALA (Fractales)

• SISTEMA CON MUCHOS COMPONENTES, CUANDO ESTOS COMPONENTES INTERACTÚAN ENTRE SÍ LOCALMENTE (Sociología)

2) UNA RED LIBRE DE ESCALA ES AQUELLA QUE POSEE UNA

DISTRIBUCIÓN DE CONECTIVIDAD DE TIPO LEY DE POTENCIAS.

* HAY MUCHOS NODOS CON POCOS ENLACES.

* PERO TAMBIÉN HAY ALGUNOS NODOS CON MUCHOS ENLACES (HUBS).

1) UNA RED ES UN CONJUNTO DE NODOS Y ENLACES.

NODOS COMPONENTES DE UN SISTEMA.

ENLACES RELACIÓN ENTRE COMPONENTES.

¿QUÉ ES UNA RED LIBRE DE ESCALA?

WWW Nodos: WWW documents

Links: URL links

Autoorganizada

Sociedad (redes sociales)

Nodos: individuos

Links: interacciones entre individuos

Ejemplos:

- Modelos de votación

- Estudios de propagación de rumores

Autoorganizada

REDES BIOLÓGICAS

Red metabólicaNodos: metabolitos

Links: reacciones bioquímicas

Nodos: especies

Links: interacciones tróficas

Red trófica

Autoorganizada (evolución)

NO BIOLÓGICAS > 2

www = 2.1

actores = 2.3

citas = 3

eléctricas = 4

BIOLÓGICAS < 2

De proteínas =1.5, 1.6, 1.7, 2.5

Metabólica de E. Coli = 1.7, 2.2

Genética de expresión (levadura) = 1.4-1.7

Genética de interacción funcional = 1.6

Algunas redes de las que conocemos su

topología: P(k) ~ k-

- REDES AUTOORGANIZADAS (¿Evolutivamente?)

- LA INTERACCIÓN ES LOCAL

- SON REDES MUY DIFERENTES UNIVERSALIDAD

¿QUÉ TIENEN EN COMÚN TODOS ESTOS EJEMPLOS?

DEBE EXISTIR MECANISMOS GENERALES / EVOLUTIVOS

MODELIZACIÓN MATEMÁTICA

Enganche preferencial (preferential attachment)

1) POBLACIÓN INICIAL.

2) A CADA t, INTRODUCIMOS NUEVOS NODOS.

3) ESOS NUEVOS NODOS SE ENGANCHARÁN CON LOS EXISTENTES. DE TAL FORMA QUE, LO HARÁN CON MAYOR PROBABILIDAD, CON LOS NODOS MÁS RELEVANTES (MÁS FUERTES).

Tiempo (más nodos)

Población inicial jj

ii k

kk

)(

- Epidemiología (propagación de virus).

- Robustez, tolerancia frente a ataques (deliberados).

- Procesos de optimización (publicidad).

- . . .

APLICACIONES

Propagacion de epidemias:

RED DE CONTACTOS SEXUALES

Nodos: individuos

Links: relaciones sexuales RED LIBRE DE ESCALA

HAY UNOS POCOS NODOS CON MUCHA MAYOR PROBABILIDAD DE CONTAGIAR QUE OTROS (HUBS)

‘La red influye sobre la dinámica’

ESTRATEGIAS DE PREVENCION DE EPIDEMIAS

PREVENCIÓN: ESTUDIO MATEMÁTICO DE LA ROBUSTEZ DE LA RED

ROBUSTEZ FRENTE A FALLOS / ATAQUES: RED ELÉCTRICA

SISTEMA ELÉCTRICO ESPAÑOL

MODELO MATEMÁTICO (RED)

Generadores Nodos

Líneas eléctricas Enlaces

Calentamiento de un generador

Desaparición de un nodo

Mal estado de un cable de tensión

Desaparición de un enlace

Cortes en cadenaApagón general

Desmembración de la red

Fallo aleatorio

Consecuencia

(OTRO EJEMPLO: REDES ECOLÓGICAS y EXTINCIONES)

OPTIMIZACIÓN DEL FLUJO: publicidad por Internet

RED (internet) ES LIBRE DE ESCALA

LA DIFUSIÓN DE INFORMACIÓN ENTRE NODOS NO ES ALEATORIA, SINO QUE ESTÁ ESTRUCTURADA

ESTRATEGIAS DE OPTIMIZACIÓN según QUÉ TIPO DE DIFUSIÓN QUEREMOS (RAPIDEZ, CONSTANCIA, ETC)

Se aplican:

•Teoría de grafos

•Difusión no lineal

•Física estadística (modelos de percolación)

* UBICUAS tanto en la naturaleza como a nivel social o tecnológico

* AUTO-ORGANIZADAS a partir de principios evolutivos.

* Estudio matemático :

- modelización (mecanismos generales)

- propagación: * frenarlo (virus)

* optimizarlo (publicidad)

- seguridad: * tolerancia frente a fallos (infraestructura)

* robustez

* ETCÉTERA

CONCLUSIONES ~ Redes libres de escala P(k) k-