Network Science

Code:

CC4063

Acronym:

CC4063

Level:

400

Keywords
Classification	Keyword
OFICIAL	Computer Science

Instance: 2022/2023 - 2S

Active?	Yes
Web Page:	http://www.dcc.fc.up.pt/~pribeiro/aulas/ns2223/
Responsible unit:	Department of Computer Science
Course/CS Responsible:	Master in Bioinformatics and Computational Biology

Cycles of Study/Courses

Acronym	No. of Students	Study Plan	Curricular Years	Credits UCN	Credits ECTS	Contact hours	Total Time
E:BBC	0	PE_Bioinformatics and Computational Biology	1	-	6	42	162
M:BBC	3	The study plan since 2018	1	-	6	42	162
M:DS	8	Official Study Plan since 2018_M:DS	1	-	6	42	162
			2
M:ERSI	11	Official Study Plan since 2021_M:ERSI	1	-	6	42	162

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; GNNs; ...

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 (%)
Trabalho prático ou de projeto	40,00
Teste	60,00
Total:	100,00

Amount of time allocated to each course unit

designation	Time (hours)
Elaboração de projeto	15,00
Estudo autónomo	90,00
Frequência das aulas	42,00
Trabalho de investigação	15,00
Total:	162,00

Eligibility for exams

To have delivered the small research project.

Calculation formula of final grade

- 2 Homeworks: 30%
Small mixed wrirrten + application/implementation assignments
- Test: 30%
Onsite written test
- Project: 40%
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.