network Information Networks



Reading List


Datasets and Code

Interesting Links


Homework 1

Homerwork 1 is a problem set. You can download it from here. The due date is April 14th in class. On Monday, April 4th there will be a tutorial about the first assignment.

Homework 2

Homework 2 is a presentation. You will have to select a paper and present it in 20 minutes. The presentations will take place in the last week of the course, but you are required to submit your slides (the presentation file, or copy of the slides) on May 3rd. For the presentation, you can select any of the papers below, or propose a paper yourself (you should send me an email to discuss about it). Papers will be handed out in first come first serve fashion.
(If you are interested in doing a presentation on P2P, epidemic spreads in networks, or biological networks let me know. I did not have the time to add links for these topics)

If you have questions, or you get stuck with your presentation or project, feel free to email me, and we can arrange to meet and discuss about it.


Here are some possible topics for experimental projects.
  • Crawl the site and generate the underlying graph (that is, the graph of the web pages that are within this domain, and the links between them -- no outside pages, or links). Study the underlying graph by making standard measurements. Code for fetching pages and extracting links is provided in Perl. This project could be done by more than one person.
  • Study the structure of the wikipedia graph
  • Using the datasets on web search data, and the results of various Link Analysis Algorithms, experiment with different rank-aggregation algorithms.
  • Using the datasets on web search data, experiment with various ranking algorithms that make use of the link structure. You could implement various Link Analysis Ranking algorithms, as well try heuristics that have not been applied to the Web.
  • Experiment with the idea of combining clustering and ranking. One specific project is to implement the ideas in (or ideas along the lines of) the paper,
  • Simulate a Distributed Hashing Protocol (e.g. the Freenet, or the Symphony P2P network).
  • Experiment with site percolation,virus propagation, immunization on the datasets of the course
You can also propose your own ideas for projects. Please contact me to discuss further about your project. Survey type of projects are also possible, but they should be more than just a summary of a few papers. You should propose some future direction, and I would strongly recommend that you provide some indicative experiments.


The homework for the course will be tailored again along the lines of Kleinberg's course (click here for a description of the coursework for this course).  Below are the different types of homework.

Any problem sets will be posted here.

Reaction Paper

For the reaction paper you should select at least two papers relevant to some section of the course, that have not been already discussed, and write a report of approximately 3 pages, where you should include the following
  • Summary of the main contribution and technical content of the papers, and how they relate to each other.
  • Discussion on how the papers relate to the topics of the course.
  • Discussion about the shortcomings of the papers, and possible future directions.
The reaction paper should not be just a summary of papers. The objective is to do a synthesis of ideas, find some interesting related work that was not covered, think about a problem, and about possible interesting questions.

Exercise Set

Depending on the material covered in class there may be an exercise set related to the papers covered. The exercises will be mathematical.


Depending on the number of people that take the class, instead of a reaction paper, there may be a presentation. In this case you will be asked to select a paper and present it in 20 minutes.


For the project you are asked to select your favorite network and study it. You can do the following type of projects:
  1. An experimental analysis of the network with respect to measurements, algorithms or models. You can use one of the datasets in the course home page or some dataset available on the Web, or you can collect your own data. If substantial work is required for collecting the dataset this will be counted towards the final grade.
  2. A rigorous theoretical analysis of an algorithm or model related to the network.
  3. An in-depth survey that makes a critical analysis of a topic and offers a new perspective.
You are expected to produce a report with your findings of about 10-15 pages.  You should start thinking about the project early on, and you can discuss it with me or Evimaria if you need direction. Large projects could be split between two people. I would recommend that you do a type 1 project, unless you are strong theoretically, or you feel you can offer a new perspective to the analysis of a network. A type 3 project should not be an extended reaction paper, and it will be graded with respect to the new ideas it generates.