Buscar

introdução comunicação e redes

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você também pode ser Premium ajudando estudantes

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você também pode ser Premium ajudando estudantes

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você também pode ser Premium ajudando estudantes
Você viu 3, do total de 70 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você também pode ser Premium ajudando estudantes

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você também pode ser Premium ajudando estudantes

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você também pode ser Premium ajudando estudantes
Você viu 6, do total de 70 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você também pode ser Premium ajudando estudantes

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você também pode ser Premium ajudando estudantes

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você também pode ser Premium ajudando estudantes
Você viu 9, do total de 70 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você também pode ser Premium ajudando estudantes

Prévia do material em texto

BCM0506: Comunicação e Redes
Semana 1
Introdução
Santo André, Fevereiro de 2017
Roteiro da Aula
Parte 1 – Apresentação da Disciplina
Objetivos
Ementa
Metodologia
Avaliação
Cronograma
Referências
Parte 2 – Introdução e Motivação
2.1 – Sistemas Complexos
2.2 – Redes Complexas
2.3 – Redes no Mundo Real
2.4 – Classificações de Redes
Parte 1
Apresentação da Disciplina
Objetivo Geral
Conhecer e trabalhar com a área interdis-
ciplinar de Redes Complexas (ou Ciência 
das Redes ou Sistemas Complexos), envol-
vendo conceitos, aplicações, relacionamen-
tos, métodos e ferramentas.
Dentre as aplicações, será dado um destaque especial 
aos processos de transmissão e distribuição de in-
formação. 
Objetivos Específicos
Compreender os conceitos fundamentais de 
redes complexas, uma área interdisciplinar que 
envolve disciplinas como física, matemática, 
engenharia, computação, biologia, sociologia …
Conhecer a teoria dos grafos e sua aplicação 
nas redes complexas.
Conhecer os principais tipos de redes, como 
redes small-world e scale-free.
Conhecer aplicações dos conceitos em várias 
redes do mundo real, como redes tecnológicas, 
de informação, sociais e biológicas.
Conteúdo Programático
Introdução e motivação: contexto e aplicações
Teoria dos grafos
Leis de potência
Grafos aleatórios
Redes de mundo pequeno (small-world)
Redes sem escala (scale-free)
Redes de computadores, Internet e Web
Redes sociais (e redes sociais online)
Redes biológicas
Metodologia
Os slides das aulas, enunciados de atividades, notas 
e outras comunicações da disciplina serão publicados 
na aba da disciplina no Tidia, bcm0506: 
https://tidia4.ufabc.edu.br
Aulas expositivas
Apresentações auxiliadas com slides
Animações
Demonstrações com softwares 
Trabalhos individuais
Pesquisas de resultados científicos
Programação de problemas de redes complexas
Execução de softwares existentes e análise de resultados
Avaliação
Prova P1: 17 de março, peso 2 [2h] 
Prova P2: 19 de abril, peso 3 [2h] 
Prova PSub: 28 de abril [2h] 
Atribuição de Conceito Final (CF): Vide Tabela de 
Conversão
Prova Substitutiva (PSub): Apenas Para Quem Tiver 
Falta JUSTIFICADA na P1 ou na P2
Recuperação: feita por upgrade das tarefas T no 
conceito final. Se o aluno fez TODAS as tarefas 
de forma correta, então T=1 (recebe upgrade), 
senão T=0 (não recebe). Será aberta a TODOS 
os alunos (independente do conceito final). Data-
limite de entrega das Tarefas: 28/4/2017 (Postar 
no seu Escaninho do Tidia).
Cronograma de Aulas
Semana Aula Conteúdo
1 Apresentação e 
Introdução
• Apresentação da disciplina
• Introdução e Motivação 
• Sistemas Complexos
• Redes Complexas
• Redes no mundo real: tecnológicas, de 
informação, sociais e biológicas
2 Introdução à Teoria dos 
Grafos
• Conceito e definições básicas
• Histórico: Euler e o problema das pontes de 
Königsberg
• Representação de grafos
3 Algoritmos de Grafos • Busca em largura e profundidade
• Caminho mínimo
4
Leis de Potência
 (Power-Laws)
