Engenharia de Computação e Informação
UFRJ
Redes de Computadores
II – 2009/2
REDES COMPLEXAS
Professores:
Luis Henrique
Otto
Rafael Dahis
O que é uma rede ?

Conjunto de Entidades conectadas por Relações
O que é uma rede ?


Conjunto de Entidades conectadas por Relações
Na matemática...
G
=(V,E)
 Euler e as pontes de Konigsberg
 Como percorrer a cidade sem repetir
as pontes?
Grafos

Inicialmente...
 Estudos
de redes pequenas
 Análises visuais
 Preocupação com questões micro
Grafos

Inicialmente...
 Estudos
de redes pequenas
 Análises visuais
 Preocupação com questões micro
Qual o vértice
central?
Grafos

Inicialmente...
 Estudos
de redes pequenas
 Análises visuais
 Preocupação com questões micro
Qual o vértice
com maior grau?
Grafos

Inicialmente...
 Estudos
de redes pequenas
 Análises visuais
 Preocupação com questões micro
Qual o “pontoúnico-de-falha”?
Redes Complexas

O mundo ficou mais complexo ?
Redes Complexas

O mundo ficou mais complexo ?
 Nossos
métodos de coleta, armazenamento e
processamento que evoluíram
 Grafos maiores podem ser estudados...
Redes Complexas
Qual o vértice
central?
Qual o vértice
com maior grau?
Qual o “pontoúnico-de-falha”?
Redes Complexas

E agora ?
 Viés
estatístico
 Visualização como um dos grandes desafios
Análise de Redes Complexas - Objetivos



1 – Análise estatística e verificação de propriedades
conhecidas
2 – Formulação de modelos de geração de grafos
semelhantes
3 – Estudo do comportamento da rede frente a certos
eventos
Adição / exclusão de um vértice
 Vírus
 Fluxo

Tipos de Redes

Redes Sociais
 Pessoas
conectadas por ...
Tipos de Redes

Redes Sociais
 Músicos
de Jazz conectadas por Parcerias
Tipos de Redes

Redes Sociais
 Pesquisadores
conectadas por Colaboração
Tipos de Redes

Redes Sociais
 Usuários
conectadas por Amizade Virtual
Tipos de Redes

Redes Biológicas
 Redes
que representam sistemas naturais
Tipos de Redes

Redes Biológicas
 Cadeias
Alimentares
Tipos de Redes

Redes Biológicas
 Redes
de Neurônios
Tipos de Redes

Redes Biológicas
 Caminhos
 Vértices
Metabólicos
são substratos / produtos de reações
Tipos de Redes

Redes de Informação
 Entidades
= representam informações
 Relacionamentos = proximidade de informações
Tipos de Redes

Redes de Informação
 Redes
de Conceitos
Tipos de Redes

Redes de Informação
 Redes
de Preferências
Tipos de Redes

Redes de Informação
 Grafo
da Web
Tipos de Redes

Redes Tecnológicas
 Feitas
pelo homem para distribuição de produtos ou
recursos
Tipos de Redes

Redes Tecnológicas
 Redes
de Ligações Telefônicas
Tipos de Redes

Redes Tecnológicas
 Internet
Tipos de Redes

Redes Tecnológicas
 Internet
Tipos de Redes

Redes Tecnológicas
 Redes
de Transporte
Propriedades das Redes Complexas

Efeito Small-World
 Experimento
 300
de Milgram
cartas
 De diversas cidades distantes, para Boston
 25% das cartas chegaram
 “Seis graus de separação”
Propriedades das Redes Complexas

Efeito Small-World
 Conceito
de distância
 Número
de arestas percorridas
 Peso pode ser contabilizado
 Distância

média geodésica
Média das distâncias entre todos pares de vértices
Propriedades das Redes Complexas

Transitividade
 Dois
amigos meus tem muita chance de serem amigos
Propriedades das Redes Complexas

Transitividade
 Dois
amigos meus tem muita chance de serem amigos
Propriedades das Redes Complexas

Distribuição de Graus
 Pk
= probabilidade do grau ser maior que k
 Lei
de Potência
Propriedades das Redes Complexas

Distribuição de Graus
Propriedades das Redes Complexas

Resiliência
 Capacidade
de manter a conectividade, à medida que
vértices são removidos
 Pode ser expresso em função da distância média
 Diferentes maneiras de se retirar vértices
