Seminars in Computer Networks

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

Networks: An Introduction by M.E.J. Newman (Oxford University Press).
Networks, Crowds and Markets by D. Easley and J. Kleinberg (Cambridge University Press),
Networked Life by M. Chiang (Cambridge University Press).

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]

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.