-
Presentation
Presentation
The course "Introduction to Graph Theory and Networks" aims to provide students with tools for using graphs in various problems. It starts with basic concepts, covers classical problems, and concludes with a brief introduction to complex networks and their applications in Data Science problems.
-
Class from course
Class from course
-
Degree | Semesters | ECTS
Degree | Semesters | ECTS
Bachelor | Semestral | 6
-
Year | Nature | Language
Year | Nature | Language
2 | Mandatory | Português
-
Code
Code
ULHT6634-24499
-
Prerequisites and corequisites
Prerequisites and corequisites
Not applicable
-
Professional Internship
Professional Internship
Não
-
Syllabus
Syllabus
S1. Basic Concepts (Definition, vertices, edges, directed and undirected graphs, metrics, subgraphs, distance and connectivity, isomorphisms, invariants, and spectral theory). S2. Networks and Flows (Maximum flow, minimum cost flow). S3. Network Analysis (Network representation, visualization, degree, distance measures, and centrality). S4. Random Graphs (Erdös-Rényi, Watts-Strogatz, Barabasi-Albert). S5. Applications in Data Science.
-
Objectives
Objectives
The main objectives of this discipline are: LO1. Identify and use concepts and foundations of graph theory. LO2. Introduce students to the problems, and basic theorems of graph theory. LO3. Represent networks, determine distance statistics, and clustering coefficients. LO4. Analyze the centrality of a network. LO5. Characterize random networks: classical (Erdös-Rényi), small-world (Watts-Strogatz), and scale-free (Barabasi-Albert). LO6. Apply the concepts covered in the course to Data Science.
-
Teaching methodologies
Teaching methodologies
There are theoretical and practical classes, being mainly expositives and in-person lectures. We expect at least 115 hours off class dedication and 52h to un-person classes. TM1. Lectures. TM2. Practical, incorporating both explanatory segments and exercises. TM3. Theoretical and practical exercise assignments. TM4. Independent project development. TM5. Recommendation of supplementary materials.
-
References
References
L. Barabasi, M. Pósfai, Network Science, Cambridge University Press, 2016 B. Bollobás, Random Graphs, Cambridge University Press, 2001 D. M. Cardoso, J. Szymanski, M. Rostami, Matemática Discreta: combinatória, teoria dos grafos e algoritmos, Escolar Editora, 2008. P. Feofiloff, Y. Kohayakawa, Y. Wakabayashi, Uma Introdução Sucinta à Teoria dos Grafos, 2004
-
Assessment
Assessment
A avaliação da cadeira está dividida em componentes prática e teórica, sendo composta por:
Componente prática:
- Assiduidade, participação e Laboratórios computacionais (20%).
- Projetos computacionais a desenvolver em grupo, com um prazo de duas semanas para desenvolvimento (80%).
Componente teórica:
- Assiduidade, participação e exercícios realizados em sala de aula (30%)
- 2 testes escritos, sendo o primeiro realizado numa aula teórica e o segundo na data final da frequência (70%).
Cada componente de avaliação tem peso de 50% na nota final. Sendo que o aluno deve atingir no mínimo 50% por componente, e 50% na média dos componentes.
-
Mobility
Mobility
No
