Baixe o app para aproveitar ainda mais
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
Compartilhar