Network Science

Código:

CC4070

Sigla:

CC4070

Nível:

400

Áreas Científicas
Classificação	Área Científica
OFICIAL	Ciência de Computadores

Ocorrência: 2018/2019 - 2S

Ativa?	Sim
Página Web:	http://www.dcc.fc.up.pt/~pribeiro/aulas/ns1819/
Unidade Responsável:	Departamento de Ciência de Computadores
Curso/CE Responsável:	Mestrado Integrado em Engenharia de Redes e Sistemas Informáticos

Ciclos de Estudo/Cursos

Sigla	Nº de Estudantes	Plano de Estudos	Anos Curriculares	Créditos UCN	Créditos ECTS	Horas de Contacto	Horas Totais
MI:ERS	15	Plano Oficial desde ano letivo 2014	4	-	6	42	162

Língua de trabalho

Inglês

Objetivos

As redes são uma ferramenta fundamental para modelar sistemas complexos sociais, biológicos e tecnológicos. Tendo também em conta a emergente disponibilidade de dados de larga escala de redes, esta unidade curricular foca-se na análise destas redes, o que acarreta múltiplos desafios computacionais, algorítmicos e de modelação. Irá cobrir investigação recente na estrutura e anaĺise  destas redes, bem como modelos e algoritmos que possam abstrair as suas principais propriedades.

Resultados de aprendizagem e competências

No final desta unidade curricular os estudantes devem ser capazes de:
- explicar os conceitos chave da ciência de redes e da e análise de redes complexas
- aplicar um leque variado de técnicas para caracterizar a estrutura de redes
- definir metodologias para analisar redes de diferentes domínios
- demonstrar conhecimento da investigação recente na área

Modo de trabalho

Presencial

Programa

- Introdução e Fundamentos: a emergência de uma ciência das redes; conceitos fundamentais de teoria de grafos; representações de redes em computador; algoritmos clássicos de grafos.
- Métricas e propriedades estruturais básicas: distribuição de graus, caminhos e diâmetro, coeficiente de clustering, medidas de centralidade (betweenness, closeness, eigenvector, ...).
- Visualização de Redes: formatos; desenho de grafos, algoritmos para layout, análise exploratória com recurso a visualização.
- Propriedadas comuns e modelos de redes: redes aleatórias e modelo Erdös-Rényi; propriedade “small-world” e modelo de Watts-Strogatz; propriedade “scale-free” e modelo de Albert-Barabsi; outros modelos (ex: grafos de Kronecker).
- Comunidades: algoritmos para deteção de comunidades; optimização de modularidade; comunidades com sobreposição e outras variantes.
- Padrões e Subgrafos: subgrafos como unidades fundamentais; censo de subgrafos; conceito e algoritmos para descoberta de “network motifs”; distribuiçõe de graus de graphlets; redes pesadas, coloridas e outras variantes.
- Análise de links: ranking de nós, algoritmos HITS, Pagerank e variantes.
- Análise de larga escala: o papel da amostragem; algoritmos paralelos; sistemas e bases de dados orientadas a grafos.
- Propagação em redes: fluxo de informação; influência; epidemologia e modelos de propagação.
- Outros tópicos: previsão de ligações; alinhamento de redes; análise do papel de um nós; redes temporais; redes multi-camada; ...

Bibliografia Obrigatória

Barabasi, A.; Network Science (disponível online em http://barabasi.com/networksciencebook/)

Bibliografia Complementar

Newman, M.; Networks: An Introduction, Oxford University Press, 2010
Easley, D., Kleinberg, J.; Networks, Crowds, and Markets: Reasoning About a Highly Connected World

Métodos de ensino e atividades de aprendizagem

Aulas teórico-práticas com apresentação teórica dos tópicos abordados e discussão de exemplos e casos de estudo. Resolução de pequenos problemas com aplicação das metodologias selecionadas e uso de software existente. Implementação de algoritmos selecionados. Desenvolvimento de um projeto de análise de redes. Revisão e apresentação de literatura cientifica relacionada.

Tipo de avaliação

Avaliação distribuída sem exame final

Componentes de Avaliação

Designação	Peso (%)
Apresentação/discussão de um trabalho científico	15,00
Teste	45,00
Trabalho prático ou de projeto	40,00
Total:	100,00

Componentes de Ocupação

Designação	Tempo (Horas)
Apresentação/discussão de um trabalho científico
Elaboração de projeto
Estudo autónomo
Frequência das aulas
Trabalho de investigação
Trabalho laboratorial
Total:	0,00

Obtenção de frequência

Ter entregue o projecto de investigação.

Fórmula de cálculo da classificação final

- Mini-Testes e Mini-Trabalhos: 45%
  Alguns pequenos testes teóricos (+/- 1h cada), alguns mini-trabalhos de aplicação/implementação.
- Apresentação/Revisão de artigo: 15%
  Escolha de um artigo científico muito recente na área para apresentação oral na aula.
- Projecto: 40%
  Desenvolvimento de um pequeno projeto de investigação com aplicação de ferramentas e algoritmos de network science, e com a escrita de um artigo descrevendo o trabalho desenvolvido.