Project 6: Google Page Rank
Brendan Gramp
Contents
Background
http://math.gmu.edu/~tsauer/class/447/proj/447proj6.html
Problem: Slimmed down reality check: Two nodes
Problem 1
Find the adjacency matrix A and google matrix G for the following internet graph. Give the page rank vector, and rank all of the pages, from most to least important, according to page rank.
The that is being analyzed is displayed below.
format long;
v = pagerank1()
D =
2 0 0 0 0 0
0 2 0 0 0 0
0 0 3 0 0 0
0 0 0 1 0 0
0 0 0 0 2 0
0 0 0 0 0 1
A =
0 0 1 0 0 0
1 0 0 0 0 0
0 1 0 1 1 0
1 0 1 0 0 1
0 1 0 0 0 0
0 0 1 0 1 0
G =
Columns 1 through 3
0 0 0.333333333333333
0.500000000000000 0 0
0 0.500000000000000 0
0.500000000000000 0 0.333333333333333
0 0.500000000000000 0
0 0 0.333333333333333
Columns 4 through 6
0 0 0
0 0 0
1.000000000000000 0.500000000000000 0
0 0 1.000000000000000
0 0 0
0 0.500000000000000 0
v =
0.117647058823529
0.058823529411765
0.352941176470588
0.308823529411764
0.029411764705882
0.132352941176471
As can be seen from v, the ranks of the vectors are, from highest to lowest: page 3, page 4, page 6, page 1, page 2, and last of all, page 5.
Problem 2
Same as Problem 1, for the following graph:
v = pagerank2()
D =
1 0 0 0 0 0 0
0 1 0 0 0 0 0
0 0 2 0 0 0 0
0 0 0 3 0 0 0
0 0 0 0 2 0 0
0 0 0 0 0 1 0
0 0 0 0 0 0 2
A =
0 0 1 0 0 0 0
1 0 0 0 0 0 0
0 1 0 1 0 0 0
0 0 1 0 0 0 1
0 0 0 1 0 1 0
0 0 0 0 1 0 1
0 0 0 1 1 0 0
G =
Columns 1 through 3
0 0 0.500000000000000
1.000000000000000 0 0
0 1.000000000000000 0
0 0 0.500000000000000
0 0 0
0 0 0
0 0 0
Columns 4 through 6
0 0 0
0 0 0
0.333333333333333 0 0
0 0 0
0.333333333333333 0 1.000000000000000
0 0.500000000000000 0
0.333333333333333 0.500000000000000 0
Column 7
0
0
0
0.500000000000000
0
0.500000000000000
0
v =
0.045454545454545
0.045454545454545
0.090909090909091
0.136363636363636
0.272727272727273
0.227272727272727
0.181818181818182
As can be seen from v, the ranks of the vectors are, from highest to lowest: page 5, page 6, page 7, page 4, page 3, and last of all, pages 1 and 2 are tied in terms of page rank.
Problem 3
Make your own graph and find page ranks
v = pagerank3()
D =
2 0 0 0 0 0 0 0 0 0
0 2 0 0 0 0 0 0 0 0
0 0 2 0 0 0 0 0 0 0
0 0 0 3 0 0 0 0 0 0
0 0 0 0 2 0 0 0 0 0
0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 4 0 0
0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 0 4
A =
0 0 1 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 1 0 0
0 1 0 0 1 0 0 1 0 1
0 0 0 1 0 0 0 0 0 1
0 1 0 0 0 0 0 0 0 0
0 0 0 0 1 1 0 0 0 1
0 0 1 1 0 0 0 0 0 0
0 0 0 0 0 0 0 1 0 1
0 0 0 1 0 0 1 1 1 0
G =
Columns 1 through 3
0 0 0.500000000000000
0.500000000000000 0 0
0.500000000000000 0 0
0 0.500000000000000 0
0 0 0
0 0.500000000000000 0
0 0 0
0 0 0.500000000000000
0 0 0
0 0 0
Columns 4 through 6
0 0 0
0 0 0
0 0 0
0 0.500000000000000 0
0.333333333333333 0 0
0 0 0
0 0.500000000000000 1.000000000000000
0.333333333333333 0 0
0 0 0
0.333333333333333 0 0
Columns 7 through 9
0 0 0
0 0 0
0 0.250000000000000 0
0 0.250000000000000 0
0 0 0
0 0 0
0 0 0
0 0 0
0 0.250000000000000 0
1.000000000000000 0.250000000000000 1.000000000000000
Column 10
0
0
0
0.250000000000000
0.250000000000000
0
0.250000000000000
0
0.250000000000000
0
v =
0.011396011396012
0.005698005698006
0.022792022792023
0.170940170940171
0.138651471984805
0.002849002849003
0.153846153846154
0.068376068376068
0.098765432098765
0.326685660018993
As can be seen from v, the ranks of the vectors are, from highest to lowest: page 10, page 4, page 7, page 5, page 9, page 8, page 3, page 1, page 2, and last of all, page 6.