Análise de Grandes Grafos

Objetivos

O objectivo principal da UC é desenvolver competências que permitam estudar estruturas dos grandes grafos. As metodologias para atingir esse objectivo são apresentadas nos tópicos 3 e 4, após a introdução (no ponto 2) dos necessários conceitos básicos de grafos. No ponto 1 apresentam-se e destacam-se particularidades de grandes grafos que ocorrem em diversos contextos, e serve para motivar a matéria a tratar nesta UC. Os pontos 4 e 5 fornecem metodologias para prever a evolução de fenómenos em objectos representados por grandes grafos.

Caracterização geral

Código

12082

Créditos

6.0

Professor responsável

Jorge Orestes Lasbarrères Cerdeira, Pedro José dos Santos Palhinhas Mota

Horas

Semanais - 4

Totais - A disponibilizar brevemente

Idioma de ensino

Português

Pré-requisitos

Os alunos devem ter alguma capacidade de formular problemas em programação inteira, e de conceber e implementar algoritmos.

Bibliografia

Networks (second edition), Mark Newman, Oxford University Press, 2018 (ISBN: 9780198805090)

Networks, Crowds, and Markets: Reasoning about a highly connected World, David Easley and Jon Kleinberg, Cambridge University Press, 2010 (ISBN: 9780521195331)

Graph Analysis and Visualization: Discovering Business Opportunity in Linked Data, Richard Brath and David Jonker, Wiley, 2015 (ISBN: 978-1-118-84584-4)

Big Data Analytics: From Strategic Planning to Enterprise Integration with Tools, Techniques, NoSQL, and Graph, David Loshin, Imprint: Morgan KaufmannPrint, Elsevier, 2013 (ISBN: 978-0-12-417319-4)

Método de ensino

As aulas são teóricas/práticas participadas, com exposição e discussão dos conceitos e metodologias devidamente complementada com exemplos e resoluções de problemas (incluindo software). Eventuais dúvidas poderão ser esclarecidas no decurso das aulas ou em sessões individuais no período de atendimento docente aos alunos. 

Os alunos necessitam de assistir a um mínimo de 2/3 das aulas para obter frequência à UC. 

Avaliação contínua: Um teste a realizar durante o período lectivo, e elaboração de um relatório escrito, sobre um tópico a definir, e apresentação oral do trabalho. Considera-se aprovado o aluno com frequência e soma das classificações obtidas nos dois elementos de avaliação >=10. A classificação final será o valor dessa soma.

Avaliação por exame de recurso: Só os alunos com frequência podem realizar exame de recurso. Considera-se aprovado o aluno que obtenha frequência e nota de exame final >=10 valores. 

Método de avaliação

Os alunos necessitam de assistir a um mínimo de 2/3 das aulas para obter frequência à UC. 

Avaliação contínua: Um teste a realizar durante o período lectivo, com a cotação de 12 valores, e elaboração de um relatório escrito, sobre um tópico a definir, e apresentação oral do trabalho, com a cotação de 8 valores. Considera-se aprovado o aluno com frequência e soma das classificações obtidas nos dois elementos de avaliação >=10. A classificação final será o valor dessa soma. 

Avaliação por exame de recurso: Só os alunos com frequência podem realizar exame de recurso. Considera-se aprovado o aluno que obtenha frequência e nota de exame final >=10 valores.

Conteúdo

1 Exemplos de grandes grafos reais; 

2 Conceitos básicos de grafos; 

3 Medidas topológicas (centralidade, comunidades, semelhança); 

4 Análise da estrutura de grafos de grandes dimensões (componentes, caminhos mais curtos e efeito small-world, distribuição dos graus dos vértices, distribuição de medidas de centralidade;) 

5 Grafos aleatórios; 

6 Processos em grandes grafo.  

Cursos

Cursos onde a unidade curricular é leccionada: