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 [125]
6
1
4
2
5
7
l17=4 [1346  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