Seminar of Computer Networks: Online Social Networks and Network Economics

Academic Year 2011 / 2012

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.

Announcements

7/5/2012: the first homework set is out and available here. It is due by May 31st, before the class
19/4/2012: Elias takes over classes.

Instructors

Prof. Stefano Leonardi, Sapienza University of Rome
Dr. Luca Becchetti, Sapienza University of Rome, email: luca.becchetti@dis.uniroma1.it
Prof. Elias Koutsoupias, University of Athens

When and Where

When: Thursdays, 10.15-13.40 (Room A3)    
Where: Via Ariosto 25, Room A3

Office Hours

Luca: we can arrange by email.

Book

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

Syllabus

We will cover some of the following topics, and maybe a few more to be decided:
Seminar series on Algorithmic Game Theory and Mechanism Design by Prof. Elias Koutsoupias
Part of the course will consist of a seminar series on Algorithmic Game Theory and Mechanism Design given by Professor Elias Koutsoupias. All lectures will be held on Thursdays, 10:15 - 13:30, Room A3, from April 19th to May 24th. An outline of the course and its schdule can be found here.

Homeworks, Exams

We will have two homework sets and a final project. The first homework set is available here. Solutions should be returned by May 31st, before the class. Hand in your solutions and keep a copy for yourself. After the due date we will post the solutions and in the final exam we will ask you to explain us what were your mistakes.

Instructions for the final project to come soon. As a reference, these were the projects for the Academic Year 2010/2011.

Handouts


Background Material

Basic combinatorics: Basic matirial for counting permutations and combinations, binomial coefficients, etc.

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

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.

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

Slides

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


Introduction: Introduction, structural properties

Probability - slides by Aris Anagnostopoulos and Luca Becchetti (the latter cover more aspects than needed):  Basic discrete probability, random variables, expectation

The small world phenomenon: small worlds, models of small world networks, navigability

Introduction to Epidemics: examples of epidemic models and their properties