Download 5_RBN

Robutness of Scale-free
Networks
Random failure fc =1
s
(2 < g  3)
Attack = progressive failure of the most
connected nodes fc <1
fc
1
Internet maps
R. Albert, H. Jeong, A.L. Barabasi, Nature 406 378 (2000)
Epidemic spreading on SF networks
Natural computer virus
•DNS-cache computer viruses
•Routing tables corruption
Internet topology
Data carried viruses
•ftp, file exchange, etc.
Computer worms
•e-mail diffusing
•self-replicating
Epidemiology
E-mail network topology
Air travel topology
Mathematical models of epidemics
Coarse grained description of individuals and their state
•Individuals exist only in few states:
•Healthy or Susceptible * Infected * Immune * Dead
•Particulars on the infection mechanism on each individual are neglected.
Topology of the system: the pattern of contacts
along which infections spread in population is
identified by a network
•Each node represents an individual
•Each link is a connection along which the
virus can spread
SIS model:
•Each node is infected with
rate n if connected to one or
more infected nodes
•Infected nodes are
recovered (cured) with rate d
without loss of generality d =1
(sets the time scale)
•Definition of an effective
spreading rate l=n/d
r
Absorbing
phase
Active phase
Finite prevalence
Virus death
lc
r=prevalence
The epidemic threshold is a general result
The question of thresholds in epidemics is central
(in particular for immunization strategies)
l
•Non-equilibrium phase
transition
•epidemic threshold =
critical point
•prevalence r =order
parameter
What about computer viruses?
• Very long average lifetime (years!)
comparedr to the time scale of the antivirus
Absorbing
Active phase case
• Small prevalence
in the endemic
phase
Finite prevalence
Virus death
lc
l
Computer viruses ???
Long lifetime + low prevalence = computer viruses always tuned
infinitesimally close to the epidemic threshold
???
SIS model on SF networks
SIS= Susceptible – Infected – Susceptible
Mean-Field usual approximation: all nodes are
“equivalent” (same connectivity) => existence of
an epidemic threshold 1/<k> for the order
parameter r (density of infected nodes)
Scale-free structure => necessary to take into
account the strong heterogeneity of
connectivities => rk=density of infected nodes
of connectivity k
=>epidemic threshold
<k>
l c= 2
<k >
Epidemic threshold in scale-free networks
<k>
=
lc
<k2>
<k2>  
l c 0
Order parameter
behavior in an
infinite system
Rationalization of computer virus data
•Wide range of spreading rate with low prevalence (no tuning)
•Lack of healthy phase = standard immunization cannot
drive the system below threshold!!!
Results can be generalized to generic -g
scale-free connectivity distributions P(k)~ k
•If 2 < g  3 we have absence of an epidemic
threshold
and no critical behavior.
•If 3 < g  4 an epidemic threshold appears, but
it is approached with vanishing slope (no criticality).
•If g > 4 the usual MF behavior is recovered.
SF networks are equal to random graph.
Redes booleanas aleatorias
inspiradas en las redes genéticas.
Gen activo: produce proteína.
Gen inhibido: no produce
proteína.
La presencia o ausencia de
ciertas proteínas regulan la
activación o inhibición de
ciertos genes.
Red genética: conjuntos de
genes auto-regulados.
Modelo fago Lambda:
dx
n
 n
x
n
dt   y
dy
n
 n
y
n
dt   x
¿Qué podemos hacer cuando tenemos miles de genes acoplados?
Redes booleanas aleatorias
Random Boolean Networks
(RBN)
Stuart Kauffman 70’s
Definición de RBN
0 = inactivo
K genes
input
2 posibles valores:
gen
(autómata)
1 = activo
xi (t  1)  f i ( xi1 (t ), xi2 (t ),..., xik (t ))
Donde f es una función booleana
de K argumentos booleanos.
Ej. de RBN con K=3 y N=10
PARÁMETROS:
N = nº autómatas ~ genes
K = conectividad
Autónomo
Síncrono
Quenched
N
FK : {0,1}  {0,1}
Estado global en t
t
1
t
Estado global en t  1
t 1
1
t
t 1
x3
x
x2

0
0
0
1

0
1
0
1
0

0
0
0
0
1
1

1
1
1
1
0
0

0
1
1
1
0
1

0
1
1
1
1
0

0
1
1
1
1
1

1
1
1
x3
x
x2
0
0
0
0
0
0
t 1
N, K  N
N
*
FK  ( f1 , f 2 ,..., f N )
K
f i : {0,1}  {0,1}
t 1
 FK (x )
t 1
i
 f i ( x , x ,..., x )
x
x
t
t
i1
t
i2
t
iK
Ejemplo con N=13 y K=3
Las 213 = 8192 configuraciones globales en 15 cuencas
de atracción disjuntas del ejemplo de RBN anterior.
Cuenca anterior
Transición orden-desorden
Orden (K=1)
Kc=2
Desorden (K=3)
Enfoque ingeniero
versus
enfoque matemático
N T ~ Ng
Enfoque ingeniero
versus
enfoque matemático
Propiedades generales: emergencia y evolución.
Generalización de las RBN
Ricard V. Solé and Bartolo Luque.
Phase transitions and antichaos
in generalized Kauffman networks.
Physics Letters A 196 (1995)
pp. 331-334.
K  Conectivid ad media
p  Sesgo
1
Kc 
2 p(1  p)
Núcleo estable
Método de la distancia
(teoría de perturbaciones)
Maxent
(métodos variacionales)