Notas sobre REDES COMPLEJAS
Famaf, Noviembre 2, 2005
1
● Motivación y elementos de redes
● Ejemplos de redes complejas
● Conceptos básicos
● Análisis de algunas Redes Reales
2
Introducción: Motivación (1)
Expresiones Populares de
Small Worlds
¿A cuántos saludos estás tú de
Bill Clinton?
Six degrees of separation
Los números de Kevin Bacon y
de Paul Erdös
1
PE-0
1
1
2
2
Los seis grados de M. Lewinski
3
3
Introducción: Motivación (2)
Motivación para Redes Complejas
Incapacidad de las redes aleatorias de
capturar algunas características básicas de las
redes complejas y generar principios de
organización no triviales.
Sumado a la gran cantidad de información
disponible en diferentes sistemas complejos
por los avances en Computacion y obtencion
de datos de sistemas reales.
4
Introducción: Elementos de Redes (1)
Describen amplia variedad de sistemas naturales,
tecnológicos y sociales.
Se representan por medio de grafos dirigidos o nodirigidos.
Tenemos nodos y enlaces. Un enlace (i,j) conecta
los nodos i y j
Cada nodo tiene un número entero no-negativo de
enlaces conectados (grado del nodo).
5
Introducción: Elementos de Redes (2)
A complex network often is the skeleton of a complex system
Satellite View
NY City Area
Conmuter View
NY City Area
6
Introducción: Elementos de Redes (1)
The way in which nodes connect each other is relevant in many aspects…
Pinochet
7
Introducción: Elementos de Redes (1)
More often networks in Nature are non homogeneous
Homogeneous
Scale-free
P(k) ~ k -
In random nets most nodes are linked by about the same number of links (k), while in scale-free nets a few are extremely well connected.
8
Introducción: Elementos de Redes (1)
A few numbers to pay attention
Homogeneous
Average
minimal length: L (shortest distance between any two nodes)
Clustering:
C(k) (how many of your links are also mutually linked)
The “few well connected”
Random
Scale-free
Small word
Is “small-world” if:

C >> Crand

