COS 425, Fall 2006 - Problem Set 4, Part II: ranking in social networks
Due at 1:30pm, Monday Nov. 13, 2006.
Collaboration Policy
You may discuss problems with other students in the class. However,
each student must write up his or her own solution to each problem
independently. That is, while you may formulate the solutions to
problems
in collaboration with classmates, you must be able to articulate the
solutions on your own.
Late Penalties
- 10% of the earned score if submitted after class but by 5pm the
day due.
- 30% of the earned score if submitted by 5pm on Wednesday
11/15/06.
- No credit if submitted later than the 30% penalty
deadline
There is one problem with 4 parts:
In this problem you will compute hubs and authority weights and
pageranks
for the following graph:
|------<------^
V |
Node_1 ---> Node_2 ---> Node_3 ---> Node_4-|
^ |
| |
|------------<------------
That is, there are edges from Node 1 to Node 2, from Node 2 to Node 3,
from Node 3 to Node 4, from Node 4 to Node 2 and from Node 4 to Node 3.
Both hub and authority weights and pageranks are obtained from
iterative
formulae. Write a small program to calculate these values. Specifically,
compute:
- Part a Final
hub and authority weights for all nodes.
- Part b The final pagerank of all nodes when parameter q is set to 0.15 .
- Part c The final pagerank of all nodes when parameter q is set to zero.
The final values are the results of stopping the iterative computation
when some convergence criterion (or criteria) has been met. Say
what convergence criteria
you
are using in each part. Also give the values after each iteration
to
show how the values converge. You may "hardwire" the graph into
your program, i.e. your program need not take the graph specification
as an input. Submit
your program and its output, either by email or printed. Notes on the algorithms based
on our class discussion have been posted here.
Also:
- Part d Compare the
results of Parts a and b. Specifically, if authority is
used for ranking, which results do you find match your intuition about
the ranking of the nodes (assuming the results of Parts a and b give
different rankings). Give reasons.