Seminars in Computer Networks -- Academic Year 2012/13: Networks Everywhere


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. Successfully striking examples are collaborative recommendation systems (e.g., Amazon for books and Netflix for DVDs), folksonomies - systems of collaborative social tagging - (e.g., Citeulike, Delicious, Flickr and Youtube), cooperative systems for building repositories of information as Wikipedia, systems of social networking (e.g., myspace, Facebook) and forum of discussion and opinion formation (e.g., blogs and Web communities). 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 second homework solutions have been published.


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

We will follow the book Networked Life by M. Chiang, published by Cambridge University Press. It will be complemented by lecture notes for some of the lectures.
Another useful reference is Networks, Crowds and Markets by D. Easley and J. Kleinberg (Cambridge University Press), which is available for download.


Syllabus

We plan a set of topics among the following:


Class 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.
DateTopicsRequired readingOptional reading

28/02/2013

Introduction

Distributed power control

[slides]

[C1]

[EK1]

 

07/03/2013

Game theory review

Auctions and sponsored web search

[notes]

[C2]

[EK6.1-6.8]

[EK15.1-15.5]

21/03/2013

Graph theory review

Ranking of web pages

[notes]

[C3]

[EK2]

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

04/04/2013

Collaborative filtering

[C4] (excluding C4.2.3, C4.4.1)

[C4.2.3, C4.4.1]

11/04/2013

Probability theory review

The wisdom of crowds

[notes]

[C5] (excluding C5.4)

 

[C5.4]

18/04/2013

Centrality and connectedness
 

Using Octave/Matlab

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

[slides] [scripts]

[EK3]
 

 

02/05/2013

Small-world networks

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

[EK20]

09/05/2013

Information cascades

Tipping and synchronization

[EK16.1-16.5]

[C7.1.2, C7.2.2, C7.3.2, C7.4.1]

[C7.2.1, C7.3.1]

[EK17.4]

16/05/2013

Cascading in networks

[EK19] (excluding EK19.4, EK19.6)

[EK19.4, EK19.6]

23/05/2013

Epidemics

Generative models of networks

[EK21.1, EK21.2, EK21.8.A]

[C10] (excluding C10.2.3, C10.3)

[C8.2.3-8.3.2]

[EK18]

30/05/2013

Distributed shortest paths

[C13] (excluding C13.4), [slides]

Physarum model and analysis


Homeworks

Homework 1

Homework 2


Projects

The instructions to prepare your project are here.