L ~ Lrand
9
Introducción: Elementos de Redes (1)
Example
The highway system is homogeneous
The consequence of deleting a node (city or airport) is dramatically different
in these two cases.
The airline network is Scale-Free
Scale-free nets, in terms of resistance to damage are: Robust (to random) but
Fragile (to targeted attack).
1. Introduction
2. Complex Networks
3. Catalogue
4. fMRI nets
5. Ever New?
6. Cortical Cultures 7. Conclusion
10
Redes Complejas
Ejemplos
Internet es una red compleja donde los nodos son
computadores y routers y las aristas comunican
computadores.
También se puede definir la red a nivel de inter-dominio
(o sistema autónomo), donde cada dominio, compuesto
de cientos de routers y computadores, se representa por
un único nodo, y un enlace conecta dos dominios si
existe a lo menos una ruta que los conecte.
11
Internet
12
Ejemplos de Redes Complejas (2)
WWW es una red compleja (virtual) los nodos
son las páginas web y las enlaces son los
hyperlinks.
Se pueden establecer a nivel de dominios y
de páginas.
www.chialvo.net
www.ucla.edu/~dchialvo/
13
Ejemplos de Redes Complejas (3)
Redes Celulares es una red compleja
donde los nodos son substratos tales
como ATP, ADP y H2O y los enlaces
representan reacciones químicas
(dirigidas) entre los substratos.
Interacciones entre proteínas donde
los nodos son proteínas y los enlaces
conectan proteínas que a través de
experimentos se demuestra que
interactúan.
14
Nodes: chemicals (substrates)
Metabolic Network
Links: bio-chemical reactions
15
Nature 408 307 (2000)
…“One way to understand the p53 network is to compare it to
the Internet.The cell, like the Internet, appears to be a ‘scale-free
network’.”
16
Ejemplos de Redes Complejas (4)
Redes Lingüísticas las palabras son nodos y
los enlaces conectan palabras consecutivas
(no trivialmente) o casi consecutivas en un
texto.
Otra red lingüística mantiene los nodos como
palabras pero las enlaces son palabras que
son sinónimos, antonimos, etc.
17
Ejemplos de Redes Complejas (5)
Red Social: Es un conjunto de personas, cada
una de ellas conocida para un subconjunto de
las restantes. Se puede definir en diferentes
contextos particulares, como por ejemplo, la
Universidad de Cordoba, y también generales;
por ejemplo, el mundo entero.
Una motivación para su estudio es conocer los
patrones de interacción humana, y otra puede
ser investigar implicaciones para la difusión
de información y contagio.
18
Red Social:
19
Sex-web
Nodes: people (Females; Males)
Links: sexual relationships
4781 Swedes; 18-74;
59% response rate.
20
Liljeros et al. Nature
2001
Ejemplo de Redes Complejas (6)
Collaborativas (co-autoría de papers) donde
los nodos son científicos y los enlaces
representan co-autoría en un paper.
El ejemplo más famoso de este tipo de red
es en torno al matemático Paul Erdös
(número de Erdös).
[ más detalle esta red]
21
Ejemplos de Redes Complejas (7)
Citaciones en artículos científicos donde los
nodos son artículos publicados y un enlace
apunta a una referencia de un artículo
publicado. (no debería tener ciclos dirigidos)
(Physical Review Letters 1975-94, ISI)
Actores de cine (y/o TV) donde los nodos son
los actores y una enlace representa una
participación conjunta de actores en una
película.
22
Ejemplos de Redes Complejas (8)
Llamadas Telefónicas (larga distancia). Los
nodos son números telefónicos y las aristas son
arcos dirigidos del nodo origen al nodo destino
de la llamada.(duró el experimento un día - USA)
Redes Ecológicas en las cuales los nodos son
especies y Los enlaces representan relaciones
tipo predador-presa entre las especies. [se
estudiaron 7 webs de comida]
Contactos sexuales humanos. Los nodos son
personas y las enlaces conectan dos personas
que se han relacionado sexualmente.
(Experimento conducido en Suecia [1996])
23
Food Web (red troficas)
Nodes: trophic species
Links: trophic interactions
R.J. Williams, N.D. Martinez Nature (2000)
R. Sole (cond-mat/0011195)
24
Ejemplos de Redes Complejas (9)
Redes Neuronales en las cuales los nodos son
neuronas y los enlaces son sinapsis o correlaciones
entre (grupos de) neuronas.
[C elegans, Corteza Cerebral, Fmri]
Redes de Potencia donde los nodos son generadores,
transformadores y subestaciones, y los enlaces son
líneas de transmisión de alto voltaje. [Western USA ]
Otras Redes
Circuitos Electrónicos
Evolución Viral
25
Mapa del sistema nervioso del C. Elegans
26
Degree k, degree distribution
P(k)
Degree = total number of
connections (edges) from a
node
In- and out-degrees for
directed graphs
Average degree <k>
Degree distribution P(k)
= function expressing the
probability that a node has
degree k
Log distribution (log P(k)
as function of log k) is also
often used
27
Between1999 – 2001, researchers
found out that
most real world networks have
the same internal structure:
Scale-free networks
ie P(k) ~ k-r
r constant
Why?
What does it mean?
28
Scale-free complex networks
29
Nature July 27, 2000
30
Halting Viruses in Scale-Free
Networks
Classical Epidemiology: epidemic threshold T
exists, such that transmission probability < T implies
disease will die out
Recent Results:


T = 0 in scale free networks (Pastor-Satorras & Vespigniani 01)
Network of sexual contacts is scale-free (Liljeros et al 01)
 spread of AIDS will not be stopped by
traditional methods
Solution: immunizing hubs (with degree > k0)
restores positive T )
31
Barabasi-Albert Scale-free model
(1) GROWTH :
At every timestep we add a new node with m edges
(connected to the nodes already present in the system).
(2) PREFERENTIAL ATTACHMENT :
The probability Π that a new node will be connected to
node i depends on the connectivity ki of that node
 (ki ) 
ki
 jk j
