Assigned:
Mon 27 July 2009
Due:
Thu 13 August 2009 (last day of classes;hard deadline)
// M(p) is a list of pages that link to page p
// L(q) is the number of out-links from page q
// d is the PageRank damping/teleportation factor; use d = 0.85 as is typical
foreach page p
PR(p) = 1/N /* initial value */
while PageRank has not converged do
foreach page p
newPR(p) = (1-d)/N /* teleportation value */
foreach page q in M(p) /* pages pointing to p */
newPR(p) += d*PR(q)/L(q) /* add share of PageRank from in-links */
foreach page p
PR(p) = newPR(p)
return PR
In order to facilitate the computation of PageRank using the above
pseudocode, one would ideally have access to an in-link respresentation
of the web graph, i.e., for each page p, a list of the pages q that
link to p. For example, given the graph shown in Problem 5 from
HW03, one such representation would be
as follows
A D E F B A F C A B D D B C E B C D F F A B Dwhere the first line indicates that page A is linked from pages D, E, and F, and so on. Note that unlike the example in HW03, in a real web graph, not every page will have in-links, nor will every page have out-links.
To hand in: List the PageRank values you obtain for each vertex after 1, 10, and 100 iterations of the PageRank algorithm.
Run your iterative version of PageRank algorithm until your PageRank values "converge". To test for convergence, calculate the perplexity of the PageRank distribution, where perplexity is simply 2 raised to the entropy of the PageRank distribution, i.e., 2H(PR). Perplexity is a measure of how "skewed" a distribution is --- the more "skewed" (i.e., less uniform) a distribution is, the lower its preplexity. Informally, you can think of perplexity as measuring the number of elements that have a "reasonably large" probability weight; technically, the perplexity of a distribution with entropy h is the number of elements n such that a uniform distribution over n elements would also have entropy h. (Hence, both distributions would be equally "unpredictable".)
Run your iterative PageRank algorthm, outputting the perplexity of your PageRank distibution until the perplexity value no longer changes in the units position for at least four iterations. (The units position is the position just to the left of the decimal point.)
For debugging purposes, here are the first five perplexity values that you should obtain (roughly):
and here are the document IDs of the top 11th to the top 20th document:
11. WT13-B06-273 0.000566116521682172 12. WT01-B18-225 0.000535404440806094 13. WT04-B27-720 0.00050754054544844 14. WT23-B19-156 0.000484548060707884 15. WT04-B30-12 0.000442504333881711 16. WT24-B26-10 0.000436743798615904 17. WT25-B15-307 0.000435706978760228 18. WT24-B26-2 0.000417854675793139 19. WT07-B18-256 0.000416883044639094 20. WT14-B03-220 0.000385708838588178To hand in: List the perplexity values you obtain in each round until convergence as described above.
To hand in: List the document IDs of the top 10 pages as sorted by PageRank, together with their PageRank values.
will bring up document WT04-B22-268, which is an article on the Comprehensive Test Ban Treaty.
To hand in: Explain why these documents have high PageRank values, i.e., why is it that these particular pages are linked to by (possibly) many other pages with (possibly) high PageRank values. Are all of these documents ones that users would likely want to see in response to an appropriate query? Which one are and which ones are not? For those that are not "interesting" documents, why do they have high PageRank values? In short, give an analysis of the PageRank results you obtain.