CMPT 456 Assignment 5
Question 1 (15 points)
1. (10 points) Can a web page without any in-links can be reached in random walks?
2. (5 points) In commercial search engines, aggregate ranking scores are used to rank web
pages. Let Dsim(d, q) be the cosine similarity between a page d and a query q, and PR(d)
be the PageRank of d. Consider two smoothed measures:
𝑆𝑆!(𝑑𝑑, 𝑞𝑞) = 𝜆𝜆𝜆𝜆𝜆𝜆𝜆𝜆𝜆𝜆(𝑑𝑑, 𝑞𝑞) + 𝑃𝑃𝑃𝑃(𝑑𝑑)
𝑆𝑆”(𝑑𝑑, 𝑞𝑞) = 𝑙𝑙𝑙𝑙𝑙𝑙(𝜆𝜆 𝐷𝐷𝐷𝐷𝐷𝐷𝐷𝐷(𝑑𝑑, 𝑞𝑞)) + 𝑙𝑙𝑙𝑙𝑙𝑙 𝑃𝑃𝑃𝑃(𝑑𝑑).
Which one is better in ranking Web pages? Why?
Question 2 (25 points)
Consider the transition probability matrix as follows.
0 1 0
0.5 0 0.5
0.5 0.5 0
1. (10 points) Is the matrix stochastic?
2. (15 points) Assuming a = 0, what is the PageRank of the node of the least out-links?
Question 3 (25 points)
A user of a browser can, in addition to clicking a hyperlink on the page x she/he is currently
browsing, use the back button to go back to the page from which she/he arrived at x. Can such a
user of back buttons be modeled as a Markov chain? How would we model repeated invocations
of the back button?
Question 4 (35 points)
Consider the following graph.
1. (10 points) If all the hub and authority scores are initialized to 1, what is the hub/authority
score of a node after one iteration?
2. (15 points) Compute the PageRank, hub score and authority score of the nodes in the
following graph. Please set the teleport probability to 0.15.
3. (10 points) Using this example to discuss the differences between PageRank and
本网站支持淘宝 支付宝 微信支付 paypal等等交易。如果不放心可以用淘宝交易！
E-mail: [email protected] 微信:itcsdx