P(k) ~k-3
A.-L.Barabási, R. Albert, Science 286, 50932(1999)
Hierarchical structures
Problem: scale free model did not explain
recent discovery of Dorogovtsev et al (in the
deterministic scale-free case, 12/01) that
C(k) ~ k -1
A new „hierarchical model“ in recent papers
by Ravascz, Barabasi et al (Science Sep 02, Phys Rev
E in press) integrates modularity and scalefreedom
33
Hierarchical growth
34
Hierarchical vs. „classical“ scalefree models
35
Measurements for some networks
36
CONCEPTOS BÁSICOS
Small Worlds (Mundos Pequeños) [o el fenómeno
de los seis grados de separación]
En algunas redes (pudiendo tener millones de
nodos), el camino más corto (CMC) entre dos
nodos cualesquiera (en promedio), medido
como la cantidad de aristas en el camino, es un
número pequeño.(típicamente menor a 7)
37
Conceptos Básicos: Small Worlds (2)
Esta propiedad es aplicable a muchas redes
complejas, como redes de actores de cine, donde
el promedio CMC es aprox. 3, o los substratos en
una célula están separados por 3 reacciones.
Ejemplo hecho a mano:
38
Conceptos Básicos: Small Worlds (3)
El psicólogo S. Milgram (Yale U.) [67] realizó un
experimento que partía seleccionando 300 personas al
azar en USA (Boston y Omaha), debidamente instruídos
para enviar una carta a única persona “objetivo” en
Boston.
Estos diseminadores disponían de ciertas guías acerca
de la persona objetivo, tal como su localización
geográfica y ocupación.
Con base en esta información, los diseminadores
debieron mandar una carta a una persona que ellos
conocían y que se ajustaba lo mejor posible a esta
información.
Este proceso se repitió hasta que las cartas
eventualmente llegaron finalmente a la persona
objetivo.
39
Conceptos Básicos: Small Worlds (4)
Milgram publicó los resultados de su investigación
(Psychology Today) diciendo que 60 de las 300 cartas
llegaron a la persona correcta y que pasaron, en
promedio, por seis conjuntos de manos hasta llegar a
la persona correcta. (note que solo el 1/5 llego)
La conclusión de Milgram fue que las personas están
mucho más cercanas entre si de lo que uno puede
imaginar. La realidad es un poco diferente...
Esta experiencia generó un hito en lo que ahora se
conoce como propiedad de mundos pequeños o los
seis grados de separación o los seis grados de Kevin
Bacon y, posiblemente, otros nombres.
40
Conceptos Básicos: Small Worlds (5)
Después del experimento de Milgram, pasaron
muchos años antes de continuar con ese tipo de
trabajos, principalmente por las limitaciones en
cuanto al manejo de grandes cantidades de
información.
En todo caso, en el año 1993, se hizo una película Six
Degrees of Separation (adaptación de una obra de
teatro inspirada en el fenómeno).
A partir de finales de los años 90, el tema se ha
desarrollado fuertemente con gran ayuda de las
tecnologías de información y con nuevas teorías.
41
Conceptos Básicos: Small Worlds (6)
Tres estudiantes inventaron el juego “Los seis
grados de Kevin Bacon” y es posible jugarlo
on-line en una página de CS-D de Virginia U. (o
los 4 grados de KB)
( http://oracleofbacon.org/)
El grafo para el oráculo de Bacon es provisto
por la base de datos de películas de Virginia U.
42
El oracle
•The Oracle says: alfredo alcon has a Bacon number of 3.
•Alfredo Alcon was in Jandro (1965) with Luis Induni
•Luis Induni was in Bianco, il giallo, il nero, Il (1975) with Eli
Wallach
•Eli Wallach was in Mystic River (2003) with Kevin Bacon
•The Oracle says: Palito Ortega has a Bacon number of 3.
•Palito Ortega was in Amor en el aire (1967) with Cris Huerta
•Cris Huerta was in Bianco, il giallo, il nero, Il (1975) with Eli
Wallach
•Eli Wallach was in Mystic River (2003) with Kevin Bacon
43
Conceptos Básicos: Small Worlds (7)
Bajo ciertas condiciones puede ser importante
para nosotros saber algunas cosas de los
amigos de los amigos de nuestras amigas (os).
Por ejemplo, al momento de relacionarse
sexualmente con alguien.
Lo anterior podría ocurrir para otros efectos,
como por ejemplo, para la búsqueda de un
buen trabajo.
En definitiva, ya sea en la vida profesional o
en la privada, las redes y sus complejas
estructuras nos pueden ayudar a comprender
mejor el mundo.
44
Highly clustered „small
worlds“
Nature June 4, 1998
August 1999
http://smallworld.sociology.columbia.edu
45
Conceptos Básicos: Small Worlds (8)
Una ilustración de la topología de las redes dependiendo del nivel de
aleatoriedad.
Redes regulares, redes small-worlds y redes aleatorias.
46
Clustering (Agrupamiento)
El clustering se refiere a la conectividad
entre los nodos que conforman la red.
En un caso extremo tenemos un(a) clique
(clan) en el cual cada par de nodos está
conectado.
Denotemos por ki el grado del nodo i. Si el
nodo i fuese parte de un clique entonces
este clique tiene ki (ki -1)/2 enlaces.
Ei: número de enlaces que hay entre los ki
nodos.
47
Clustering (2)
Coeficiente de clustering del nodo i, Ci, se
define por la fracción entre el número de
enlaces en los ki nodos, Ei, y el máximo
posible.
Ci = 2Ei /ki(ki-1)
C(G) es el promedio de los Ci.
En un grafo aleatorio tenemos:
Ei = p·  k  ⇒ Ci = Ei /  k  = p.
i
2
i
2
En la mayoría de las redes reales, C(G) es
mucho mayor que en redes aleatorias del
mismo tamaño.
48
Clustering (3)
Ejemplo:
n = 1000 ⇒ m =500.000
En redes reales, m = ßn; si ß = 3 ⇒ m = 3.000
Aplicamos la propiedad que: ∑ gr(k) = 2m
y luego (para redes aleatorias):
m = n <k>/2 ⇒ <k> = 2m/n.
Además, para redes aleatorias: p = <k>/n.
⇒ p = 2m/n2 ⇒ p = 6.000/1.000000 = 0.006,
un valor típico para redes aleatorias.
49
Distribución de Grado
Salvo redes regulares, no todos los nodos de
una red tienen el mismo grado pudiendo,
incluso, tener todos los grados diferentes.
P(k) : función de distribución para la
probabilidad que un nodo seleccionado tenga
exactamente k enlaces.
Para un grafo aleatorio, P(k) se distribuye
Poisson con un pico en <k>, el grado
promedio de la red.
50
Distribución de Grado (2)
Para la mayoría de las redes grandes, P(k) se
distribuye de una forma bien diferente a una
distribución de Poisson.
Para las redes WWW, Internet y redes
metabólicas, la distribución sigue una ley de
potencias; esto es,
P(k) = β·k-γ
51
Modelos de Redes
Existen tres paradigmas de modelos:
- Modelos de Grafos aleatorios: se usan en varios
campos y sirven como benchmarks para
modelación y estudios empíricos.
- Modelos Small Worlds: se sitúan entre redes regulares
altamente clustered y grafos aleatorios.
- Modelos con Distribución de grado de ley de
potencias: se enfocan sobre redes dinámicas,
buscando ofrecer una teoría universal de evolución en
redes.
52
La Topología de Redes Reales
3 medidas robustas de la topología de redes: longitud
de camino promedio, coeficiente de clustering, y
distribución de grado.
Mostraremos dos tablas, una para las propiedades
generales de las bases de datos estudiadas y la otra
para los exponentes obtenidos.
N: número de nodos en la red.
<k>: grado promedio de la red.
l : longitud de camino promedio.
C : Coeficiente de clustering.
53
La Topología de Redes Reales: varios casos (2)
Red
n
<k>
l
WWW
153127
35.21
3.1
Internet
domain
3015-6209
Actores
225226
61
3.65
2.99
0.79
0.00027
Medline
coautoría
1520251
18.1
4.6
4.91
0.066
1.1·10-5
NCSTRL
coautoría
11994
3.59
9.7
7.34
0.496
3·10-4
Neurosc.
coautoría
209293
11.5
6
5.01
0.76
5.5·10-5
7.35
2.9
3.04
0.32
0.026
70.13
2.67
3.03
0.437
0.0001
E. Coli
grafo sub
Co-ocurr.
palabras
282
460902
3.52-4.11
lrand
3.7-3.76
3.35
6.36-6.18
C
Crand
0.1078
0.00023
0.18-0.3
0.001
54
La Topología de Redes Reales: varios casos (3)
Net
n
<k>
γout
γin
lreal
lrand
2.72
2.1
16
8.85
4
6.3
WWW
2·108
WWW
site
26000
Internet
domain
30154389
3.423.76
2.1-2.2
2.1-2.2
Internet
router
3888
2.57
2.48
2.48
12.15
9.75
Coauth.
Math.
70975
3.9
2.5
2.5
9.5
8.2
Phone
Call
53·106
3.16
2.1
2.1
Co-ocur
words
460902
70.13
2.7
2.7
7.5
1.94
55
La Topología de Redes Reales: varios casos (4)
Algunas Conclusiones de Redes Reales
Web
- Cumple mundos pequeños. l = 16 para una red grande
(n = 108).
- Para una red con aprox. 153.000 sitios, Adamic
encontró C = 0.1078, comparado con Crand = 0.00023,
para un grafo aleatorio del mismo tamaño y grado
promedio. Esto es, una fracción muy pequeña. (versión
red no-dirigida)
- Para la distribución de grado analizamos la distribución
de los grados internos y los externos. En varios estudios
se encontró que ambos valores siguen una ley de
potencias con valores de γ entre 2 y 3.
56
La Topología de Redes Reales: Internet (10)
Internet
Diversos estudios llegaron a resultados
similares respecto a que la distribución de
grado sigue una ley de potencias. La longitud
de camino promedio también fue pequeña y
el coeficiente de clustering fue mucho mayor
que para el caso de redes aleatorias.
Resultados similares se encontraron para las
otras redes estudiadas.
57
La Topología de Redes Reales: Red de colaboración (Math.) (11)
Red de Colaboración y Número de Erdös
(Estadísticas de la Red)
Información [2004] es dada por la bases de datos de
Mathematical Reviews (MR) de la American
Mathematical Society.
1.9 millones de artículos para 401.000 autores
diferentes.
62.4% escritos por un único autor, 27.4% por dos
autores, 8% por tres autores y 2.2% por más
autores.
En los años 40, los artículos escritos por un único
autor correspondían al 90% y ahora están bajo el
50%.
58
La Topología de Redes Reales: Red de colaboración (Math.) (12)
Sea B un grafo bipartito cuyos nodos son artículos y
autores. B tiene 2.9 millones de enlaces.
Promedio de autores por artículo: 1.51.
Promedio de artículos por autor: 7.21 y la mediana es 2.
42% en la bases de datos tiene un único artículo.
Cuatro autores tienen más de 700 artículos (Erdös tiene
1416) y ocho con más de 500 y menos de 700.
59
La Topología de Redes Reales: Red de colaboración (Math.) (13)
La Red de Colaboración C tiene 401.000 autores como
nodos y dos autores están conectados si participan en
un mismo artículo (existan o no otros co-autores).
C tiene 676.000 aristas y el número promedio de
colaboradores por autor es 3.36.
En C existe una componente grande con 268.000
nodos. De los restantes 133.000, 84.000 no han
colaborado, y luego, son nodos aislados en C.
El número promedio de colaboradores por autores que
han colaborado es 4.25, que sube a 4.73 para los que
están en la componente grande, y cae a 1.65 para
aquellos que no están en la componente grande pero
que han colaborado.
60
La Topología de Redes Reales: Red de colaboración (Math.) (14)
Para la clase de autores que han colaborado,
la mediana es 1, la media es 4.25. Si
despreciamos los nodos aislados entonces la
mediana sube a 2 y la media sube a 5.37.
Grados no nulos se ajustan a una ley de
potencias:
número de nodos con grado x = β·xk, k entre
-2 y -3.
Existen 5 autores con más de 200 co-autores y
Erdös es uno de ellos.
61
La Topología de Redes Reales: Red de colaboración (Math.) (15)
Small Worlds
1. Longitud Promedio: Se tomó una muestra de
100 pares de nodos en la componente grande y se
obtuvo el valor 7.64. La mediana de la muestra fue 7,
la menor distancia fue 4 y la mayor fue 11.
2. Coeficiente de Clustering: Fracción de ternas
ordenadas de nodos a,b,c en las cuales la arista ab y
bc están presentes cuando ac lo está. En otras
palabras, cuán frecuentemente son adyacentes dos
vecinos de un nodo.
C = 1308045/9125801 = 0.14.
Luego, C se ajusta a un modelo S-W.
62
La Topología de Redes Reales: Números de Erdös (16)
Números de Erdös
Erdös (1919-1996), el matemático actualmente con
más publicaciones y con más co-autores es el origen
de una red y tiene número de Erdös 0, sus co-autores
tienen número 1, los co-autores de éstos tiene
número 2, y así sucesivamente.
Veamos la distribución de los números de Erdös
considerando solamente aquellos autores que han
colaborado y que además están a una distancia finita
de Erdös. Existen (a la fecha del estudio) 268.000 de
estos autores.
63
La Topología de Redes Reales: Números de Erdös (17)
Número de Erdös
Número de Autores
0
1
1
504
2
6593
3
33605
4
83642
5
87760
Media:4.65
6
40014
Mediana : 5
7
11591
8
3146
Dante Chialvo
9
819
tiene número 4
10
244
11
68
12
23
13
5
64
La Topología de Redes Reales: Números de Erdös (18)
¿ Qué pasa si la raíz no es Erdös ?
Si fuese Jerry Grossman, se tendría una mediana de 6
y una media de 5.71 y el rango crece a 15.
Si fuese Arturo Robles, la mediana sería 15, y la media
es 15.06.
Se han estudiado también los números de Erdös de
segunda clase, donde solamente se aceptan coautorías entre 2 personas.
Con ésto, por ejemplo, Yolanda Debose pierde su
número de Erdös igual a 1 (Erdös, Hobbs, Debose),
pero no Hobbs.
65
Modelos de Redes
Existen tres paradigmas de modelos:
- Modelos de Grafos aleatorios: se usan en
varios campos y sirven como benchmarks para
modelación y estudios empíricos.
- Modelos Small Worlds: se sitúan entre redes
regulares altamente clustered y grafos aleatorios.
- Modelos con Distribución de grado de ley
de potencias: se enfocan sobre redes dinámicas,
buscando ofrecer una teoría universal de
evolución en redes.
66
Análisis de algunos modelos
Modelo de Watts-Strogatz (W-S)
Un primer resultado exitoso corresponde al
modelo de Watts-Strogatz. Se introduce un
parámetro que interpola entre red regular y
un grafo aleatorio, de modo de tener altos
coeficientes de clustering y pequeños caminos
más cortos.
67
Modelo de Watts-Strogatz (1)
Procedimiento de diseño de la red
(1) Comenzar con Orden: comenzar con una red tipo
anillo con n nodos en la cual cada nodo está
conectado a sus primeros k vecinos (k/2 a cada lado).
Para efectos de tener siempre una red esparsa y
conexa, se supone que n>>k>>ln(n)>>1.
(2) Aleatorizar: reconectar cada arista de la red con
probabilidad p, y de modo de eliminar autoloops y
aristas paralelas. Este proceso introduce p·n·k/2
aristas de largo alcance. Manipulando p estamos entre
orden (p = 0) y aleatoriedad (p = 1).
68
Modelo de Watts-Strogatz : Figura W-S (2)
P=0
P=1
69
Modelo de Watts-Strogatz (3)
El modelo de W-S tiene sus orígenes en sistemas
sociales en los cuales la mayoría de la gente son
conocidos con sus vecinos y colegas. Sin embargo, la
gran mayoría de las personas tiene amigos lejanos,
de otros tiempos, o que viven lejos.
Notamos que para una red anillo, p = 0:
l(0)  n/2k >>1 y C(0)= 3(k-2)/4(k-1)  ¾.
Luego, l(0) es función lineal de n y C es grande.
En el otro extremo, para una red aleatoria:
p tiende a 1 ⇒ l(1)  ln(n)/ln(k) y C(1)  k/n
Ahora l es función logarítmica de n y C decae con n.
70
Modelo de Watts-Strogatz (4)
Veamos que ocurre con la longitud de
caminos promedio l(p), clustering C(p) y
distribución de grado, en función de la
probabilidad de conexión p.
Longitud de Caminos
La longitud de los caminos depende de la
fracción p de aristas reasignadas.
71
Modelo de Watts-Strogatz: l (5)
p pequeño ⇒ l es una función lineal del tamaño del
sistema.
p grande ⇒ l es una función logarítmica del tamaño
del sistema.
La caída brusca de l se debe a la aparición de atajos.
Basta solamente algunos para esta caída.
El estudio del valor de l = l (n,p) está bién estudiado
aún cuando no es trivial. La relación obtenida se ha
confirmado por varias simulaciones numéricas.
Se confirma crecimiento lento de l.
72
Modelo de Watts-Strogatz: C (6)
Clustering
Para p = 0, C no depende de n, depende solamente
de su topología.
Cuando se aleatorizan las conexiones, C
permanece cercano a C(0) aún para valores
relativamente grandes de p.
Se define un nueva fórmula para C, C’, pero muy
parecida a la anterior. Se obtiene:
C’(p) = C’(0)·(1-p)3
73
Modelo de Watts-Strogatz: C (7)
Watts y Strogatz encontraron que existe un intervalo
amplio para el cual l(p) es cercano a l(1) aún cuando
C(p)>>C(1).
En este intervalo, coexisten l pequeño y C grande,
de acuerdo a los datos reales sobre la mayoría de los
tipos de redes comentadas.
74
Modelo de Watts-Strogatz: C (9)
El gráfico siguiente muestra la distribución de
grados del modelo W-S para k = 3 y varios valores
de p. También se muestra la distribución de grado
de un grafo aleatorio con los mismos parámetros.
•La topología de la red es relativamente homogénea con
grados parecidos de los nodos.
75
Modelo Redes Libres de Escala
Modelos aleatorio y W-S no pueden reproducir
el hecho que la distribución de grados siga una
ley de potencias.
Problema: ¿cuál es el mecanismo responsable
por la aparición de las redes libres de escala ?
R.: El dinamismo es fundamental y la topología
es un subproducto.
76
Modelo Redes Libres de Escala (1)
Modelo de Barabasi-Albert (B-A)
▪ Hasta ahora los modelos vistos asumen que
la red se forma con un número fijo de nodos n
y que después se altera la estructura de la
red cambiando las conexiones.
Sin embargo, las redes reales son sistemas
abiertos que crecen a través de nuevos nodos
y conexiones.
77
Modelo Redes Libres de Escala (2)
▪ También los modelos vistos asumen que p es
independiente de los grados de los nodos.
Esto es, las nuevas aristas se conectan al
azar.
▪ La mayoría de las redes reales exhiben
conexión preferencial, de modo que la
probabilidad de conexión a un nodo en la
red depende del grado del nodo.
H. Simon [1950]: el rico llega a ser más rico
D. S. Price [1965]: ventaja acumulada (red de citaciones)
78
Inmunidad en Redes
Inmunidad en redes: Tolerancia a Errores y Ataques
Aspectos topológicos de la robustez asociados a
remoción de arcos y/o nodos.
Robustez está asociada a la topología de la red.
Una red es robusta si contiene un cluster gigante
conteniendo la mayoría de los nodos aún después de la
eliminación de un cierto número de nodos.
Se sabe que redes libres de escala son más robustas
que redes aleatorias contra fallas aleatorias en los
nodos, pero son más vulnerables cuando las fallas
ocurren en los nodos más conectados.
79
Descargar

CONCEPTOS Y PROBLEMAS EN REDES COMPLEJAS