• Distribuições de probabilidade
• Leis de potência e escalas logarítmicas
• Interpretando as leis de potência
Cronograma de Aulas
Semana Aula Conteúdo
5
Tipos de Redes • Grafos aleatórios
6 Revisão e Prova P1 • Revisão para a P1
• Prova P1
7 Tipos de Redes
Redes de Computadores, 
Internet e Web
• Redes de mundo pequeno, Redes s/ escala
• Princípios de comunicação de dados
• Sinalização analógica e digital; transmissão 
serial e paralela, transmissão síncrona e 
assíncrona ( Será visto em BCM0504)→
8 Redes de Computadores, 
Internet e Web (cont.)
• Roteamento e o funcionamento da Internet
• A World Wide Web (WWW)
Cronograma de Aulas
Semana Aula Conteúdo
9
Centralidade
O programa GEPHI
• Centralidade
• Usando o GEPHI
10 Revisão para P2 OBS: os temas Operação simplex, half-duplex 
e full-duplex; ligação ponto a ponto e 
multiponto; multiplexação; modulação; 
comutação; distorção de sinais, foram todos 
substituído por “Revisão p/ P2”.
11 Revisão e Prova P2 • Prova P2
12 Vista da P2
Recuperação e Sub 28/8
• Vista da P2 + Revisão p/ Psub&Recuperação
• Prova Psub
• Data-limite p/ Entrega de Tarefas
Presença nas Provas
Será controlada com lista de presença e 
apresentação de Documento com Foto do Aluno.
Ficar atento para não assinar a lista no lugar de 
seus colegas.
Referências
Bibliografia Básica
Barabasi, A. L. “Linked: How Everything Is Connected 
to Everything Else and What It Means for Business, 
Science and Everyday Life”, New York: A Plume Book, 
2003.
Barabasi, A. L. “Linked: A Nova Ciência dos Networks: 
Como Tudo Está Conectado a Tudo e o que Isso 
Significa para os Negócios, Relações Sociais e 
Ciência”, São Paulo: Leopardo, 2009.
Newman, M., “The Structure and Function of Complex 
Networks”, Siam Review, Vol. 45, No 2, pp.167–256, 
2003.
Kurose, J. F.; Ross, K. W. Redes de computadores e a 
internet. 5ª ed. São Paulo: Addison Wesley, 2010, 614 p.
Referências
Bibliografia Complementar
Watts, D. J., “Six Degrees: The Science of a 
Connected Age”, New York: Norton, 2004. 
Boccalettia, S. et al., "Complex networks: Structure 
and dynamics", Physics Reports 424, pp. 175 – 308, 
2006.
Albert, R., Barabasi, A. L., “Statistical mechanics of 
complex networks”, Reviews of Modern Physics, Vol. 74, 
2002.
Costa, L. F. et al., “Characterization of Complex 
Networks: A Survey of measurements”, Europhysics 
Letters, 85, 2009.
CALDARELLI, Guido. Scale-free networks: Complex 
webs in nature and technology. Oxford, UK: Oxford 
University Press, 2007.
Parte 2:
Introdução e Motivação
Parte 2.1:
Sistemas Complexos
Sistemas Complexos
Sistemas complexos não são simplesmente 
sistemas “grandes” ou “complicados”.
Aparentemente não existe uma definição 
consensual sobre o que são sistemas complexos, 
mas existem algumas características comuns 
apresentadas por tais sistemas, com a qual a 
maioria dos pesquisadores concorda.
Sistemas Complexos: Definições
“Um sistema composto de um grande número de 
entidades, processos ou agentes que interagem 
entre si, cuja compreensão necessita do 
desenvolvimento de novas técnicas, como modelos 
não lineares e simulação computacional”.
[Advances in Complex Systems Journal] 
“Um sistema que pode ser analisado através de 
seus muitos componentes inter-relacionados, 
sendo que o comportamento de cada um depende 
do comportamento dos outros”.
Sistemas Complexos: Definições
“Um sistema que envolve um grande número de 
agentes que interagem, cujo comportamento 
agregado é não linear, ou seja, não pode ser 
derivado da soma dos comportamentos dos 
componentes individuais”.
“Um sistema composto de partes interconectadas 
que como um todo apresenta uma ou mais 
propriedades (comportamentos) que não são 
óbvias a partir das propriedades das partes 
individuais”.
Sistemas Complexos: Exemplos
Alguns exemplos
Colônias de formigas
Economias humanas
Estruturas sociais
Sistemas nervosos 
Células e seres vivos em geral
Infraestruturas de energia e comunicações
Internet
Muitos sistemas que interessam aos seres 
humanos são sistemas complexos.
Sistemas Complexos: 
Algumas Características
Redes dinâmicas
O dinamismo das ligações entre os componentes de 
um sistema complexo é importante.
Sistemas complexos podem ser aninhados
Economia é feita de organizações, que são feitas de 
pessoas, que são feitas de células (todos complexos).
Produção de fenômenos emergentes
Algumas propriedades somente podem ser 
compreendidas em um nível mais alto, como resultado 
das interações dos agentes.
Ex.: colônias de formigas ou cupins.
Sistemas Complexos: 
Algumas Características
Relacionamentos são não lineares
O efeito pode não ser proporcional à causa.
Uma pequena perturbação pode causar um grande 
efeito, um efeito proporcional ou nenhum efeito.
Relacionamentos com retroalimentação (feedback 
loops)
O efeito de um elemento é colocado de volta como uma 
entrada para o sistema.
Parte 2.2:
Redes Complexas
Redes
Uma rede é um conjunto de itens (vértices 
ou nós) com conexões entre eles(arestas)
Em termos matemáticos ou computacionais redes são 
chamadas de grafos.
Sistemas que assumem a forma de redes existem 
em grande quantidade no mundo.
Redes podem ser usadas para modelar problemas 
de várias áreas diferentes
“Nós” podem representar qualquer tipo de entidade.
“Arestas” podem representar qualquer tipo de 
relacionamento, concreto ou abstrato.
Redes: Exemplos
Internet e World Wide Web (www).
Redes sociais de amigos, conhecidos ou qualquer 
outro relacionamento entre indivíduos.
Redes organizacionais e redes de relacionamentos 
entre empresas.
Redes neurais (ou neuronais).
Redes metabólicas.
Teias alimentares.
Redes de distribuição, como vasos sanguíneos e 
rotas postais.
Redes de citações entre artigos.
O Estudo de Redes
O estudo das redes na forma da teoria dos grafos 
é um dos pilares fundamentais da matemática 
discreta
A solução de Euler para o problema das pontes de 
Königsberg é citada como o primeiro problema a ser 
resolvido com redes.
Euler inventou a teoria dos grafos para esse problema.
Redes sociais têm sido muito estudadas
Uso de questionários para saber quem tem um 
relacionamento com quem.
Questões de centralidade e conectividade.
As Pontes de Königsberg
Podem as 7 pontes ser atravessadas em uma única 
viagem, passando através de cada uma delas uma 
única vez, iniciando e terminando a caminhada no 
mesmo local? 
O Estudo de Redes
Nos últimos anos o estudo das redes ganhou um 
grande impulso
Pesquisa deixou de considerar grafos pequenos e 
propriedades de vértices ou arestas individuais.
Foco nas propriedades estatísticas dos grafos.
O motivo é a disponibilidade de computadores e 
redes de comunicação
Permitem coletar e analisar grandes quantidades de 
dados em pouco tempo.
Milhares, milhões ou até bilhões de vértices.
Contra dezenas ou centenas em pesquisas anteriores
Redes Complexas
Uma Rede Complexa é uma rede com 
características topológicas não triviais
Características que não ocorrem em redes “simples” tais 
como grafos aleatórios ou anéis (ring lattices).
Anel ou ring latticeGrafo aleatório
http://en.wikipedia.org/wiki/Complex_network
Redes “Simples” 
Sistemas Complexos naturais frequentemente 
possuem topologias complexas.
Teia Alimentar (Presa-Predador)
Rede Complexa 
Colaboração 
entre 
Cientistas 
Rede Complexa 
Internet
Rede Complexa 
Redes no Mundo Real
Motivação
Redes complexas formam a espinha dorsal dos 
sistemas complexos
Cada sistema complexo é uma rede de interações entre 
um grande número de elementos pequenos.
Algumas redes são geométricas ou regulares em espaços 
2D ou 3D.
Outras contêm conexões de longa distância ou não são 
espaciais.
Compreender um sistema complexo requer quebrá-lo em 
partes e depois remontá-lo
Redes são uma ferramenta adequada para esse função.
Motivação
A caracterização da anatomia das redes é 
importante porque em geral a estrutura afeta a 
função (e vice-versa).
Exemplo: Estrutura de redes sociais
Prevenir a transmissão de doenças.
Controlar a disseminação de informação (marketing, 
moda, boatos etc.).
Exemplo: Estrutura da rede elétrica e Internet
Compreender a robustez e estabilidade dos sistemas de 
transmissão de energia e de dados.
Tipos de Redes
Um conjunto de vértices ligados por arestas é o 
tipo mais simples de rede
Vértices e arestas podem ter uma grande quantidade de 
atributos associados.
Arestas podem ser direcionadas, representando 
relações unidirecionais.
Exemplo: redes sociais
Vértices podem representar pessoas de sexo, 
nacionalidade, idade e renda diferentes.
Arestas podem indicar relações interpessoais. 
Pesos nas arestas podem representar o grau de 
conhecimento que uma pessoa tem da outra.
Tipos de Redes
Rede não direcionada com um tipo de aresta e vértice.
Rede com tipos diferentes de vértices e arestas.
Rede com pesos variados nas arestas e nos vértices.
Rede direcionada.
O que a Área de Redes 
Estuda?
Propriedade estatísticas das redes
Encontrar propriedades estatísticas (ex.: tamanhos de 
caminhos e distribuições de grau), que caracterizem sua 
estrutura e seu comportamento.
Encontrar maneiras de medir essas propriedades.
Modelos de redes
Criar modelos de redes para compreender o significado 
das suas propriedades.
Como as redes são do jeito que são e como as 
propriedades interagem entre si.
O que a Área de Redes 
Estuda?
Predição de comportamento dos sistemas
Prever qual comportamento os sistemas terão com base 
nas propriedades estruturais medidas e nas regras 
locais que governam os vértices individuais.
Exemplos: como a estrutura da rede afeta?
O tráfego na Internet?
O desempenho de um mecanismo de busca na Web?
A dinâmica de sistemas sociais?
A dinâmica de sistemas biológicos?
Esse terceiro tópico é o mais importante e o 
menos compreendido até agora.
Parte 2.3:
Redes no Mundo Real
Redes no Mundo Real
Vários tipos de redes têm sido estudadas nos 
últimos anos, dos mais variados tipos.
As redes são normalmente classificadas em 4 
categorias, que englobam tipos semelhantes
Outras classificações são possíveis.
Categorias de redes
Redes sociais.
Redes de informação.
Redes tecnológicas.
Redes biológicas.
Redes Sociais
Uma rede social é um conjunto de pessoas ou 
grupos de pessoas com algum padrão de contato 
ou interação entre si.
Exemplos
Amizades entre indivíduos.
Relacionamentos comerciais entre empresas.
Casamentos entre famílias.
Relacionamentos sexuais (ex.: controle de DST).
Experimento “Small-World”
Stanley Milgram realizou um experimento nos 
anos 1960, cujo resultado gerou o famoso 
problema do mundo pequeno (small-world), ou “seis 
graus de separação”.
Pessoas de cidades do interior (meio oeste) dos 
EUA receberam solicitações de entregar uma 
carta para uma pessoa em Boston caso a 
conhecessem pessoalmente.
Caso contrário, elas deviam enviar pelo correio a 
carta para alguém que conhecessem bem e que em 
sua opinião estivesse mais próximo do destino.
Experimento “Small-World”
O objetivo foi avaliar a distribuição dos tamanhos 
dos “caminhos” em uma rede de pessoas 
conhecidas.
A maioria das cartas foi perdida, mas cerca de 
um quarto atingiu o destino.
Pelo procedimento adotado, foi possível medir a 
quantidade de pessoas que participaram de cada 
caminho entre origem e destino
O menor foi 3 (alguns foram da ordem de dezenas).
A média dos caminhos entre as pessoas foi 6.
Experimento “Small-World”
O resultado do experimento deu origem ao 
conceito dos “Seis Graus de Separação” que se 
tornou popular
Alguns pesquisadores acreditam ser um mito e até 
encontraram falhas no experimento de Milgran.
Em todo caso, ele ficou famoso 
Seis Graus de Separação
Redes Sociais: Problemas
Os estudos tradicionais em redes sociais têm 
vários problemas: imprecisão, subjetividade e 
amostra de tamanho pequeno.
A coleta de dados é, em geral, realizada através 
de questionários ou entrevistas
Métodos trabalhosos, que limitam o tamanho da rede.
Os dados são influenciados por aspectos 
subjetivos das pessoas que respondem
Ex.: o conceito de amigo pode variar entre pessoas.
As pessoas podem não dizer a verdade
Com ou sem intenção.
Redes Sociais: Soluções Atuais
Nos tempos da Internet, a obtenção de dados 
com alto grau de precisão tornou-se mais simples, 
facilitando a reunião de dados sobre redes de 
colaborações em diferentes níveis.
Existem inúmeros bancos de dados disponíveis 
com dados de vários tipos de relacionamentos
Artistas de Hollywood e filmes em que eles 
participaram.
Jogadores de futebol e clubes.
Pesquisadores e co-autoria de artigos.
Redes Sociais Online
As redes sociais online são grande objeto de 
estudo atualmente.
Relações estáticas e dinâmicas
Estáticas: as relações são explicitamente escolhidas 
e/ou aprovadas pelos participantes
Ex: amigos no Facebook, contatos profissionais no LinkedIn, 
seguidores no Twitter.
Podem não representar relacionamentos ativos.
Dinâmicas: com quem você se comunica frequentemente
Essas representam relacionamentos ativos.Redes Sociais Online: Dados
Obtenção de dados automaticamente das redes 
sociais é mais fácil
Informações sobre milhões de usuários, sobre 
relacionamentos e outras informações podem ser 
recuperadas.
Em geral, é possível obter toda a rede de 
relacionamentos das redes sociais, através de 
programas do tipo crawler que executam 
continuamente e recuperam dados
Utilizando as interfaces de programação (APIs) que elas 
disponibilizam.
Fazendo requisições a partir das páginas Web.
Redes de Informação
Redes de informação são também chamadas de 
“redes de conhecimento” porque uma informação 
faz referência à outra, de modo que se torna 
possível “navegar” entre as informações.
Redes de citação de artigos
Artigos citam outros artigos.
A partir disso, os pesquisadores podem conhecer outras 
fontes de informação sobre um assunto.
Estrutura: alguns pesquisadores publicam muito mais e 
são muitos mais citados do que outros
No estilo de uma lei de potência.
Redes de Informação
World Wide Web (www)
A Web forma uma rede de informação, funcionando 
como um serviço da Internet
Importante: Internet e Web NÃO são sinônimos.
Páginas contêm links para outras páginas.
Estrutura
Algumas páginas são muito mais referenciadas do que outras 
(grandes portais, por exemplo).
Algumas páginas referenciam uma quantidade enorme de outras 
páginas (mecanismos de busca, como o Google).
Novamente, no estilo de uma lei de potência.
Outros exemplos
Redes P2P, patentes, uso de palavras.
Redes de Informação
Rede de Citações Web
Redes Tecnológicas
Redes tecnológicas foram construídas pelo ser 
humano para a distribuição de algum serviço 
básico, como eletricidade ou dados.
Exemplos
Internet (no nível de interconexão de roteadores).
Redes de energia elétrica.
Rede de telefonia.
Rede de distribuição postal (correios).
Sistema de aeroportos.
Redes Tecnológicas
Rede elétrica
Rede de transmissão de 
energia de alta tensão.
Interconexão entre sistemas 
de transmissão (ou seja, rede) 
é necessária para fazer 
melhor uso dos recursos 
(energia).
Pode causar problemas, como 
apagões, quando falhas em 
cascata ocorrem e se 
propagam na rede.
Redes Tecnológicas: Internet
Rede de comutação de pacotes, para transmissão 
de dados entre computadores remotos.
Interconexão no nível físico, ou seja através de 
roteadores e enlaces (links) de dados.
Também apresenta interconexão no nível de 
Sistemas Autônomos (AS), que são agrupamentos 
de redes que possuem autonomia de roteamento
A ligação entre ASs tem influência na interconexão dos 
roteadores desses ASs (obviamente).
Exemplos de AS: RNP, Telefonica, Embratel etc.
Redes Tecnológicas: Internet
O conhecimento da topologia de interconexão da 
Internet pode trazer vários benefícios
Escalabilidade e robustez.
Projeto de melhores protocolos e aplicações.
Problema
Não se conhece a topologia da Internet, nem no nível de 
roteadores nem de ASs
Como a Internet não tem dono, em geral não se revela a topologia 
de cada AS por questões de sigilo.
Somente as redes acadêmicas revelam sua topologia.
Todo o conhecimento da topologia é obtido 
através de inferências.
Roteadores e Sistemas 
Autônomos





