T-61.6040 Project

Take at least two datasets from listed below and perform an experimental evaluation on one of the following topics.

1. Link analysis algorithms from the paper:
   A. Borodin, G. Roberts, J. Rosenthal, P. Tsaparas, Link Analysis Ranking: Algorithms, Theory and Experiments, ACM Transactions on Internet Technologies (TOIT), 5(1), 2005
2. Statistical measures on networks from the paper:
   M. E. J. Newman, The structure and function of complex networks, SIAM Reviews, 45(2): 167-256, 2003.
3. Network propagation effects from the paper:
   D. Kempe, J. Kleinberg, E. Tardos. Maximizing the Spread of Influence through a Social Network. Proc. 9th ACM SIGKDD Intl. Conf. on Knowledge Discovery and Data Mining, 2003.
4. Graph clustering from the paper:
   Satu Elisa Schaeffer. Graph Clustering. Computer Science Review 1(1):27-64,2007.

In each of the suggested papers you will find several algorithms or measures you can experiment with. The idea is that you try those algorithms/measures on selected datasets and derive corresponding conclusions. You can also implement your own solutions if you feel like it (whatever extra work you do will count for a better grade). In case you choose project 2, it would interesting to select two very different datasets to allow for a better comparison of the results.

Write a report of the experimental study containing the following points:

• Task for your project
• Brief explanation of the algorithms/measures implemented
• Datasets selected. Brief description of those datasets
• Which experiments you carried out
• Figures of the experiments
• Results and conclusions
• Include your code into Appendix.

Note: You can also propose your own project by selecting another paper with different algorithms on one of the topics above. Also you can crawl your own data from the web, or find other better datasets online. Email us to discuss about it.

Datasets

• AS Graph (use only 20020201 or 20020209).
• Italian Wikipedia graph, format: (from to) (directed)
• French Wikipedia graph, format: (from to) (directed)
• Czech Wikipedia graph, format: (from to) (directed)
• Data Sets for Link Analysis Ranking Experiments
  Related page: Collections of web pages related to queries used for testing Link Analysis Ranking algorithms
• Coauthorship graph
• US Power Grid
• AS Graph Data Sets
• The citation graph of the hep-th portion of the arXiv from KDD Cup 2003

Tips

Use appropriate language, for instance, Matlab or Python. If you decide to use C or C++, then you are on your own.

Write the expriments in a batch file so you can easily repeat them should you find any errors within your code.

Matlab code for reading the graphs into Matlab can be found here.