Seminars in Computer Networks

Seminars in Computer Networks -- Academic Year 2013/14: Networks Everywhere

(Click here to go to the page for year 2012/13.)

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

Please note that for the upcoming June exam, the only available dates for the discussion will be June 11 (afternoon) and June 12 (morning).

The homework has been released. It has to be completed by 29/5/2014.

See below for some notes about this homework.

Instructor

Dr. Vincenzo Bonifaci, IASI-CNR
Indirizzo per contatti / contact address: (cognome/surname)@dis.uniroma1.it

When and Where

When: Thursdays, 10.15-13.40 (Room A3)
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

Most material will be from one of the two books

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

Routing tables computation
Ranking of web pages
Wisdom of crowds
Small worlds
Decentralized search
Synchronization and diffusion
Information cascades
Epidemics and influence processes
Selfish interactions
Traffic equilibria

Class Diary (see here for last year's diary)

The notation [Cxx] refers to Chapter xx of the textbook by Chiang; similarly, [EKxx] refers to a Chapter in the textbook by Easley and Kleinberg.

Date Topics Required reading Optional reading

27/02/2014
Introduction
Graph theory review
Depth-first traversal
Map gossip
[slides]
[notes] [EK2]
[DF_Traversal]
[Map_Gossip]
[EK1]

06/03/2014
Shortest path algorithms
Ranking of web pages

[slides]
[C3]

[article]
[EK14.3, EK14.6.B, EK14.6.C]

13/03/2014
PageRank convergence
Probability theory review

[notes]
[notes]

[article] [survey]

20/03/2014
Wisdom of crowds
Power-law distributions
Generative models of networks

[C5] (excluding C5.4)
[article]
[EK18]

[article]
[article]
[C10] [article]

27/03/2014
Centrality measures
Connectedness, similarity, assortativity

[C8.1, C8.2.1, C8.2.2] [EK3.6]
[C8.4.2, C8.4.3]

[EK3]
[chapter]

03/04/2014
Small-world networks
Decentralized search

[C9] (excluding C9.2.2, C9.4.2)
[EK20.3, EK20.4, EK20.7.A]

[article 1, article 2]
[article]

10/04/2014
Pulse-based synchronization
Distributed averaging I

[C7.4.1]
[article sec. 1-3]

[article]

24/04/2014
Distributed averaging II
Information cascades

[article sec. 8.2-8.3]
[EK16.1-16.5]

[C7.2.1, C7.3.1]

08/05/2014
Cascading in networks
Epidemics

[EK19] (excluding EK19.4, EK19.6)
[EK21.1, EK21.2, EK21.8.A]

[EK19.4, EK19.6]
[C8.2.3-8.3.2]

15/05/2014
Introduction to game theory

[notes] [slides]

[EK6]

22/05/2014
Network traffic and congestion games
Guest Lecturer: Bart de Keijzer

[EK8]

[CG and Potentials] [PoA concept]
[PoS of LCG] [PoA of LCG]

29/05/2014
Mechanism design and auctions
Guest Lecturer: Bart de Keijzer

[Parkes] (Ch.2, until Sec.2.5)
[notes] (Sec.5 except 5.4.2)

[Parkes] (rest of Ch.2)
[notes] (Sec.5.4.2) [EK9]

Date	Topics	Required reading	Optional reading
27/02/2014	Introduction Graph theory review Depth-first traversal Map gossip	[slides] [notes] [EK2] [DF_Traversal] [Map_Gossip]	[EK1]
06/03/2014	Shortest path algorithms Ranking of web pages	[slides] [C3]	[article] [EK14.3, EK14.6.B, EK14.6.C]
13/03/2014	PageRank convergence Probability theory review	[notes] [notes]	[article] [survey]
20/03/2014	Wisdom of crowds Power-law distributions Generative models of networks	[C5] (excluding C5.4) [article] [EK18]	[article] [article] [C10] [article]
27/03/2014	Centrality measures Connectedness, similarity, assortativity	[C8.1, C8.2.1, C8.2.2] [EK3.6] [C8.4.2, C8.4.3]	[EK3] [chapter]
03/04/2014	Small-world networks Decentralized search	[C9] (excluding C9.2.2, C9.4.2) [EK20.3, EK20.4, EK20.7.A]	[article 1, article 2] [article]
10/04/2014	Pulse-based synchronization Distributed averaging I	[C7.4.1] [article sec. 1-3]	[article]
24/04/2014	Distributed averaging II Information cascades	[article sec. 8.2-8.3] [EK16.1-16.5]	[C7.2.1, C7.3.1]
08/05/2014	Cascading in networks Epidemics	[EK19] (excluding EK19.4, EK19.6) [EK21.1, EK21.2, EK21.8.A]	[EK19.4, EK19.6] [C8.2.3-8.3.2]
15/05/2014	Introduction to game theory	[notes] [slides]	[EK6]
22/05/2014	Network traffic and congestion games Guest Lecturer: Bart de Keijzer	[EK8]	[CG and Potentials] [PoA concept] [PoS of LCG] [PoA of LCG]
29/05/2014	Mechanism design and auctions Guest Lecturer: Bart de Keijzer	[Parkes] (Ch.2, until Sec.2.5) [notes] (Sec.5 except 5.4.2)	[Parkes] (rest of Ch.2) [notes] (Sec.5.4.2) [EK9]

Homework

Homework. The homework must be completed by 29/5/2014 (see instructions in the text).

Note about Problem 2: A typo in the formula stated in Problem 2 has been corrected (21/5/2014).

Note about Problem 3: The formula in point (a) refers to a definition of betweeness that involves a summation on all ordered pairs (s,t) of vertices, including the pairs with s=t.

Projects

The instructions to prepare your project are here.