Propriedades das Redes Complexas

Resiliência
 Capacidade
de manter a conectividade, à medida que
vértices são removidos
 Pode ser expresso em função da distância média
 Diferentes maneiras de se retirar vértices
 Internet


Retiradas aleatórias -> pouco efeito
Retiradas especificas -> catastrófico
Propriedades das Redes Complexas

Padrões de Ligações
 Vértices
podem ter características
Propriedades das Redes Complexas

Padrões de Ligações
 Vértices
podem ter características
Propriedades das Redes Complexas

Padrões de Ligações
 Vértices
podem ter características
 As arestas podem depender disso...
Propriedades das Redes Complexas

Estruturas de Comunidade

Clusterização = encontrar grupos
 Distância
entre vértices de um mesmo grupo é pequena
 Distância entre grupos é grande
Propriedades das Redes Complexas

Estruturas de Comunidade
 Experimento
da escola
Propriedades das Redes Complexas

Estruturas de Comunidade
 Experimento
da escola
Estudos de Caso – Topologia da Internet

Dois níveis:
Estudos de Caso – Topologia da Internet

Relação de leis de potência
 Grau
x freqûencia de um grau
 Distância x vizinhança
Estudos de Caso – Topologia da Internet

Internet como fenômeno “Small-World”
 Alta
clusterização
 Distância entre quaisquer dois vértices é pequena
OBRIGADO !


Referências Principais
[1] NEWMAN, M.E.J.; The structure and function of complex networks, SIAM
Review 45, 167–256 (2003).
[2] NEWMAN, M.E.J.; Models of the small world, J. Stat. Phys. 101, 819–
841 (2000).
[3] JIM, S.; BESTRAVOS, A.; Small-World Internet Topologies - Possible
Causes and Implications on Scalability of End-System Multicast, Technical
Report BUCS-2002-004, Boston University, 2002
[4] FALOUTSOS, M.; FALOUTSOS, P.; FALOUTSOS, C.; On Power-Law
Relationships of the Internet Topology, SIGCOMM 1999

Imagens: www.visualcomplexity.com.br
Perguntas e Respostas

1) Por que as Redes Complexas ganharam
popularidade há relativamente pouco tempo ? O
mundo tornou-se mais complexo ?
Perguntas e Respostas



1) Por que as Redes Complexas ganharam
popularidade há relativamente pouco tempo ? O
mundo tornou-se mais complexo ?
O mundo não se tornou mais complexo.
Com a evolução tecnológica, ficaram mais simples e
viáveis os processos de coleta de dados,
armazenamento dos dados e processamento de
algoritmos sobre estruturas de dados complexas e de
larga escala, como os que definem as redes complexas.
Perguntas e Respostas

2) Quais são os três principais objetivos dos estudos
em Redes Complexas?
Perguntas e Respostas

2) Quais são os três principais objetivos dos estudos
em Redes Complexas?



1 – Análise estatística e verificação de propriedades
conhecidas
2 – Formulação de modelos de geração de grafos
semelhantes
3 – Estudo do comportamento da rede frente a certos
eventos



Adição / exclusão de um vértice
Vírus
Fluxo
Perguntas e Respostas

3) O que é o efeito Small-World?
Perguntas e Respostas


3) O que é o efeito Small-World?
É o efeito que descreve o fato de que,
independente do tamanho da rede, a distancia
média entre quaisquer dois vértices da rede SmallWorld tende a ser pequena.
 Distância
do caminho médio é menor que a de um
grafo aleatório
 Coeficiente de clusterização é maior que o de um
grafo aleatório
Perguntas e Respostas

4) O que é a lei da potência e onde ela é utilizada
na análise de redes complexas?
Perguntas e Respostas



4) O que é a lei da potência e onde ela é utilizada na
análise de redes complexas?
A lei da potência relaciona duas medidas de modo que
uma é proporcional a outra elevada a um expoente
constante. Isso significa que enquanto uma delas cresce,
a outra cresce/descresce exponencialmente.
Exemplos:
Grau x frequência do grau
 Distância x vizinhança coberta por essa distância

Perguntas e Respostas

5) O que é o efeito de transitividade em um grafo?
Perguntas e Respostas


5) O que é o efeito de transitividade em um grafo?
A transitividade indica que dois vizinhos de um
vértice tem alta probabilidades de serem também
vizinhos entre si.