network Models and Algorithms for Complex Networks



Reading List


Datasets and Code

Interesting Links


Homework 1

The first assignment is a programming assignment for performing measurements on networks. You can download the assignment sheet from
here. You can download the sample matlab file here.

Homework 2

The second assigment is a reaction paper. You can download the assignment sheet here.

Homework 3

The third assigment is a presentation. You will have to select a paper and present it in 20 minutes. You should submit a copy of your presentation in advance, so that we can print a copy of it. 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 have questions, or you get stuck with your presentation, feel free to email me, or Evimaria, to 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.
  • Study the structure of the wikipedia graph.
  • Study the structure of the reality mining dataset (data on the behavior of mobile phone users, available upon request).
  • 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. This will require to implement a clustering algorithm, and on top of that some ranking algorithm. For the clustering algorithm you can implement one of the algorithms described in class, or the one in 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
Other experimental projects would include implementation of an algorithm in some of the presented papers, or some of the papers in the reading list.

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. Possible survey topics include, small world phenomena in networks (includes a lot of theoretical papers), influence of search engines on ranking, biological networks (will require some understanding of biology).


The homework for the course will mix exercise sets, reaction papers, presentation and project.  It will be a little heavier than last year and more close tho the homework in 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 shoud 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 mostly mathematical, but there may also be some programming exercises.


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.