(Click here to go to the page for year 2015/16.)

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 highlypopular usercentric 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 online 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. 
Each student that does not attend 75% of the lectures will undergo an oral exam on the contents 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 be published 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 about the project and some sample projects.
Dr. Vincenzo Bonifaci, IASICNR
Contact address: (surname)@diag.uniroma1.it
When: Tuesday 9.1010.45, Wednesday 14.1015.40 and Friday 9.109.55
Where: Via Ariosto 25, Rooms A3 (Tuesday), A7 (Wednesday) and A3 (Friday)
Fridays, 10.3011.30 (Via Ariosto 25, Room B118)
All meetings have to be confirmed by email
The official textbook of the class is
The textbook will be complemented by lecture notes from the instructor for some of the lectures.
Another useful reference is
The notation [EKxx] refers to Chapter xx in the textbook by Easley and Kleinberg. Similarly, [Nxx] refers to a Chapter in the textbook by Newman.
Date  Topics  Required reading  Further reading 

21/2/2017 
Introduction Graph theory basics

[N1] [N6.16.4]


22/2/2017 
Connectivity and distances Triadic closure, strong and weak ties 
[notes 4] 
[N6.56.11]

24/2/2017 
Graph matrices and eigenvalues: 
[notes 1] 
[N6.16.4] 
28/2/2017 
Eigenvalues of an acyclic digraph 
[notes 23] 
[N6.16.4] 
1/3/2017 
Properties of the Laplacian matrix Centrality measures: degree and closeness 
[notes 3] [notes 12] 
[N7.6] 
3/3/2017 
Centrality measures: betweenness 
[EK3.6, EK3.B, notes 3] 
[N7.7] 
7/3/2017 
Centrality measures: eigenvector centrality The Power Method 
[notes 4] 
[N7.2] [N11.1] 
8/3/2017 
Analysis of the Power Method 
[notes 4.14.4] 
[N11.1] 
10/3/2017 
Power laws 
[N8.38.4] 

14/3/2017 
Computing the second dominant eigenvalue Centrality measures: Katz centrality 
[notes 4.55] 
[N7.3] 
15/3/2017 
Centrality measures: Pagerank 
[notes 6] 
[N7.4] 
17/3/2017 
Community structure: cliques, cores, kconnectivity 
[slides] 
[N7.8;11.2] 
21/3/2017 
Graph partitioning: the KernighanLin heuristic 
[notes 3.1] 
[N11.311.4] 
22/3/2017 
Graph partitioning: spectral partitioning 
[notes 3.2] 
[N11.5] 
24/3/2017 
Graph partitioning: spectral partitioning and conductance 
[notes 3.23.3] 
[N11.5] 
28/3/2017 
Community structure: assortativity and modularity 
[N7.13;11.711.8] 

29/3/2017 
Smallworld phenomenon Network models: ErdősRényi 
[N3.6] [N12.112.2] 

31/3/2017 
ErdősRényi: degree distribution 
[N12.312.4] 

4/4/2017 
ErdősRényi: the giant component WattsStrogatz and BarabásiAlbert 
[notes 2.4] [slides] 
[N12.5] [N14.2;15.1] 
5/4/2017 
Analysis of the Copying model 
[N14.5] 

7/4/2017 
Game theory: normal form games, dominant strategies 

11/4/2017 
Game theory: Nash equilibria, zerosum games 

12/4/2017 
Mixed Nash equilibria, graphical games Auctions, stable marriages 

19/4/2017 
Evolutionarily stable strategies 

21/4/2017 
Mixed evolutionarily stable strategies 
[EK7.5] 

26/4/2017 
Network traffic equilibria 

2/5/2017 
Potential energy and the social cost of equilibria 

3/5/2017 
Cascading behavior in networks 

5/5/2017 
Cascade capacity 

9/5/2017 
Epidemics and branching processes 

12/5/2017 
Myopic search in a small world 

16/5/201726/5/2017 
Lectures on markets by prof. S. Leonardi 
The instructions to prepare your project are here.