Seminars in Computer Networks -- Academic Year 2014/15
(Click here to go to the page for year 2013/14.)
|
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
The exam originally scheduled for 11/06/2015 will be held on 18/06/2015 (same hour and room)
The exam originally scheduled for 16/07/2015 will be held on 23/07/2015 (same hour and room)
Instructor
Dr. Vincenzo Bonifaci, IASI-CNR
Contact address: (surname)@diag.uniroma1.it
When and Where
When: Thursdays, 10.15-13.40
Where: Via Ariosto 25, Room A3
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 one of the books
They will be complemented by lecture notes for some of the lectures.
Syllabus
Aspects of networks. Social networks and networks of information.
Mathematics of networks. Networks and their representation. Adjacency matrix, incidence matrix and other data structures. Connectivity and distances. Independent paths and cuts. Graph Laplacian.
Measures of centrality. Degree centrality, Eigenvector centrality, Pagerank. Ranking of web pages. Closeness centrality, betweenness centrality. Similarity measures: cosine similarity, Pearson coefficient. Homophily and assortative mixing.
Large-scale structure of networks. Shortest paths and small-world phenomenon. Degree distributions. Power laws and scale-free networks. Clustering coefficients.
Matrix algorithms and graph partitioning. Power method for eigenvector centrality and Pagerank. Clustering problem and spectral partitioning. Community detection and modularity maximization methods.
Network models. Random graphs. Preferential attachment. Vertex copying models. Network optimization models. The small-world model.
Processes on networks. Information cascades and cascading in networks. Epidemics and influence processes. Network search and message passing. Random walks on networks. Network traffic and equilibria.
Class Diary (see here for last year's diary)
The notation [Nxx] refers to Chapter xx in the textbook by Newman. Similarly, [Cxx] refers to Chapter xx in the textbook by Chiang; and [EKxx] refers to a Chapter in the textbook by Easley and Kleinberg.
Date | Topics | Required reading | Optional reading |
26/02/2015 |
Introduction Graph theory basics |
[slides] [notes 1-4] | [N1, EK1] [N6.1-6.4, EK2] |
05/03/2015 |
Connectivity, planarity Independent paths, cuts |
[notes 5-8] |
[N6.5-6.12] |
12/03/2015 |
Graph Laplacian Degree, eigenvector centralities |
[notes 9] [notes 1-2.2] |
[N6.13-6.14] [N7.1-7.2;N11.1] |
19/03/2015 |
"Kolmogorov meets Turing" workshop |
|
|
26/03/2015 |
Power method Katz centrality, Pagerank |
[notes 2-4] |
[N7.3-7.4;N11.1.1-N11.1.2] [EK14.3,14.B] |
02/04/2015 |
Spring break |
|
|
09/04/2015 |
Closeness, betweenness Cosine similarity, Pearson coefficient |
[notes 5-6], [EK3.6-3.6B] [N7.12-7.12.2] |
|
16/04/2015 |
Graph partitioning |
[notes 1] |
[N11.4-11.5] |
23/04/2015 |
Assortativity and clustering Random graphs |
[notes 2], [N7.13;N11.8] [notes 1-2.2], [N12.1-12.4] |
[EK3.6A] |
30/04/2015 |
Giant and small components Small world phenomenon |
[notes 2.3-2.4], [N12.5-12.6.1] [EK20.3,20.4,20.7.A] |
[article 1, 2, 3] |
07/05/2015 |
Power-law distributions Generative models of networks |
[article] [EK18] |
[article] [C10] [article] |
14/05/2015 |
Game theory I |
[notes 1] [slides] |
[EK6] |
21/05/2015 |
Game theory II Network cascading |
[EK19] (excluding EK19.4, EK19.6) |
[EK19.4, EK19.6] |
28/05/2015 |
Network traffic equilibria |
[notes 2] [EK8] |
[article 1, 2] |
Projects
The instructions to prepare your project are here.