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 is
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
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
- Lada A. Adamic, Rajan M. Lukose, Amit R. Puniyani,
A. Huberman. Search
Phys. Rev. E, 64 46135 (2001).
- Michalis Faloutsos, Petros Faloutsos and Christos
On Power-Law Relationships of the Internet Topology.
ACM SIGCOMM 1999.
- Deepayan Chakrabarti, Yiping Zhan and Christos
R-MAT: A Recursive Model for Graph Mining
SIAM Int. Conf. on Data Mining, April 2004.
- V. Nguyen and C. Martel. Analyzing
graphs. To appear in the 2005 ACM-SIAM symposium
- D. J. Watts, P. S. Dodds, and
M. E. J. Newman, Identity
search in social networks, Science
1302-1305 (2002). (Hannu Maksimainen)
- C. Martel and V. Nguyen. Analyzing
(and other) small-world
models. In the 23rd ACM Symposium on Principles of
pp. 179-188, 2004.
- M. Naor, U. Weider Know
Neighbor’s Neighbor: Better Routing for Skip-Graphs
and Small Wolds
- P. Fraigniaud, C. Gavoille, and C. Paul, Eclecticism
Even Small Worlds, 23rd ACM Symp. on Principles of
- D.M. Pennock, G.W. Flake, S. Lawrence, E. J. Glover,
take all: Characterizing the competition for links on
Proc. of the National Academy of Sciences, 2002
- Z. BarYossef, A. Broder, R. Kumar and A. Tomkins.
Telae: Towards an Understanding of theWeb's Decay.
Proceedings of the Thirteenth International World Wide
New York, New York, 2004. (Sini Ruohomaa)
- Micah Adler, Michael
Web Graphs in Proceedings of the IEEE
Conference (DCC), 2001.
- M. Henzinger, A.
Mitzenmacher, and M. Najork. Measuring
Quality using Random Walks on the Web.
8th International World Wide Web Conference, May
- M. Diligenti, F.M.
S. Lawrence, C.L. Giles, M. Gori Focused
Using Context Graphs.
26th International Conference on Very Large
Databases, VLDB 2000.
- A. Y. Ng, A. X. Zheng,
M. I. Jordan. Stable
for link analysis.
24th International Conference on Research and
Information Retrieval (SIGIR 2001).
- Taher H. Haveliwala. Topic-Sensitive
11th International World Wide Web Conference, 2002.
- J. Cho, S. Roy,
Search Engines On Page Popularity, WWW 2004 (Papp Zoltan)
- N. Eiron, K. S.
McCurley, J. A. Tomlin, Ranking
Web Frontier, WWW 2004
- R. Guha, R. Kumar, P. Raghavan, A. Tomkins, Propagation
Trust and Distrust WWW
- R. B. Almeida, V. A. F.
Community-Aware Search Engine WWW
Chen, Y. Lu, S.
Ma, E. A. Fox, Link
A Unified Link Analysis Framework for Multi-Type
Objects WWW 2004
- K. Berberich, M.
Vazirgiannis, G. Weikum, T-Rank:
Aware Authority Ranking, WAW 2004 (Markus
Mohammad Mahdian, D. Sivakumar, Searching
workplace web, WWW 2003 (Edit Bodorkos)
- P. Ferragina, A. Gulli, F. Romani, Ranking
News, To appear in WWW2005
Ravi Kumar and D. Sivakumar Comparing
lists, Extended abstract in 2003
ACM-SIAM Symposium on Discrete Algorithms (SODA '03),
Balakrishnan, and David Karger. Analysis
the Evolution of Peer-to-Peer Networks. In
of PODC 2002.
in Unstructured Peer-to-Peer Networks.
Goel, H. Zhang, and R. Govindan.
Using the Small-World Model to Improve Freenet
IEEE Infocom, 2002.
- A. Rowstron, P. Druschel. Pastry:
distributed object location and routing
for large-scale peer-to-peer systems.
18th IFIP/ACM International Conference on Distributed
Platforms (Middleware 2001).
- B. Y. Zhao, J. D. Kubiatowicz, A. D. Joseph, Tapestry:
Infrastructure for Fault-Tolerant Wide-Area
Location and Routing.
UC Berkeley Computer Science Division, Report No.
R. Guha, David Liben-Nowell, and
Andrew Tomkins. Information Diffusion through Blogspace
version). Proceedings of WWW'04.
- C. R. Myers,
"Software systems as complex networks: structure,
evolvability of software collaboration graphs", Phys.
68, 046116 (2003).
Liben-Nowell, J. Kleinberg. The
Prediction Problem for Social Networks.
Proc. 12th International Conference on Information and
Management (CIKM), 2003.
- Christos Faloutsos, Kevin McCurley and Andrew
of 'Connection Subgraphs' KDD 2004, Seattle, WA,
- Jasmine Novak, Prabhakar Raghavan, Andrew
on the web. WWW
2004: 30-39 (Pekka
- Ravi Kumar, Uma Mahadevan, Sivakumar: A
to extract storylines from search results. KDD 2004: 216-225
If you have questions, or you get stuck with your
project, feel free to email me, and we can arrange
to meet and discuss
some possible topics for experimental projects.
also propose your own ideas for projects. Please contact
me to discuss
further about your project. Survey type of projects are
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.
site http://www.cs.helsinki.fi and generate the
(that is, the graph of the web pages that are within
this domain, and
the links between them -- no outside pages, or links).
underlying graph by making standard measurements. Code
pages and extracting links is provided in Perl. This
project could be
done by more than one person.
structure of the wikipedia graph
datasets on web search data, and the results of
Analysis Algorithms, experiment with different
datasets on web search data, experiment with various
algorithms that make use of the link structure. You
various Link Analysis Ranking algorithms, as well try
have not been applied to the Web.
the idea of combining clustering and ranking. One
is to implement the ideas in (or
ideas along the
lines of) the paper,
Distributed Hashing Protocol (e.g. the Freenet, or the
site percolation,virus propagation, immunization on
of the course
for the course will be tailored again along the
lines of Kleinberg's
course (click here
description of the coursework for this
course). Below are the
different types of homework.
Any problem sets will be posted here.
the reaction paper you should select at least two papers
some section of the course, that have not been already
write a report of approximately 3 pages, where you
include the following
- Summary of the main contribution and technical
the papers, and how they relate to each other.
- Discussion on how the papers relate to the topics of
- Discussion about the shortcomings of the papers, and
possible future directions.
The reaction paper should not
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.
Depending on the material covered in class
there may be an
exercise set related to the papers covered. The
exercises will be
on the number of people that take the class, instead of a
paper, there may be a presentation. In this case you will
be asked to
select a paper and present it in 20 minutes.
the project you are asked to select your favorite network
and study it.
You can do the following type of projects:
to produce a report with your findings of about 10-15
should start thinking about the project early on, and you
it with me or Evimaria if you need direction. Large
projects could be
split between two people. I would recommend that you do a
project, unless you are strong theoretically, or you feel
you can offer
a new perspective to the analysis of a network. A type 3
not be an extended reaction paper, and it will be graded
to the new ideas it generates.
- An experimental analysis of the network with respect
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
the dataset this will be counted towards the final
- A rigorous theoretical analysis of an algorithm or
related to the network.
- An in-depth survey that makes a critical analysis of a
topic and offers a new perspective.