Network Science
Keywords |
Classification |
Keyword |
OFICIAL |
Computer Science |
Instance: 2020/2021 - 2S
Cycles of Study/Courses
Teaching language
English
Objectives
Networks are a fundamental tool for modeling complex social, technological, and biological systems. Having into account the emergeng o large scale network data, this course focuses on the analysis of these networks, which provide multiple computational, algorithmic, and modeling challenges. The course will cover recent research on the structure and analysis of such networks, as well as models and algorithms that abstract their main properties.
Learning outcomes and competences
At the end of this curricular unit the students should be able to:
- explain the key concepts of network science and network analysis
- apply a range of techniques for characterizing network structure
- define methodologies for analyzing networks of different fields
- demonstrate knowledge of recent research in the area
Working method
Presencial
Program
- Introduction and Fundamentals: the emergence of network science; graph theory fundamental concepts; representing networks in computer; classical graph algorithms.
- Metrics and basic structural properties: degree distribution, paths and diameter, clustering coefficient, centrality measurements ((betweenness, closeness, eigenvector, ...).
- Network Visualization: graph drawing, layout algorithms, exploratory analysis with the aid of visualization.
- Common properties and network models: random networks and Erdös-Rényi model; “small-world” property and Watts-Strogatz model; “scale-free” property and Albert-Barabsi model; other models (ex: Kronecker graphs).
- Communities: algorithms for detecting communities; optimizing modularity; overlallping communities and other variants.
- Patterns and Subgraphs: subgraph as fundamental units; subgraph census; concept and algorithms for network motifs discovery; graphlet degree distributions; incorporating attributes such as colors and weights.
- Link Analysis: node rankings, HITS algorithms, PageRank and other variants.
- Propagation in networks: information flow; influence; epidemics and propagation models.
- Análise de larga escala: o papel da amostragem; algoritmos paralelos; sistemas e bases de dados orientadas a grafos.
- Other topics: link prediction; network alignment; node role analysis; temporal networks; multiplex networks; ...
Mandatory literature
Barabasi, A.; Network Science (available online at http://barabasi.com/networksciencebook/)
Complementary Bibliography
Newman, M.; Networks: An Introduction, Oxford University Press, 2010
Easley, D., Kleinberg, J.; Networks, Crowds, and Markets: Reasoning About a Highly Connected World
Teaching methods and learning activities
Lectures: exposition of selected topics and discussion of examples and case studies. Solving small problems with the application of the the given methodologies and using existing software. Implementing selected algorithms. Developing a network analysis project. Reviewing and presenting related scientific literature.
Evaluation Type
Distributed evaluation without final exam
Assessment Components
designation |
Weight (%) |
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 |
Amount of time allocated to each course unit
designation |
Time (hours) |
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 |
Eligibility for exams
To have delivered the small research project.
Calculation formula of final grade
- Homeworks: 25%
2 small application/implementation assignments (each one worth 12.5%).
- Tests: 30%
2 small tests of approximate duration of 1h30m (each one worth 15%)
- Presenting/Reviewing an article: 10%
Choosing a very recent related scientific article and presenting it orally in class
- Project: 35%
Development of a small research project with the application of network science tools and algorithms, and with the creation of a written article describing the work done.