Redes Complexas Carlos Felipe Saraiva Pinheiro orientador: Américo T. Bernardes Laboratório de...

Redes Complexas

Carlos Felipe Saraiva Pinheiroorientador: 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.

QuadrilhaJoão foi para os

Estados Unidos, Teresa para o convento, Raimundo morreu de desastre, Maria ficou para tia, Joaquim suicidou-se 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

SociedadeNós: indivíduos

Links: relações sociais (família/trabalho/amizade/ etc.)

S. Milgram (1967)

Redes Sociais: Muitos indivíduos com relações diversas de interação social entre si.

John Guare Six Degrees of Separation

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ényiredes 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

iiC

de viz.possíveis ligaçõesligações de no.

1

2

3

4

5

6

7

l15=2 [125]

l17=4 [1346 7]

… < l > = ??i

Distribuição de graus

Grau do sítio iki =: no de links

incidentes no nó iP(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

800 million documents (S. Lawrence, 1999)

ROBOT: collects all URL’s found in a document and follows them recursively

Nodes: WWW documents Links: URL links

R. Albert, H. Jeong, A-L Barabasi, Nature, 401 130 (1999)

k ~ 6

P(k=500) ~ 10-99

NWWW ~ 109

N(k=500)~10-90

Oque era esperado?

Oque foi encontrado:

Pout(k) ~ k-out

P(k=500) ~ 10-6

out= 2.45 in = 2.1

Pin(k) ~ k- in

NWWW ~ 109 N(k=500) ~ 103

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

What does it mean?Poisson distribution

Exponential Network

Power-law distribution

Scale-free Network

Airlines

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

(Faloutsos, Faloutsos and Faloutsos, 1999)

Nodes: computers, routersLinks: physical lines

Internet

ACTOR CONNECTIVITIESNodes: actorsLinks: cast jointly

N = 212,250 actorsk = 28.78

P(k) ~k-

Days of Thunder (1990)Far and Away (1992)Eyes Wide Shut (1999)

=2.3

Actors

RobustêsSistemas complexos mantêm suas funções mesmo sob erros e falhas

(células mutações; Internet queda dos servidores)

Falha de nó

fc

0 1Fração de nós removidos, f

1

S

Robustês das redes scale-free

1

S

0 1ffc

Ataques

3 : fc=1(R. Cohen et al PRL, 2000)

Falha

Tolerância de danos devido à

topologia

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