Embed Size (px)
Citation preview
Redes complexas:como as "coisas" se conectam
Prof. Antonio Augusto (Guto)IC/UFF
Áreas de Atuação:Redes de Computadores e
Segurança de Dados
Área de Interesse:Qualquer tópico interessante e desafiador!
Palestra na disciplinaIntrodução à Computação
05 e 07 fevereiro 2013 – Niterói
Algumas perguntas...
O que é uma rede?
O que é um grafo?
Como representamosum grafo?
E as redes?
O que são redes?
Vértice, nó, ator, ....
Arco, enlace,ligação, ...
Diferentes áreas, diferentes nomes....
“Uma rede é um conjunto de vértices (ou nós) providos de alguma regra (ou padrão) que os conectam através de arestas (ou ligações).
O que são redes?
Vértice, nó, ator, ....
Arco, enlace,ligação, ...
Diferentes áreas, diferentes nomes....
“Uma rede é um conjunto de vértices (ou nós) providos de alguma regra (ou padrão) que os conectam através de arestas (ou ligações). Muito burocrática!
Redes: outra definição
Abstração que permite codificar relacionamentos entre pares de objetos
Redes: outra definição
Abstração que permite codificar relacionamentos entre pares de objetos
Que objetos?
Redes: outra definição
Abstração que permite codificar relacionamentos entre pares de objetos
Que objetos?
Qualquer um! Ex. pessoas, países, páginas web, etc...
Redes: outra definição
Abstração que permite codificar relacionamentos entre pares de objetos
Que objetos?
Qualquer um! Ex. pessoas, países, páginas web, etc...
Que relacionamentos?
Redes: outra definição
Abstração que permite codificar relacionamentos entre pares de objetos
Que objetos?
Qualquer um! Ex. pessoas, países, páginas web, etc...
Que relacionamentos?
Qualquer um! Ex. amizade, língua falada, links, etc.Qualquer um! Ex. pessoas, países, páginas web, etc...
Redes: importância
Para que servem?
Abstração que permite entender características do relacionamentos entre pares de objetos
Como analisaressa abstração
Análise da rede
Uma figura vale mais do que mil palavras!!!
Nem sempre!
Algumas redes são “complexas”!
O que são Redes Complexas?
●Rede complexa é uma rede (grafo) comcaracterísticas topológicas não-triviais,
com padrões de conectividade (espacial etemporal) entre seus elementos que não
são nem puramente regularesnem puramente aleatórios
Redes Complexas é também...
Estudo abrangente de estruturas e funcionalidades em redes
Área de pesquisa emergente e multidisciplinar (física, matemática, computação, biologia, sociologia, etc)
Muitas questões fundamentais ainda em aberto.
Exercício: vejamos algunsexemplos de redes complexas
Quais os objetose relacionamentos?
Redes físicas?
malha aérea rede elétrica
Quais os objetose relacionamentos?
Redes físicas?
malha aérea rede elétrica
propagação dedoenças
Redes biológicas?
redes de neurônios
Redes tecnológicas?
chamadastelefônicas
Redes tecnológicas?
topologia internet
Redes tecnológicas?
topologia internet
Redes tecnológicas?
Aplicações P2P
Redes sociais?
co-autores
pessoas conhecidas
Redes sociais?
Estudo de Redes Complexas
Como estudar asredes complexas?
Resumo da estrutura da rede
Algumas caracterísiticas estruturais Ex., Tamanho, densidade, graus, distâncias, clusterização, etc.
Dão ideia geral da estrutura da rede
Características estruturais
Tamanho da rede
# de vérticas e arestas
Densidade
fração de arestas que o grafo possui
Grau (médio) dos vértices
# (médio) de conexões dos vértices
Distirbuição do grau
frequência relativa dos graus de todos os vértices
Distância (média)
menor caminho entre (todos) pares de vértices da rede
Clusterização
Fração de arestas entre vizinhos
Três características importantes
Small-World
Quantas vezes nos surpreendemos ao descobrirpoucos “saltos” para completos estranhos?
Small-World
A partir dos resultados do experimento pioneiro do psicólogo social Milgram (1967), dois indivíduos aleatoriamente escolhidos se “mostraram” muito próximos numa rede social
6 graus de separação
Popularizou o termo “Small-World”
Resultados em OSN são ainda menores
Amigo dos amigos
Amigo dos amigos
Qual a probabilidade de existência de uma aresta entre dois de meus vizinhos?
valor esperado para essa variável aleatória representa o coeficiente de clusterização
Efeito “meus amigos também são amigos”
Propriedade para diversas redes reais
roteadores na Internet, WWW
Ricos cada vez mais ricos
Abaixo a democracia!
Modelo gerador:
Comece com um número pequeno de vértices
Adicione um novo nó e o conecte a N diferentes nós que já estejam presentes no sistema
probabilidade de escolher um vizinho dependerádo grau do vizinho (Preferential Attachment)
nós com mais vizinhos serão escolhidoscom maior probabilidade
Abaixo a democracia!
Modelo gerador:
Comece com um número pequeno de vértices
Adicione um novo nó e o conecte a N diferentes nós que já estejam presentes no sistema
probabilidade de escolher um vizinho dependerádo grau do vizinho (Preferential Attachment)
nós com mais vizinhos serão escolhidoscom maior probabilidade
Qual o efeito disso?
Abaixo a democracia!
Ricos ficam cadavez mais ricos!
Pesquisa
E o que maishá de interessante?
Minhas pesquisa
1M usuários 100k swarms,alguns muito grandes
100M usuários,10M trans./mês
Minhas pesquisa
1M usuários
Como identificarSybil Atack?
Minhas pesquisa
100k swarms,alguns muito grandes
Podemos definirum sistema derecomendação
Minhas pesquisa
100M usuários,10M trans./mês
É possível definir umsistema de reputação?
Mensagem pra casa
RC é uma área de pesquisa relativamente nova
completou 10 anosMultidisciplinar (física, matemática, computação, biologia, sociologia, etc)
Tenta explicar diversas questões fundamentais, algumas ainda em aberto
Ex, por que tanta similaridadeentre redes tão diferentes?
Área importante devido à crescente abundância de dados (sobre quase tudo)
Se tiverem interesse em estudaras propriedades de conexões de
alguma coisa interessante,me avisem! :)
