Ciência de Redes

Código:

CC4063

Sigla:

CC4063

Nível:

400

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

Ocorrência: 2020/2021 - 2S

Ativa?	Sim
Página Web:	http://www.dcc.fc.up.pt/~pribeiro/aulas/ns2021/
Unidade Responsável:	Departamento de Ciência de Computadores
Curso/CE Responsável:	Mestrado em Bioinformática e Biologia Computacional

Ciclos de Estudo/Cursos

Sigla	Nº de Estudantes	Plano de Estudos	Anos Curriculares	Créditos UCN	Créditos ECTS	Horas de Contacto	Horas Totais
M:BBC	3	Plano estudos a partir de 2018	1	-	6	42	162
M:DS	8	Plano Oficial a partir de 2018_M:DS	1	-	6	42	162
			2

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.
- Propagação em redes: fluxo de informação; influência; epidemologia e modelos de propagação.
- Análise de larga escala: o papel da amostragem; algoritmos paralelos; sistemas e bases de dados orientadas a grafos.
- 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	10,00
Trabalho prático ou de projeto	60,00
Teste	30,00
Total:	100,00

Componentes de Ocupação

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

Obtenção de frequência

Ter entregue o projecto de investigação.

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

- "Homeworks": 25%
2 mini-trabalhos de aplicação/implementação (cada um valendo 12.5%).
- Testes: 30%
2 pequenos testes de duração aproximada de 1h30m (cada um valendo 15%)
- Apresentação/Revisão de artigo: 10%
Escolha de um artigo científico muito recente na área para apresentação oral na aula.
- Projecto: 35%
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.