Seminar of Computer Networks: Online Social Networks and Network Economics

Academic Year 2010 / 2011

Online social networks have become a major driving phenomena on the web since the Internet has expanded as to include users and their social systems in its description and operation. Internet has developed from a communication medium and information sharing devise into a platform enabling a wide range of new social activities and applications. 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, tags, annotations, 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, algorithms for data mining in social networks, and some network economic issues.


26/6/2011: Solutions to Homework 2 are available: Solutions

8/6/2011: On request Homework 2 has been revised. There are 5 problems altogether now from which you are supposed to solve 4. Solutions are due on June 24 and can be handed-in in office B118.

7/6/2011: The second homework is out and due on June 24. Solutions can be handed-in in office B118.

6/6/2011: We have posted a list of potenital projects to choose from. On Wednesday, 8/6 we will have a short discussion about the projects.

24/5/2011: The solutions to the first homework have been published.

9/5/2011: There was a mistake with the equations of Problem 5 in the first homework. Please download the updated version.

6/5/2011: There will be no classes on Monday, 16/5/2011 and Monday, 30/5/2011.

6/5/2011: Class notes available (will be updated weekly).

2/5/2011: Guido takes over classes.

19/4/2011: Aris will be out of Rome until the end of April. You can come at office hours or email for an appointment for questions on the class material or the homework after May 1st.

19/4/2011: The first homework is out and due on May 18. It has 4 theoretical questions and a data-mining one. Read carefully the instructions. If you do not have a partner and you would like one, you can mail to to try to match you up. Please start early, as the questions are not completely trivial.

11/4/2011: On Wednesday, 20/4/2011, since there is no available room at the regular time, the class will be at 10.15-11.45 at Aula A7.

28/3/2011: On Wednesday, 30/3/2011, since there is no available room at the regular time, the class will be at 3.45-5.15 at Aula A5.

28/3/2011: The class times are Monday, 3.45-5.15 (Aula A7) and Wednesday 2.00-3.30 (Aula A6).

23/3/2011: The class times are Monday, 3.45-5.15 and Wednesday 2.00-3.30, in Room A7.

16/3/2011: There is no class on Monday 21/3. On Wednesday, 23/3 we have class at 2.00-3.30, at Aula A7.


Prof. Stefano Lenardi, Sapienza University of Rome
Dr. Aris Anagnostopoulos, Sapienza University of Rome, email:
Prof. Guido Schäfer, Centrum Wiskunde & Informatica (CWI), Amsterdam

When and Where

When: Monday 15.45-17.15 (Aula A7) and Wednesday 14.00-15.30 (Aula A6).
Where: Via Ariosto 25, Aule A6, A7

Office Hours

Aris: Wednesday, after class, office B118. If you have classes at this time we can arrange by email.


There does not exist a book for the class material. We will post the slides and maybe some notes for some of the lectures.


We will cover some of the following topics, and maybe a few more to be decided:

Homeworks, Exams

We will have two homework sets and a final project.

Homework 1 (updated 9/5) (due May 18, before class)
Solutions for Homework 1.
Homework 2 (due June 24)
Solutions for Homework 2.

Note that the final exams will be on June 28 and July 11, 2011.

Instructions for the final project.


Background Meterial

15/3/2011: Basic combinatorics
Basic matirial for counting permutations and combinations, binomial coefficients, etc.

15/3/2011: Introduction to probability
Here you can find a brief introduction to probability. Make sure that you understand all the material.

15/3/2011: Random variables
This describes random variable, expectation, variance, and other related topics. We will work mostly with discrete random variables but you should know the basics for the continuous ones.

15/3/2011: Main distribution functions
It describes the main types of distributions. Definitely understand Section 5.1 and you can study the rest when we do them in the class


Make sure that you read also the lecture notes for the material we covered and is not in the slides (networks models, etc.).

15/3/2011: Introduction, 14/3/2011: Introduction, structural properties

23/3/2011: Probability, 16/3/2011: Basic discrete probability, random variables, expectation

6/4/2011: Introduction to Epidemics, 4/4/2011, 6/4/2011 (updated 6/4/2011)

6/4/2011: Influence Maximization, 6/4/2011

13/4/2011: Introduction to Community Detection and Centrality, 11/4/2011, 13/4/2011