BCM0506 -- Comunicação e Redes -- 2020.S

Turma DB1

Sep 1, 2020
Atualizado em 14/01

Conceitos

Aulas e Avaliações

  • Professor: Aritanan Gruber ( página no Tidia )
  • Atendimento: segundas das 10h às 12h via Google Classroom (código: e2rsalx) / Meet.
  • Listas: $L_1$ ( 16/11; solução ), $L_2$ ( 17/12; solução ).
  • Aulas assíncronas: vídeos (máximo de 30min cada) no canal Aritanan Gruber do YouTube.
  • Notas de aula:

    • A01-21/09 – vídeos:
      Expediente. Introdução. Gephi.
      leitura: Barabási 1.1–1.7; Newman 2.1–5.3

    • A02-24/09 e A03-01/10 – vídeos: parte 1, parte 2, parte 3, parte 4, parte 5.
      Grafos (I)
      leitura: Barabási 2.1–2.4; Newman 6.1–6.3, 6.9, 9.3

    • A04-05/10 e A05-08/10 – vídeos: parte 1, parte 2, parte 3, parte 4.
      Grafos (II)
      leitura: Barabási 2.6–2.9; Newman 6.10–6.12, 9.1, 10.3

    • A06-15/10 – vídeos: parte 1, parte 2, parte 3, parte 4, parte 5, parte 6.
      Caminhos Mínimos
      leitura: Barabási 2.8, 2.9; Newman 10.4, 6.4, 6.6, 6.7

    • A07-19/10 – vídeos: parte 1, parte 2, parte 3, parte 4.
      Importância Estrutural
      leitura: Barabási 2.10, 2.A; Newman 7.1–7.9, 10.2

    • A08-22/10 – vídeos:
      Sistemas Dinâmicos Lineares
      leitura: Newman 11.1, 18.1

    • A09-29/10 – vídeos:
      Passeios Aleatórios e Cadeias de Markov
      leitura: Newman 6.13, 6.14, 7.4

    • A10-02/11 – vídeos:
      Difusão, Dispersão e Infecção
      leitura: Barabási 10.1 – 10.7; Newman 17.1 – 17.6

    • A11-05/11 – vídeos:
      Comunidades e Clusterização
      leitura: Barabási 9.1 – 9.4; Newman 11.2 – 11.8

    • A12-12/11 – vídeos:
      Modelo Aleatório Erdös-Rényi-Gilbert I
      leitura: Barabási 3.1 – 3.5; Newman 12.1 – 12.4

    • A13-16/11 – vídeos:
      Modelo Aleatório de Erdös-Rényi-Gilbert II
      leitura: Barabási 3.6 – 3.9; Newman 12.5 – 12.8

    • A14-19/11 – vídeos:
      Modelo Aleatório de Barabási-Albert
      leitura: Barabási 5.1 – 5.6; Newman 14.1 – 14.4

    • A15-26/11 – vídeos:
      Outros Modelos Aleatórios
      leitura: Barabási 4.1, 4.2, 6.2, 6.4; Newman 8.2, 8.4, 13.2, 13.10, 13.11, 15.1, 15.2

    • A16-30/11 – equivalente a feriado em 02/11

    • A17-03/12 – equivalente à prova $P_1$

    • A18-10/12 – equivalente a prova $P_2$

    • A19-14/12 – equivalente à prova $P_S$

    • A20-17/12 – equivalente à recuperação

Critérios

Avaliação Peso Cálculo
Nota nominal ($N$)     $N = (L_1+L_2)/2$

Conceito nominal ($C_N$): reflete o seu desempenho frente ao material apresentado e às avaliações realizadas; obtido pelo encaixe de $N$ em um dos intervalos: $$-\infty < \mathbf{F} < 5.0 \leq \mathbf{D} \leq 6.0 < \mathbf{C} \leq 7.0 < \mathbf{B} \leq 8.5 < \mathbf{A} < \infty.$$

Normalização

Sejam $\mu$ e $\sigma$ a média e o desvio padrão das notas $N$ atribuídas a todos os alunos. Cada aluno obterá uma nota normalizada: $$M = (N-\mu)/\sigma.$$

Conceito normalizado ($C_M$): reflete o seu desempenho perante os seus colegas; obtido pelo encaixe de $M$ em um dos intervalos: $$-\infty < \mathbf{F} < -\frac{1}{4}\sigma \leq \mathbf{D} < 0 \leq \mathbf{C} < \frac{1}{4}\sigma \leq \mathbf{B} < \frac{1}{2}\sigma \leq \mathbf{A} < \infty.$$

Considerando-se a ordenação $\mathbf{A} > \mathbf{B} > \mathbf{C} > \mathbf{D} > \mathbf{F}$, seu conceito efetivo (final / pré-recuperação) será maior ou igual ao seu conceito nominal: $$C_F = \max\{C_N,C_M\}.$$

Recuperação

Caso seu conceito $C_F$ seja $\mathbf{D}$ ou $\mathbf{F}$, você tem direito a uma prova de recuperação presencial $P_R$. Esta será única e contemplará toda a matéria do quadrimestre. Uma nova nota nominal $\overline{N}=(N+P_R)/2$ será utilizada para gerar um novo conceito (nominal) final pós-recuperação $\overline{C}_N$. Não haverá normalização na recuperação. Seu conceito final pós-recuperação pode ser menor que o pré-recuperação: uma vez feita, a recuperação é parte integrante da sua avaliação.

Descrição e objetivos

