Comprehensive Test
Due to the nature of some answers, they cannot be processed on the internet. Please write your answers and mail them to CRL, Inc. or give it to your lab supervisor.1. Draw a 10-node directed graph that has at least two dangling nodes and at least one cycle.
2. Convert your graph into a 10x10 binary matrix A.
3. Convert A to the substochastic matrix H.
4. Find the dangling node vector a.
5. Using H and a, find the matrix S.
6. Using G = (S + (1-α)(1/n)E, write the Google matrix (using α=0.85 and rounding to the nearest thousandth).
7. Find the first two iterations of π(k)T by hand.
8. What do the directed lines in your graph represent for the web?
9. What is the problem in finding the PageRank for your original matrix A? How were these problems fixed?
10. What is the justification used in creating the matrices H and S?
11. What special type of matrix is G and what major property does this special matrix utilize in finding the PageRank?
12. What role does α play in the Google matrix?
13. Where can the personalization vector be substituted in the formula for the Google matrix? What does this do for the PageRanks? What are some pros and cons for using a personalization vector?
14. What method is used to compute the PageRank? What were some justifications for using this method?
15. In your own words, give a summary of how Google ranks the pages it returns. Pictures may be helpful.