OVERVIEW

Networks are everywhere and they can be represented as graphs. This course will unravel the hidden patterns and dynamics of networks in various domains such as social networks, internet and the web, biological systems, and more. Students will learn the theoretical foundations of network analysis and experience hands-on activities to put into practice what introduced during classes.

AIMS AND CONTENT

LEARNING OUTCOMES

Learning algorithms and techniques for large scale graph analytics, including centrality measures, connected components, graph clustering, graph properties for random, small-world, and scale free graphs, graph metrics for robustness and resiliency, and graph algorithms for reference problems.

AIMS AND LEARNING OUTCOMES

Regular attendance and active participation in the proposed educational activities, along with individual study, will enable students to understand and explain the classical problems encountered in the study of large-scale networks. In particular, students will be able to:

• explain universal properties of graphs that can be used to study large networks, regardless of their application domains;
• ​explain popular ranking algorithms;
• understand which synthetic model best represents a real network;
• analyze the evolution of large-scale networks under conditions of failure, strategic attack, or contagion;
• use available libraries to implement exercises and put into practice the topics covered during lectures.
   

PREREQUISITES

To be successful in this course, students should have knowledge on:

• Basic graph theory (definitions, paths, components, visits)
• Web (how it works, its structure)
• Programming (for the hands-on activities)

TEACHING METHODS

Lectures and hands-on activities which are preparatory for the completion of the assignments discussed during the oral exam.

SYLLABUS/CONTENT

Students will learn how to analyze graphs of large size, even when it is impossible to visualize them because they are too large. Topics covered during the course are the following:

• Background on linear algebra and probability
• Complex networks introduction: examples from biology, sociology, economy, computer science
• Network topology (at local and global level): degree, centrality measures, connectivity, communities, and more
• Network models: random graphs, small-world, power-law networks
• Web graph: Markov chains and random walk, ranking, search engines
• Robustness and fault tolerance of networks (random failures and target attacks)
• Dynamic evolution of networks (social contagion and epidemic spreading)
• Networks visualization using open source software tools

RECOMMENDED READING/BIBLIOGRAPHY

• F. Menczer, S. Fortunato, C. A. Davis: A First Course in Network Science, Cambridge University Press, 2020
• D. Easley and J. Kleinberg: Networks, Crowds, and Markets: Reasoning About a Highly Connected World (http://www.cs.cornell.edu/home/kleinber/networks-book/)
• A. Barabasi: Network Science (http://barabasilab.neu.edu/networksciencebook/)
• Scientific papers will be suggested during the course

TEACHERS AND EXAM BOARD

Exam Board

MARINA RIBAUDO (President)

LESSONS

LESSONS START

According to the calendar approved by the Degree Program Board: https://corsi.unige.it/en/corsi/11964/studenti-orario

EXAMS

EXAM DESCRIPTION

The exam consists of the following parts: (i) a written test and (ii) an oral presentation during which students will discuss their assignments.

Guidelines for students with certified Specific Learning Disorders, disabilities, or other special educational needs are available at https://corsi.unige.it/en/corsi/11964/studenti-disabilita-dsa

ASSESSMENT METHODS

The written test, which serves as the admission to the assignments discussion, consists of questions related to the topics covered in class and it allows the evaluation of the student's theoretical knowledge acquired during the course. For the oral part, students will be evaluated based on the quality of the produced code and the completeness of the reports. The written test and the assignments discussion take place in the same session.

FURTHER INFORMATION

For further information, please refer to the course’s AulaWeb module or contact the instructor.