AS
roteador
Mapa da Internet: Nível AS
http://www.caida.org
Cada Sistema Autônomo 
(AS) nesta topologia 
corresponde 
aproximadamente a um 
Provedor (Internet 
Service Provider – ISP) 
Redes Biológicas
Vários sistemas biológicos podem ser 
representados como redes.
Exemplos mais comuns
Redes de caminhos metabólicos.
Teias alimentares.
Interações entre proteínas.
Regulação genética.
Redes de neurônios.
Redes vasculares.
Redes Biológicas
Redes de caminhos 
metabólicos
Os vértices são substâncias 
químicas presentes nos seres 
vivos, que podem ser tanto 
produto como substrato para 
uma reação.
Arestas direcionadas de 
entrada indicam reações 
metabólicas conhecidas 
atuando num substrato e 
produzindo um resultado.
Redes Biológicas
Teias alimentares
Vértices representam 
espécies em um 
ecossistema.
Arestas direcionadas da 
espécie A para a espécie B 
indicam que B é predador de 
A.
Ou indica a energia que flui 
de A para B.
Parte 2.4:
Classificação de Redes
Modelos de Redes
Três modelos representativos de redes 
complexas
Redes de Grafos Aleatórios
[Erdös-Rényi:1960]
Redes de Mundo Pequeno (Small-World)
[Watts-Strogatz:1998]
Redes sem Escala (Scale-Free)
[Barabasi-Albert:1999]
Grafos Aleatórios
Um Grafo Aleatório é um grafo (rede) gerado por 
um processo aleatório.
Formação
Iniciar com N vértices e nenhuma aresta.
Com probabilidade p, conectar 2 vértices selecionados 
aleatoriamente com uma aresta.
com p=0.2
Redes Small-World
Uma Rede Small-World é um tipo de grafo em que 
a maioria dos vértices não é vizinha dos outros 
vértices, mas a maioria dos vértices pode ser 
alcançada de qualquer outro vértice através de um 
número pequeno de arestas.
Formação
Iniciar com um anel (lattice) de N vértices com arestas 
entre os seus dois próximos vizinhos.
Cada aresta deve ser religada a outro vértice com 
probabilidade p.
Redes Small-World
Formação
Iniciar com um anel (lattice) de N vértices com arestas entre os seus 
dois próximos vizinhos (portanto, com a média de conexões <k> = 4).
Cada aresta deve ser religada a outro vértice com probabilidade p (uma 
das extremidades de cada aresta é conectada a um novo vértice 
aleatoriamente selecionado).
WS -> Watts-Strogatz (propuseram este algoritmo).
Redes Sem Escala (Scale-Free)
Redes Scale-Free possuem a distribuição dos 
seus graus (quantidade de arestas dos vértices) 
de acordo com uma lei de potência (power law)
Vértices com k arestas ocorrem com probabilidade 
P(k) ~ k-, sendo 2<<3. 
Consequência
Poucos vértices (hubs) possuem muitas arestas e muitos 
vértices possuem poucas arestas.
Importância: muitas redes observadas 
empiricamente possuem a propriedade Scale-Free.
Redes Sem Escala (Scale-Free)
Tarefa
Pesquisar um exemplo de problema que foi 
modelado através de redes complexas, fazer um 
resumo de +/- 2 páginas
Guarde o resumo, pois este será entregue 
posteriormente como parte da 1a atividade
Atenção: Não esqueça de colocar as referências 
utilizadas no texto e nunca copie textos sem 
colocar entre aspas e citar de onde o texto foi 
tirado
	Slide 1
	Slide 2
	Slide 3
	Slide 4
	Slide 5
	Slide 6
	Slide 7
	Slide 8
	Slide 9
	Slide 10
	Slide 11
	Slide 12
	Slide 13
	Slide 14
	Slide 15
	Slide 16
	Slide 17
	Slide 18
	Slide 19
	Slide 20
	Slide 21
	Slide 22
	Slide 23
	Slide 24
	Slide 25
	Slide 26
	Slide 27
	Slide 28
	Slide 29
	Slide 30
	Slide 31
	Slide 32
	Slide 33
	Slide 34
	Slide 35
	Slide 36
	Slide 37
	Slide 38
	Slide 39
	Slide 40
	Slide 41
	Slide 42
	Slide 43
	Slide 44
	Slide 45
	Slide 46
	Slide 47
	Slide 48
	Slide 49
	Slide 50
	Slide 51
	Slide 52
	Slide 53
	Slide 54
	Slide 55
	Slide 56
	Slide 57
	Slide 58
	Slide 59
	Slide 60
	Slide 61
	Slide 62
	Slide 63
	Slide 64
	Slide 65
	Slide 66
	Slide 67
	Slide 68
	Slide 69
	Slide 70

Outros materiais