Redes evolutivas
EPS-UAM Curso de doctorado
Modelos de Conectividad
2005-2006
07/10/2015
Redes evolutivas
1
Más allá del modelo de
Barabási-Albert (BA) (I)





Leyes de potencias con exponente
variable (1-3)
Cutoffs exponenciales
Saturación para grado k bajo
Procesos subyacentes a conexión
preferencial
Coeficientes de agrupamiento altos
07/10/2015
Redes evolutivas
2
Más allá de BA (II)






Variantes de conexión preferencial
Crecimiento acelerado
Alteración de grafo: recableado
Crecimiento con restricciones
Competición
Origen de conexión preferencial
07/10/2015
Redes evolutivas
3
Conexión preferencial




Probabilidad de conexión lineal en BA
Influencia en distribución de grados k
Determinación experimental según
tiempo en que aparece nodo
Dependencia de probabilidad con k en
redes reales: ley de potencias (lineal o
sublineal)
07/10/2015
Redes evolutivas
4
Conexión preferencial:

conexión no lineal k



Kaprivsky et al.: Scale-free se destruye
Caso sublineal: distribución de grados
exponencial
Caso supralineal:



  2 : nodos con una rama y nodo ‘gel’
  2 : nodos con varias ramas (número
finito) y nodo ‘gel’
Caso lineal: exponente entre 2 e infinito
07/10/2015
Redes evolutivas
5
Conexión preferencial:
atracción inicial (I)



Dogorotsev et al.
Probabilidad no nula de conexión a
nodo aislado: (k )  A  k 
Modelo:


07/10/2015
Nuevo nodo
M ramas dirigidas desde nodo aleatorio a
nodo preferencial
Redes evolutivas
6
Conexión preferencial:
atracción inicial (II)


Atracción inicial no destruye scale-free
Se modifica exponente de distribución
de grados
  2  A/ m
07/10/2015
Redes evolutivas
7
Crecimiento



Grado medio constante en BA:
crecimiento lineal de número de nodos
y ramas
Redes reales: grado medio suele crecer
Crecimiento acelerado: número de
ramas a ritmo mayor que número de
nodos
07/10/2015
Redes evolutivas
8
Crecimiento acelerado:
Dogorotsev et al.
Nuevo nodo recibe n ramas de nodos
aleatorios (grafo dirigido)

 c0t nuevas ramas desde nodo aleatorio
a nodo preferencial (atracción inicial)
  controla crecimiento acelerado
 No se destruye scale-free, se modifica
exponente   1  1 /(1   )

07/10/2015
Redes evolutivas
9
Crecimiento acelerado:
Barabási y Albert




Nuevo nodo conectado con b nodos de
forma preferencial (BA)
Nuevas ramas (fracción a de existentes)
según conexión preferencial (producto
de grados)
Grado medio: <k>=at+2b
Grado crítico y doble ley de potencias
07/10/2015
Redes evolutivas
10
Alteración de elementos de
grafo



Redes reales con sucesos que cambian
grafo de conexión
Adición y eliminación de nodos y de
ramas
Recableado: sustitución de una rama
por otra
07/10/2015
Redes evolutivas
11
Alteración de grafo:
Albert y Barabási (I)




m0 nodos iniciales aislados
m<=m0 nuevas ramas con probabilidad
p, extremos aleatorio-preferencial
m recableados con probabilidad q, nodo
alternativo preferencial
Nuevo nodo con m ramas con conexión
preferencial, con probabilidad 1-p-q
07/10/2015
Redes evolutivas
12
Alteración de grafo:
Albert y Barabási (II)
Ley de potencias generalizada
P(k )  (k   )
 q umbral: P(k) exponencial
 P(k) se satura para k bajo
  entre 2 e infinito

07/10/2015
Redes evolutivas
13
Alteración de grafo:
Dogorotsev y Mendes





Developing/decaying networks
Creación/eliminación de c ramas en
cada paso
Conexión preferencial (proporcional a
producto de grados)
 1  c   c=0 es BA
Scale-free:   2  1 ;   1  2c
07/10/2015
1  2c
Redes evolutivas
2(1  c)
14
Restricciones al crecimiento


Envejecimiento y desaparición de nodos
(personas en redes sociales)
Número de ramas máximo para un nodo
(router de internet)
07/10/2015
Redes evolutivas
15
Restricciones al crecimiento:
Amaral et al.

Hay redes reales sin scale-free pero no
aleatorias



Exponencial
Ley de potencias con cutoff exponencial
Si nodo alcanza su límite de edad o de
número de ramas, nadie se puede
conectar a él: cutoff exponencial
07/10/2015
Redes evolutivas
16
Restricciones al crecimiento:
Dogorotsev y Mendes

Conexión preferencial según edad

(ki )  ki (t  ti )
   1 : scale-free
   1 : se aproxima a exponencial
07/10/2015
Redes evolutivas
17
Competición




Modelo BA: antigüedad es un grado
Grado de un nodo crece con ley de
potencias: ki  t  ;   1/ 2
Nodos más antiguos, más favorecidos
Redes reales: nodos jóvenes pueden
atraer muchos nodos nuevos
07/10/2015
Redes evolutivas
18
Competición:
Bianconi y Barabási




Fitness model
Cada nodo tiene fitness  i según una
distribución de probabilidad  ( )
Conexión proporcional a fitness
Distribución de grados es suma de leyes
de potencias, y dependen de  ( )
07/10/2015
Redes evolutivas
19
Competición:
Dogorotsev y Mendes





Herencia de ramas
Nuevo nodo como heredero de nodo
aleatorio
Hereda fracción c de ramas de ancestro
Distribución h(c)
No scale-free
07/10/2015
Redes evolutivas
20
Origen de conexión
preferencial: Copiado





Kleinberg et al., Kumar et al.
Nuevo nodo con m ramas
Con probabilidad p se conecta
aleatoriamente
Con probabilidad1-p a vecino de nodo
prototipo (aleatorio)
Scale-free con exponente entre 2 e
infinito
07/10/2015
Redes evolutivas
21
Origen de conexión
preferencial: Redirección




Krapivsky y Redner; equivalente al de
Kumar
Nuevo nodo se conecta con
probabilidad 1-r a nodo aleatorio i
Con probabilidad r se redirecciona rama
a ancestro de i
Scale-free
07/10/2015
Redes evolutivas
22
Origen de conexión
preferencial: Barrido





Vázquez
Nuevo nodo se conecta a i aleatorio
Con probabilidad p se conecta a vecinos
de i y así sucesivamente: breadth-first
Exponencial para p  pc  0.4
Ley de potencias (exponente aprox. 2)
para p superior a valor crítico
07/10/2015
Redes evolutivas
23
Origen de conexión
preferencial: conexión a ramas



Dogorotsev et al.
Nuevo nodo se conecta a extremos de
rama aleatoria
Semejante a BA
07/10/2015
Redes evolutivas
24
Ejercicios
1.
2.
Realizar un programa que genere
redes según alguno de los modelos
vistos
Inventar un modelo y realizar un
programa que genere redes de
acuerdo a él. Estudiar sus
propiedades.
07/10/2015
Redes evolutivas
25
Descargar

Redes evolutivas