From: "Ivona Bezakova" <ivona@cs.uchicago.edu>
Date: Thu, 18 Apr 2002 23:48:26 -0500

The Small-World Phenomenon: An Algorithmic Perspective
[Jon Kleinberg]

1. State the main contribution of the paper:
The author proposes a family of graphs to model the small-world
phenomenon and discusses its properties. This family is a generalization
of the preceding approaches and after tuning its parameters it can be
used to model a successful local routing algorithm (as opposed to just
pure existence of a short path). More precisely, the expected length of
the routing path used by this algorithm is poly-logarithmic in the
number of vertices. This statement is “if and only if”, i.e. if the
parameters are chosen differently, the expected routing path using any
local routing method is at least polynomial.

2. Critique the main contribution.  
   a. Rate the significance of the paper: 4-5. This theoretical study
      is related to different contexts – experimental data ranging from
      sociology to world-wide-web (?-see below). The results are simple
      and strong.
   b.  Rate how convincing the methodology is: 4-5. Well-written. 
   c. What is the most important limitation of the approach?
 
3. What are the three strongest and/or most interesting ideas in the
paper?
– The model itself, it seems to be natural and still quite intriguing. –
Ability to analyze the model (in so simple way!) and the strength of
  the results.
– Well-written for any type of audience.

4. What are the three most striking weaknesses in the paper?
– Proofs without restating Theorems to-be-proven.
– World-wide-web is mentioned in the abstract but no further evidence
  of it being a small-world is given.

5. Name three questions that you would like to ask the authors?
– Is there some well-established “definition” of the small-world
  phenomenon? [Or is it just the ability of finding short paths using
  local strategies?]

6. Detail an interesting extension to the work not mentioned in the
future work section.
See 7. Experimentally verify this model as a model for the Internet.

7. Optional comments on the paper that you’d like to see discussed in
class.
The study relates to small-world w.r.t. people’s relationships. The
model is natural in this context, people tend to know the best the
people living in close vicinity. How does it correspond to Internet, or
the web-linking structure?