Redes Complexas Carlos Felipe Saraiva Pinheiro orientador: Américo T. Bernardes Laboratório de Modelamento e Simulação Computacional DEFIS - UFOP REDEMAT Quadrilha João amava Teresa que amava Raimundo que amava Maria que amava Joaquim que amava Lili que não amava ninguém. Quadrilha João foi para os Estados Unidos, Teresa para o convento, Raimundo morreu de desastre, Maria ficou para tia, Joaquim suicidouse e Lili casou-se com J. Pinto Fernandes que não tinha entrado na história. Grafo Nó = personagem Arco = relação (amar) Grafo direcionado + Conecividade Grau de incidência k kin e kout Hub ou plexo Nó extremamente conectado Sociedade Nós: indivíduos Links: relações sociais (família/trabalho/amizade/ etc.) S. Milgram (1967) Six Degrees of Separation John Guare Redes Sociais: Muitos indivíduos com relações diversas de interação social entre si. Redes de comunicação Nós computadores roteadores satélites Links linhas telefônicas cabos ondas eletromagnéticas Problema do custo mínimo Logística Se tudo está em rede Devemos estudá-las topologia mecanismos propriedades Nova visão: Física: reducionismo partícula e distância Há sistemas em que: distância é irrelevante nem tudo interage Modelo Erdős-Rényi redes aleatórias N fixo Faz-se as ligações aleatoriamente Reinou por anos não descreve a maioria dos sistemas reais Redes Reais Mundo pequeno Por maior que seja a distância, há sempre um atalho six degrees to Kevin Bacon caminho médio l Compactação meus amigos são amigos entre si Coef. de compactação no.de ligações Ci ligações possíveis viz.de i 3 l15=2 [125] 6 1 4 2 5 7 l17=4 [1346 7] … < l > = ?? i Distribuição de graus Grau do sítio i ki =: no de links incidentes no nó i P(k) =: probabilidade de um nó ter k vizinhos Redes Aleatórias: Distribuição de Poisson Modelo (WS) Watts-Strogatz C(p) : clustering coeff. L(p) : average path length (Watts and Strogatz, Nature 393, 440 (1998)) World Wide Web Nodes: WWW documents Links: URL links 800 million documents (S. Lawrence, 1999) ROBOT: collects all URL’s found in a document and follows them recursively R. Albert, H. Jeong, A-L Barabasi, Nature, 401 130 (1999) Oque era esperado? k ~ 6 P(k=500) ~ 10-99 NWWW ~ 109 N(k=500)~10-90 Oque foi encontrado: out= 2.45 in = 2.1 P(k=500) ~ 10-6 NWWW ~ 109 N(k=500) ~ 103 Pout(k) ~ k-out Pin(k) ~ k- in J. Kleinberg, et. al, Proceedings of the ICCC (1999) Três classes principais de modelos ER (random graph) aleatórios; L peq.; C peq. P(k) é Poisson Small World WS om p adequado; L peq.; C gde. P(k) semelhante a ER Scale Free crescimento da rede; L peq.; C gde. P(k) ~ k - Redes SF Poucos com muito e muitos com pouco (Léo Jaime) Exemplos abundam: www, internet, citações, aeroportos, sexo, Hollywood,... Dinâmica Crescimento Conexão preferencial Ricos cada vez mais ricos Se uma das condições acima faltar, não se obtém uma rede SF Airlines What does it mean? Poisson distribution Exponential Network Power-law distribution Scale-free Network Rede sem escala faça você mesmo a sua Cresce um nó por vez Cada nó se liga a m nós conexão preferencial INTERNET BACKBONE Nodes: computers, routers Links: physical lines (Faloutsos, Faloutsos and Faloutsos, 1999) Actors ACTOR CONNECTIVITIES Nodes: actors Links: cast jointly Days of Thunder (1990) Far and Away (1992) Eyes Wide Shut (1999) N = 212,250 actors k = 28.78 P(k) ~k- =2.3 Robustês Sistemas complexos mantêm suas funções mesmo sob erros e falhas (células mutações; Internet queda dos servidores) 1 S fc 0 1 Fração de nós removidos, f Falha de nó Robustês das redes scale-free Falha Tolerância de danos devido à topologia 1 3 : fc=1 S 0 Ataques (R. Cohen et al PRL, 2000) fc f 1 Calcanhar de Aquiles erro ataque Exemplo Implicações das redes sem escala Computação Resiste a falha mas é vulnerável ao ataque Impossível erradicação de vírus Medicina Vacinar hubs é mais efetivo ? Eliminação de efeitos colaterais ? Identificar moléculas hub Negócios Evitar quebradeira em cascata Marketing
Download
