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
Pedro José dos Santos Palhinhas Mota
Horas
Semanais - 4
Totais - 70
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.