Parte 4-B
Mais Exemplos
(específicos - redes de computadores)
1
Exemplos
• Nível de interconectividade
• robustez em redes complexas
• Nível de aplicação
• rede de emails
2
Resiliência (Robustez)
•
•
Capacidade da rede de operar na presença de faltas
(tolerante a faltas)
•
Ocorrem em vértices ou arestas
Como avaliar a robustez da rede?
•
•
Métricas locais
•
•
impacto em um ou poucos vértices
ex. número de arestas para desconectar um vértice
qualquer
Métricas globais
•
•
impacto na rede
ex. tamanho do componente gigante
3
Resiliência (Robustez)
• Baseando-se no artigo “Error and attack
tolerance of complex networks”(Albert et al, Nature
406, 2000)
• Foco: Métrica global
• Análise do diâmetro da rede
• Mudanças na topologia da rede
• Tamanho do componente gigante
• Tamanho médio dos componentes
Tipos de Faltas
• Que tipos de faltas nós e arestas podem
apresentar?
• Aleatórias
• uniforme: todos possuem a mesma prob.
de falta
• não-uniforme: probabilidade pode
depender de alguma característica do nó,
por exemplo
• Determinísticas
• faltas seguem ordem específica entre os
nós p.ex. baseada no grau decrescente dos
nós
Tipos de Faltas
• Faltas aleatórias (falha)
• ex. roteador pifou
• Faltas determinísticas (ataque)
• ex. roteador atacado
Faltas e Robustez
• Robustez da rede no caso de
• faltas aleatórias (distribuição uniforme)
• faltas determinísticas (ordenadas pelo grau)
• Em redes seguindo diferentes modelos
• modelo G(n,p)
• modelo BA
Faltas no Modelo G(n,p)
• Faltas aumentam (levemente) a distância média
entre os nós
• Faltas aleatórias e determinísticas tem impacto
similar
Modelo G(n,p):
impacto similar de
faltas aleatórias e
determinísticas
com aumento
pequeno da
distância
Faltas no Modelo BA
• Faltas aleatórias não se parecem com faltas
determinísticas
• Faltas aleatórias (falhas): pouco impacto;
Faltas determinísticas (ataque): muito impacto
Faltas determinísticas
no Modelo BA:
5% de nós removidos,
distância média dobrou!
Faltas aleatórias
no Modelo BA:
5% de nós removidos,
distância média não variou!
8
Análise do
Componente Gigante
• Tamanho relativo do componente gigante (CG)
• fração dos nós da rede pertencentes ao CG
• representado por S
• Tamanho médio dos demais componentes
• representado por <s>
Modelo G(n,p)
• Falhas/ataques reduzem
CG em comportamento
similar
• Redução do CG aumenta
tamanho médio dos
demais componentes
• Após eliminação do CG
demais componentes se
fragmentam
Rede fragmentada!
Modelo BA
• Sob falhas redução linear
do CG
demais componentes
aumento suave da média
• Sob ataques CG se desfaz
mais rapidamente do que
G(n,p)
demais componentes se
fragmentam após eliminação
do CG
Rede fragmentada!
Modelo BA
Distribuição de grau segue lei de potência
• Maioria dos nós
• Poucos nós
• Estes tem pouca
• Estes interconectam
• Tolerante a falhas
• Vulnerável a ataques
tem grau baixo
importância na
robustez da rede
aleatórias
tem grau alto
a rede
direcionados
Modelo BA
Rede Scale-Free
• Alta tolerância a falhas aleatórias
• robustez é a base para a tolerância a
defeitos de muitos sistemas
complexos:
de sistemas celulares a sistemas
distribuídos de comunicação
• explica porque, apesar de problemas
frequentes no roteamento, raramente
há uma “queda” global da rede
Modelo BA
Rede Scale-Free
• Severamente vulnerável ataques
• no caso de redes biológicas, propriedade
favorável para o desenvolvimento de
remédios com o objetivo de combater
doenças (imunização)
• para redes de dados (Internet,
Web), ao
contrário do esperado, robustez a ataques é
muito pequena
Redes Reais
• Grafos Internet (AS ) e
Web
• redes seguem lei de
potência (grau)
• comportamento similar
ao modelo BA
• tolerante a falhas
aleatórias, vulnerável a
ataques
16
Programa de Verão LNCC 2011 - Minicurso Redes
Complexas
A. P. C. da Silva (UFJF), N. Alves Jr. (CBPF) & Artur
Exemplos
• Nível de interconectividade
• robustez em redes complexas
• Nível de aplicação
• rede de emails
Rede de Emails
• Nós correspondem a endereços de
email
• Arestas correspondem à troca de
mensagem entre dois endereços
Rede de Emails
• Qual a topologia da rede?
• Podemos usar o conhecimento da topologia
para melhorar serviços?
• Ex. combater disseminação de vírus?
• Podemos distinguir o comportamento
de usuários?
• Ex. detectar spam?
19
Cenário
• Baseado no artigo “Scale-free topology of e-mail
networks”
[Ebel et al, Physical Review E, 66, 2002]
• Registro dos emails de ou para estudantes da
Universidade de Kiel, Alemanha (112 dias)
• Rede com 59812 nós e grau médio de 2.88
• Componente gigante com 56969 nós e diversos
clusters com menos de 150 nós
20
Propriedade Scale-Free
• Grau considerando
somente os
estudantes
(conhecimento do
grau exato)
• Grau segue lei de
potência com
γ = 1.32 ± 0.18
21
Propriedade Small-World
• Alta clusterização
(comparada com grafo aleatório)
•
•
•
Cemail = 3.44x10-2 (método I)
Cemail = 3.15x10-3 (método II)
Cemail ≫ Crandom
Crandom = 4.82x10-5
• Diâmetro pequeno
(comparada com tamanho da rede)
•
•
Demail = 4.95
Drandom = 10.10
CG com 56969
nós
Identificando essas
características
• Segurança: identificação de hubs e controle
de imunização contra vírus (bem similar a
epidemiologia em vida real)
• Marketing: identificação de comunidades de
usuários (rede social), de usuários mais
influentes na difusão de informação...
otimização de ações de marketing
(pode ser usado para o mal...)
Exemplos
• Nível de interconectividade
• robustez em redes complexas
• Nível de aplicação
• rede de emails
Apenas dois exemplos de aplicação
de redes complexas em redes de computadores....
Muitos outros existem.
Parte 5
Considerações finais
Alguns livros relacionados...
Divulgação
científica!
26
Mais técnicos...
Coletânea de artigos
clássicos / influentes
Específico
em
Dinâmica!
Conceitos de
Redes
complexas
aplicados à
Internet
27
+ muitos
artigos!!!!!
Trabalhos em
andamento...
• Difusão e busca em redes considerando a
dinâmica do sistema modelado
Análise da Disseminação de Informação em
Redes de Comunicação Considerando Dinâmica
Abrão Guimarães, Alex Borges Vieira, Ana Paula
Couto Silva – WP2P/ SBRC 2012
Trabalhos em
andamento...
• Caracterização dinâmica de comunidades em
sistemas P2P-TV
Caracterização de Nodos Estáveis no SopCast
Considerando Dinâmica
Francisco Henrique Ferreira,Ana Paula Couto
Silva, Alex Borges Vieira – WP2P/ SBRC 2012
Trabalhos em
andamento...
• Análise da correlação de medidas de
centralidade em grafos dinâmicos
Colaboração com Alex Borges (UFJF) e Daniel
Sadoc (UFRJ)
Revisitando os
Objetivos
• Visão geral da área de redes complexas
• em particular quando aplicada a redes de
computadores e sistemas distribuídos
• Despertar interesse para
• cooperações