Seminars in Social Networks and Markets -- Academic Year 2015/16
(Click here to go to the page for year 2014/15.)
|
The social network of A Game of Thrones. Read how it was built
|
We are surrounded by networks. The Internet, one of the most advanced artifacts ever created by mankind, is the paradigmatic example of a "network of networks" with unprecedented technological, economical and social ramifications. Online social networks have become a major driving phenomenon on the web since the Internet has expanded as to include users and their social systems in its description and operation. Technological networks such as the cellular phone network or the energy grid support many aspects of our daily life.
Moreover, there is a growing number of highly-popular user-centric applications in Internet that rely on social networks for mining and filtering information, for providing recommendations, as well as for ranking of documents and services.
In this course we will present the design principles and the main structural properties and theoretical models of on-line social networks and technological networks, algorithms for data mining in social networks, and a few network economic issues, with an eye towards the current research issues in the area.
|
Announcements
Updated Exam Rules
Each student has to attend 75% of the lectures or, alternatively, undergo an oral exam on the content of the course (as defined in the Syllabus and the Class Diary). Attendance in class is highly recommended.
Each student is required to complete any homework that will be assigned in class; any such assignment will also appear on this website.
Finally, each student will be assigned a project (either a software project or a literature survey) and will have to present and discuss the project at the exam. See the bottom of this webpage for more details on the project.
Instructors
Dr. Vincenzo Bonifaci, IASI-CNR
Contact address: (surname)@diag.uniroma1.it
Dr. Francesco Pasquale, Sapienza University of Rome
Contact address: (surname)@diag.uniroma1.it
When and Where
When: Tuesday 12.00-13.30 and Thursday 12.00-13.30
Where: Via Ariosto 25, Rooms A3 (Tuesday) and A2 (Thursday)
Office Hours
Thursdays, 15.00-16.00 (Via Ariosto 25, Room B118)
All meetings have to be confirmed by email
Book(s)
Most material will be from either of the books
The books will be complemented by lecture notes for some of the lectures.
Syllabus
Network structure:
graph theory and social networks;
measures of centrality;
homophily and assortative mixing;
power laws and scale-free networks;
communities and modularity.
Network dynamics:
information cascades and cascading in networks;
epidemics and influence processes;
network search and message passing;
random walks on networks.
Strategic interaction in networks and online markets:
network traffic and equilibria;
algorithmic mechanism design and computerized auctions;
market equilibria;
matching markets;
online labor marketplaces;
voting mechanisms.
Class Diary (see here for last year's diary)
The notation [Nxx] refers to Chapter xx in the textbook by Newman. Similarly, [EKxx] refers to a Chapter in the textbook by Easley and Kleinberg.
| Date | Topics | Required reading | Further reading |
23/02/2016 |
Information cascades: A simple cascade model and its analysis |
[EK16] |
Bikhchandani et al. 1992 |
25/02/2016 |
Network effects: Stable and unstable equilibria and dynamic view |
[EK17.1-17.6] |
W. Brian Arthur 1994 |
01/03/2016 |
Examples of networks and their properties Graph theory review I |
[EK1] [notes 1-3] [EK2] | [N1] [N6.1-6.4] |
03/03/2016 |
Graph theory review II Triadic closure, strong and weak ties |
[notes 4] [EK3.1] | [N6.5-6.11] Granovetter 1973 |
08/03/2016 |
The Rich-Get-Richer phenomenon: Preferential attachment model and analysis of its mean-field approximation |
[EK18] | Broder et al. 2000 Barabasi and Albert 1999 Bollobas et al. 2001 |
10/03/2016 |
Local bridges and weak ties Introduction to centrality measures: betweenness |
[EK3.2-3.3] [EK3.6B] [notes 6] |
[N7.7] Riondato and Kornaropoulos 2014 |
15/03/2016 |
Game theory: Rationality and common knowledge. Strategic games, dominant strategies, Nash equilibria. |
[EK6] | Nash 1951 Aumann 1976 |
17/03/2016 |
Centrality measures: eigenvector centrality |
[notes 5] [notes 2] |
[N6.2] [N7.2] |
22/03/2016 |
Game theory: Game theory beyond rationality: Evolutionary dynamics Evolutionary Stable Strategies vs Nash equilibria |
[EK7] | Maynard Smith 1974 |
24/03/2016 |
Centrality measures: analysis of the power method |
[notes 2] |
[N6.2] [N7.2] |
24/03/2016 |
Centrality measures: Katz centrality, Pagerank, closeness |
[notes 3-5] |
[N6.14] [N7.3-7.6] [EK14.3, 14.B-C]
Brin and Page 1998 |
07/04/2016 |
Cascading in networks: Simple networked coordination game Cascades and clusters Cascade capacity of an infinite network |
[EK19] | Morris 2000 |
12/04/2016 |
Graph partitioning: local search, spectral method |
[notes 1.1-1.2] |
[N11.4-11.5] |
14/04/2016 |
The Small-World phenomenon: The Watts-Strogatz model Decentralized search and analysis of the one-dimensional Kleinberg model |
[EK20] | Kleinberg 2000 |
19/04/2016 |
Epidemics: SIR, SIS, SIRS, and analysis of a simple branching process. "Mitochondrial Eve" and coalescence.
|
[EK21] | Nowzari et al 2016 Cann et al 1987 |
21/04/2016 |
Graph partitioning: analysis of the spectral method Partitioning without given sizes |
[notes 1.2-1.3] |
Chung 2007 |
26/04/2016 |
Voting systems: Majority rule and Borda count, pathologies.
Arrow's impossibility theorem
|
[EK23.1-23.5, EK23.11] | Arrow 1950 Tabarrok and Spector 1999 Geanakoplos 2005 |
28/04/2016 |
Assortativity and modularity Divisive and agglomerative clustering methods |
[notes 2] |
Newman and Girvan 2004 Newman 2004
|
03/05/2016 |
Lecture by prof. Leonardi |
TBA |
|
05/05/2016 |
Traffic equilibria: existence proof via Lagrange multipliers |
[notes 1-2] Kelly 2008 sections 1-3 |
[EK8] |
10/05/2016 |
Lecture by prof. Leonardi |
TBA |
|
17/05/2016 |
Lecture by prof. Leonardi |
TBA |
|
19/05/2016 |
Congestion control: TCP as utility maximization |
[notes 1-2] Kelly 2008 sections 4-6 |
[EK8] |
Projects
The instructions to prepare your project are here.