Obiettivi formativi
The course will provide the foundational tools for the analysis of complex networks, drawing from graph theory, social network analysis and complexity science. The course will discuss methods, as well as their practical application in real-life situations involving networks.
Prerequisiti
Knowledge and understanding:
The course will offer key theoretical tools to model complex networks and to analyze them (graph theory, probability theory).
Applying knowledge and understanding:
We expect students to be able to manipulate the concepts both in exercises (computing by hand) and in coding applications.
Making judgements:
We expect students to learn to be critical on the use of models. They will learn to balance how realistic the model is and how simple it is to analyze it.
Communications Skills:
The course will provide the students with the tools to formulate and communicate their ideas, proposals, analysis and critical reasoning in the field of network science in the most effective and appropriate way.
Learning skills:
The course will offer students further knowledge in mathematics, dedicated theoretical knowledge on network analysis and dedicated programming knowledge on networks.
Risultati di apprendimento attesi
Calculus, Linear algebra, Elementary probability.
Contenuti Del Corso
The aim is to present different mathematical and computational solution concepts used when studying networks.
The course will cover some basic concepts in graph theory. We will first introduce several measures to investigate the structure of networks. Then, we will focus on a variety of models able to reproduce the observed empirical structure of real-world networks.
Finally, we discuss how network structure affect the dynamics of a networked systems, as in diffusion/contagion over social networks, and investigate the consequences in terms of external interventions.
Testi Di Riferimento
Textbooks:
- Menczer, F., Fortunato, S., & Davis, C. (2020). A First Course in Network Science. Cambridge: Cambridge University Press. doi:10.1017/9781108653947.
- Latora, V., Nicosia, V., & Russo, G. (2017), Complex Networks: Principles, Methods and Applications, Cambridge: Cambridge University Press.
- Notes on Luiss Learn.
- Exercises provided by the teachers and the teaching assistants.
Other readings (non-mandatory):
- Barabási, A. L. (2013). Network science.
- NetworkX Documentation (Network Analysis in Python)
Metodologie Didattiche
The teaching will be realized through four different channels: theory lecture, exercise sessions, coding sessions and project.
Modalità di verifica dell'apprendimento
The assessment is made by: (a) three written evaluations on weeks 4, 8 and 12; (b) one project. Project is mandatory.
Each written evaluation is graded over 8. Each evaluation focuses on the preceding three weeks’ classes and is composed of a multiple-choice question and three exercises. Each student has to choose two out of the three exercises to solve. It is closed book. The total grade for the theory during the semester (three written evaluations) is 24 points. At the end of the semester, students can decide to reject or not this total grade. It is not possible to accept any of the three evaluation grades while rejecting another one.
The project is composed of a series of questions, approximately one for each week. It must be submitted as a Jupyter file (Python code + explanation). It should contain an introduction (around 250 words), a conclusion (around 250 words) and, for each question, explanations/analysis (100-150 words).
The maximal grade of the project will depend on when it is submitted. The precise deadlines (day and time) will be announced during the first class. If the project is submitted on week 12, the maximal grade is 8.5. If it is submitted before the first exam of the winter session, the maximal grade is 7.5. If it is submitted before the second exam of the winter session, the maximal grade is 7. A submission in any other session, will be graded over 6.
In addition, the students may (non-mandatory) submit an intermediate report on week 6 for a bonus of up to 1 point (at the discretion of the professors) and feedback.
For students who did not take/pass/accept the theory during the semester, the exam will be composed of a written exam with multiple-choice questions and three/four exercises. It is a closed book exam. The maximal total grade for the theory part (exam during winter session) is 22.5.
The teacher reserves the right to have an oral examination if the written exam or the project leaves some doubts. The students do not have the right to ask for an oral examination.
Criteri per l’assegnazione dell’elaborato finale
Interview.
Settimana 1
Basic concepts of graph theory.
Sessions 1-2: We will review some basic vocabulary when speaking about graphs and Networks.
Notions: Density, Degree, Network types, Network representations, Paths/Walk/Cycles, Matrix multiplication, directed and signed interactions
Session 3: Exercises.
Settimana 2
General connectivity features & small-world phenomenon
Sessions 1-2: Social networks exhibit very special features. We introduce the main ones.
Notions: Assortativity, Distances, Connectedness, Components, Trees, Shortest path, Social distance, Small world, Clustering.
Session 3: Exercises.
Settimana 3
Hubs & centrality measures.
Sessions 1-2: A key question when analyzing a social network is to determine the key agents. We will investigate different notions to classify the agents by importance.
Notions: Centrality Measures (Degree, Closeness, Betweenness, PageRankg), Centrality Distribution (Degree distributions), power-laws, Distribution of Neighbor’s Degree
Session 3: Exercises.
Settimana 4
Revision and Evaluation.
These sessions may change depending on the schedule.
Session 1: Mock Evaluation and Q&A
Session 2: Programming
Session 3: .Written Exam
Settimana 5
Assortativity & robustness.
Sessions 1-2: In many real-world networks, similar individuals tend to be connected together. This week will be dedicated to study homophily in social networks, and to investigate the robustness of real-world networks under a variety of different attacks
the specificities of Internet networks.
Session 3: Exercises.
Settimana 6
Network models.
Sessions 1-2: The aim of this chapter is to provide mechanical processes/algorithms that create graphs. We will present an historical approach and see if these models are representative of observed networks based on their degree distributions, diameter, and clustering.
Notions: Erdős–Rényi graphs (Definitions, Asymptotic behavior), Watts-Strogatz networks-Configuration Model, Preferential attachment (and some of its variants),
Communities.
Sessions 1-2: We have seen before the tendency of friends of someone to be friends. A challenging problem for marketer is to identify communities in Networks.
Notions: Community variables, Cohesion and separation, Methods and algorithms (e.g., Kernighan–Lin algorithm, Girvan–Newman algorithm, Stochastic Block Models), Evaluation methods.
Session 3: Exercises.
Settimana 7
Communities.
Sessions 1-2: We have seen before the tendency of friends of someone to be friends. A challenging problem for marketer is to identify communities in Networks.
Notions: Community variables, Cohesion and separation, Methods and algorithms (e.g., Kernighan–Lin algorithm, Girvan–Newman algorithm, Stochastic Block Models), Evaluation methods.
Session 3: Exercises.
Settimana 8
Revision and Evaluation.
These sessions may change depending on the schedule.
Session 1: Mock evaluation and Q&A.
Session 2: Programming
Session 4: Second written evaluation.
Settimana 9
Core-periphery & motif analysis.
Sessions 1-2: The aim of this chapter is to investigate a peculiar feature of many social networks, the presence of a core of tightly connected of nodes and of a periphery. We will also introduce the concept of motif analysis, and structural balance for signed social networks
Session 3: Exercises.
Settimana 10
Network Filtering.
Sessions 1-2: Very often networks are extremely large and with many edges. How can we reduce the dimensionality and simplify the representation of our network still preserving its most peculiar features? The aim of this week is to introduce methods for network filtering, and applying them to real-world social networks.
Session 3: Exercises.
Settimana 11
Network Dynamics.
Sessions 1-2: The aim of this week is to study the diffusion in a network of a technology, a disease or a discrete opinion. A typical example is the case of a disease where after an initial outbreak, an agent may infect its neighbor and so forth so on. We will see different theoretical models, analyze some of them theoretically, and simulate them.
Notions: Threshold models, Cascade, SIR model, SIS Model,
Session 3: Exercises.
Settimana 12
Revision and Evaluation.
These sessions may change depending on the schedule.
Session 1: Mock evaluation and Q&A.
Session 2: Third written evaluation.
Session 3: Programming
t.