Network Science

Code:

CC4070

Acronym:

CC4070

Level:

400

Keywords
Classification	Keyword
OFICIAL	Computer Science

Instance: 2018/2019 - 2S

Active?	Yes
Web Page:	http://www.dcc.fc.up.pt/~pribeiro/aulas/ns1819/
Responsible unit:	Department of Computer Science
Course/CS Responsible:	Master's Degree in Network and Information Systems Engineering

Cycles of Study/Courses

Acronym	No. of Students	Study Plan	Curricular Years	Credits UCN	Credits ECTS	Contact hours	Total Time
MI:ERS	15	Plano Oficial desde ano letivo 2014	4	-	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.
- Large Scale Analysis: the role of sampling; parallel algorithms, systems and graph-oriented databases.
- Propagation in networks: information flow; influence; epidemics and propagation models.
- 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	15,00
Teste	45,00
Trabalho prático ou de projeto	40,00
Total:	100,00

Amount of time allocated to each course unit

designation	Time (hours)
Apresentação/discussão de um trabalho científico
Elaboração de projeto
Estudo autónomo
Frequência das aulas
Trabalho de investigação
Trabalho laboratorial
Total:	0,00

Eligibility for exams

To have delivered the small research project.

Calculation formula of final grade

- Mini-Tests and Mini-Assignments: 45%
  Some small theoretical tests (+/- 1h each), some small application/implementation assignments.
- Presenting/Reviewing an article: 15%
Choosing a very recent related scientific article and presenting it orally in class
- 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.