O curso será uma introdução à ciência das redes complexas. Informalmente, uma rede é uma coleção de objetos interconectados com um determinado propósito. Formalmente, é um grafo ou um digrafo rotulado (formalismos matemáticos para o estudo de endorelações binárias). A qualificação complexa encontrada na literatura se refere ao grande volume de informação representado por e à propriedades implicitamente codificadas em uma rede. Redes complexas encontram uma multitude de aplicações nos mais variados campos, como tecnologia (internet, www, telefonias fixa e móvel), infra-estrutura (água, luz, gás), logística (transporte, roteamento, localização), biologia (metabolismo, interações entre proteínas e/ou medicamentos, cérebro e rede neural), ecologia (filogenia, cadeia predatória, inter e intra-dependência em ecossistemas), educação/informação (enciclopédias, wikipedia, coautorias e citações), sociologia (facebook, instagram, twitter, linked-in, snapchat, whatsapp, clubes, sociedades e castas).

O campo é vasto, varrendo da representação à especificação à inferência e à mineração de propriedades estáticas ou dinâmicas, determinísticas ou estocásticas. Nossa abordagem será primariamente abstrata e matemática, com foco na definição, caracterização e inferência de aspectos estruturais e assintóticos de propriedades em redes massivas (grande número de vértices) e em algoritmos para verificação ou cômputo de tais propriedades. Em momentos adequados ou oportunos, introduziremos aspectos semânticos através de aplicações. Inúmeras técnicas para construção de provas serão apresentadas. O objetivo é desenvolver na/o estudante o raciocínio e a destreza na manipulação de estruturas discretas, espaços lineares e argumentos probabilísticos.

Bibliografia

As referências básicas são, em ordem: Barabási-Pósfai [0], Newman [7] e Easley-Kleinberg [1]. Figueiredo [3] é uma introdução sucinta em português (não cobre tudo). Em momentos oportunos, faremos incursões em Frieze-Karonski [4] e Hofstad [5]. Referência de apoio para grafos e digrafos (com enfoque teórico) são Feofiloff-Kohayakawa-Wakabayashi [2] e Lehman-Leighton-Meyer [6].

Páginas úteis

Estudando para esta disciplina

Este curso tem nível introdutório e contempla uma coleção de problemas elementares e fundamentais na área. Apesar disso, é normal fazer confusões e sentir-se perdido no início. O motivo é, em geral, a falta de familiaridade com formalismo matemático e raciocínio algorítmico -– algo que o curso pretende reverter.

  • Refaça os exemplos fornecidos em sala de aula e re-prove os principais resultados.
  • Preste atenção ao processo de solução e não foque somente no resultado final.
  • Assista às aulas (vídeos) e resolva os exercícios propostos durante as mesmas e os contidos nas listas (não somente os para entrega).
  • Estude a bibliografia indicada (monte grupos de estudo online) e faça um bom uso dos horários de atendimento.
  • Tenha sempre em mente que aprendizado é uma tarefa ativa; não fique somente assistindo.
  • Se ainda estiver se sentindo perdido, repita os passos acima. Mais cedo ou mais tarde, eles convergirão à compreensão.

Integridade acadêmica e transgressões

O Artigo 25 do Código de Ética da UFABC estabelece, à página 23: “Quanto aos trabalhos acadêmicos, é eticamente inaceitável que os discentes:

  • I - fraudem avaliações;
  • II - fabriquem ou falsifiquem dados;
  • III - plageiem ou não creditem devidamente autoria;
  • IV - aceitem autoria de material acadêmico sem participação na produção;
  • V - vendam ou cedam autoria de material acadêmico próprio a pessoas que não participaram da produção.”

Trabalhos (listas, provas, programas) suspeitos de cópia ou de outra representação fraudulenta acarretarão aos envolvidos conceitos $\mathbf{F}$ (falha) no curso. A atividade será reportada à Comissão Disciplinar Discente da universidade para que sejam tomadas todas as providências disciplinares cabíveis.

Tópicos

  • 1 - Redes Complexas: Grafos e Digrafos

    • Definições elementares
    • Matrizes de adjacência e incidência; Laplaciano
    • Automorfismo e isomorfismo
    • Distribuições de graus, comunidades e centralidade

  • 2 - Conectividade

    • Caminhos, trilhas, passeios, ciclos, circuitos e tours
    • Florestas e árvores
    • Cortes, fluxos e emparelhamentos
    • Conjuntos estáveis, cliques e colorações
    • Graus de correlação
    • Comunidades

  • 3 - Métodos Probabilísticos e Modelos Aleatórios

    • Espaços e medidas de probabilidade (caso discreto), variáveis aleatórias, esperança, variância
    • Convergência de variáveis aleatórias e desigualdades de concentração e desvio
    • Processos estocásticos: cadeias de Markov e Martingais
    • Erdös-Renyi e Gilbert
    • Watts-Strogatz e Barabási-Albert
    • Chung-Lu e Norros-Reittu
    • Leis de potência e redes livres de escala

  • 4 - Extremalidade

    • Mantel, Turán e Ramsey
    • Geradores (spanners), expansores (expanders) e esparsificadores (sparsifiers)
    • Evolução, componente gigante, pontos críticos e transições de fase
    • Condensação de Bose-Einstein
    • Passeios aleatórios e processos de geração

  • 5 - Difusão, Dispersão e Infecção

    • Modelos SI, SIS, SIR, SIRS
    • Contato e redes temporais
    • Sistemas dinâmicos em redes

  • 6 - Robustez (*)

    • Conectividade Redux
    • Confiabilidade e falhas em cadeia
    • Percolação
    • Tolerância a ataques
    • Projeto de redes robustas
Avatar
Aritanan Gruber
Assistant Professor

“See, if y’all haven’t the same feeling for this, I really don’t give a damn. If you ain’t feeling it, then dammit this ain’t for you!"
(desconheço a autoria; agradeço a indicação)