Obiettivi formativi
The course will provide the basic tools for the analysis of social networks, drawing from graph theory, probability, game theory, optimization. The course will focus on questions inspired from real-life situations involving networks.
Prerequisiti
Knowledge and understanding:
The course will offer key theoretical tools to model social 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 Networks 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 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 some of the most relevant tools and tasks within Social Network Analysis. Finally, we will study diffusion/contagion in Networks and investigate the consequences in terms of external interventions.
Testi Di Riferimento
Textbook:
- Menczer, F., Fortunato, S., & Davis, C. (2020). A First Course in Network Science. Cambridge: Cambridge University Press. doi:10.1017/9781108653947.
- Notes on Luiss Learn.
- Exercises provided by the teachers and the teaching assistants.
Other readings (non-mandatory):
- Barabási, A. L. (2013). Network science. Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences, 371(1987), 20120375.
- Jackson, M.O., Social and Economic Networks, Princeton University Press 2010.
- 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.
Session 3: Exercises.
Settimana 2
Small world.
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.
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), Centrality Distribution (Degree distributions), Distribution of Neighbor’s Degree, Core decomposition.
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
Directions and Weights.
Sessions 1-2: In many applications like internet pages, it is more reasonable to consider directed graph. This week will be dedicated to study the specificities of Internet networks.
Notions: Page Rank (centralities), Directed Networks, Cascade networks, WWB, Co-occurrences Networks.
Session 3: Exercises.
Settimana 6
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
Link Prediction.
Sessions 1-2: One of the most relevant problems in Social Networks is predicting how likely it is for two people to become friends. This is achieved through Link Prediction.
Notions: Topological similarity indices, Attribute-based features, Models, Evaluation methods, Applications to Friendship Recommendation in Facebook.
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
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.
Notions: Random Networks, Erdős–Rényi graph (Definitions, Asymptotic behavior), Configuration Model, Preferential attachment (and some of its variants), Differential equation.
Session 3: Exercises.
Settimana 10
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, Differential equations (Steady State).
Session 3: Exercises.
Settimana 11
Opinion Diffusion.
Sessions 1-2: In some situations, like reviews on internet, it is more reasonable to have a large number or even a continuous number of possible opinions. We will introduce the model of De Groot to simulate diffusion of opinions when an opinions is represented by a real number.
Notions: Degroot model, Consensus/Polarization/Fragmentation, Simple Linear system,
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.