Download 5_RBN
Document related concepts
Transcript
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)