Tolerância a Erros
e Ataques em Redes
Complexas
Apresentado por Walfredo Cirne
Baseado nos slides de Patrício de Alencar Silva
Agenda
• Tipos de Redes
• O Diâmetro da Web
• Tolerância a Erros e Ataques
• Aplicações
• Conclusões
Agenda
• Tipos de Redes
• O Diâmetro da Web
• Tolerância a Erros e Ataques
• Aplicações
• Conclusões
Redes
• Abstraindo dos detalhes, redes
(grafos) são uma coleção de nós
conectados por links
• Redes modelam vários sistemas
diferentes
– Internet
– Web
– Célula
– Sociedade
Conectividade
• A conectividade de um nó é o número
de links do nó
• A distribuição de conectividade
diferencia entre os dois grandes
tipos de redes
– Redes homogêneas
– Redes heterogênea
• Definições:
– P(k) é a probabilidade de um nó estar
conectado com outros k nós da rede
– <k> é a média de P(k)
Tipos de Redes
• Homogênea
– Todos os nós têm (estatísticamente)
o mesmo número de links
– P(k) é uma distribuição de Poisson
• Heterogênea
– A maioria dos nós têm poucos links
– Uns poucos nós (hubs) têm muitos
links
– P(k) é uma power-law: P(k) = ck-
Network Types
Poisson (Média = 10)
0,14
0,12
0,1
0,08
0,06
0,04
0,02
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
Power-Law P(k)  k
-2
0,45
0,4
0,35
0,3
0,25
0,2
0,15
0,1
0,05
30
28
26
24
22
20
18
16
14
12
10
8
6
4
2
0
Redes Homogêneas ×
Redes de Livre Escala
rodovias
rotas aéreas
Redes Heterogêneas
• Rede dos amigos
• Rede sexual
• Rede dos co-autores em paper
• Rede dos aeroportos
• Rede das moléculas bioquimicas
• Web
• Internet
Modelos de Rede
• Erdös-Rényi  Homogênea
– Cada link possível existe com uma
probabilidade p
• Livre de escala  Heterogênea
– A rede cresce um nó de cada vez
– A probabilidade p de que o novo nó
se conecta ao nó i é proporcional ao
número de nós que i já possui
– Preferential attachment
Redes de Livre Escala
Agenda
• Tipos de Redes
• O Diâmetro da Web
• Tolerância a Erros e Ataques
• Aplicações
• Conclusões
A Web
• A Web é um grande
grafo direcionado
• Documentos são nós
• URLs são links
• A topologia do
grafo determina a
eficiência na
localização da
informação
• Como o grafo é
direcionado, temos
vários continentes
“continentes” na
Web
The Fragmented Web (Linked)
Modelando a Web
• Como quantificar o grau de
conectividade na web, com
aproximadamente 800 milhões de
documentos?
• Um robô (crawler) obteve uma amostra
da Web
• Distribuição da conectividade dos nós
amostrados sugere uma rede power law
• Usando uma amostra, estrapolou-se a
mesma distribuíção para a Web inteira
O Diâmetro da Web
• O diâmetro é média da distância mínima
entre dois nós quaisquer na rede, medida
pelo somatório dos links intermediários
• Pela constantes obtidas na amostragem,
chega-se a:
<d>(N) = 0.35 + 2.06log(N)
• Daí estima-se que o diametro da Web seja:
<dwww> =~ 19 links
• Note que o incremento de 1000% na Web
aumentaria o diametro de 19 para apenas 21
links
Agenda
• Tipos de Redes
• O Diâmetro da Web
• Tolerância a Erros e Ataques
• Aplicações
• Conclusões
Tolerância a Erros e
Ataques: uma Análise
• Erros tendem a aleatoriedade
• Ataques são específicos a nós de
maior importância
– Em Redes Homogêneas, tanto faz,
tudo é a mesma coisa...
– Em Redes Heterogêneas...
Falha
Falha
Falha
Ataque!
Ataque!
Ataque!
Impacto no Diametro
Impacto na Fragmentação
• S é a fração dos nós que fazem parte do maior cluster
• <s> é a média dos nós que pertencem aos clusters
“secundários”
Impacto na Fragmentação
Uma pequena crítica
• Esta análise assume que a
dificuldade de atacar um nó é o
mesmo para todos os nós
• Mas os nós mais importantes
tendem a ser melhor defendidos
• Assim, atacar um hub deveria ser
mais díficil (que seria
naturalmente modelado como
custando mais)
Agenda
• Tipos de Redes
• O Diâmetro da Web
• Tolerância a Erros e Ataques
• Aplicações
• Conclusões
Aplicações
• A análise da dinâmica de redes
complexas é útil à inúmeros sistemas,
incluindo:
–
–
–
–
–
–
–
–
Web, Internet, comunicação no geral
Desenvolvimento celular
Sistemas políticos
Panorama econômico
Ecossistemas
Orkut
Direito
...
Aplicações
• Projeto de novas
drogas contra o
câncer
• Vírus, bactérias
resistentes
• Tratamentos
quimioterapêuticos
• Atingir o cerne do
desenvolvimento de
doenças infectocontagiosas...
Aplicações
• Durante longas
eras, a natureza
lida com a autoorganização de
seus ecossistemas
• É necessário
estudas seus
padrões de
“tolerância a
falhas”
• Computação
Bioinspirada
Agenda
• Tipos de Redes
• O Diâmetro da Web
• Tolerância a Erros e Ataques
• Aplicações
• Conclusões
Conclusões
• Avanços dos estudos de organização de
redes complexas revelam apenas a
ponta do iceberg
• Redes complexas pode ser fundamentais
no entendimento de sistemas complexos
– Precisamos ir além da arquitetura
conhecida e descobrir as leis que
governam processos dinâmicos, como o
tráfico na Internet ou a cinética de
reações celulares
Linked
• Tudo isso esta
explicado no livro
Linked
• Leitura fortemente
recomendada