Back to Problem Solutions forum
Hi! I have a general question about this problem which is still is very unclear to me. So, we have some nodes(web-pages) and we need to find out the page's rank for every node(web-pages). Thus the page rank is number (in percentages) and if summ all the ranks of all nodes(web-pages) we should get 100 %. Till now this obvious fact is completely clear to me.And now the question: We have a vector r which initially takes the same values for every element r = [0.2, 0.2, 0.2, 0.2, 0.2], suppose we have 5 nodes thus we have 1/5=0.2. Then after multiple steps we take the same vector for every node(web-pages)but with different values and it just normal :). So i have 5 nodes(web-pages) with its let's say final vector (after multiple steps of multiplication with Matrix MZ) and what i need as result is a sequence of values like for example (23% 34% 11% 2% 20%)= 100% but i have still this final vector for every node. So, how can i get this 23% for example for first node when my Java code ends up with this final vector for every node. What is link between a vector and this 23 % or 34 % and so on.Hopefully i was explecitly enough to describe my question.
And the second questions: for every node we create a vector r = [0.2, 0.2, 0.2, 0.2, 0.2], let's say we have 5 of them. And for every node we do this multiplications of r=MZr; But should be the same result, because we do 5 times the same opearation( multiple steps of r=MZr, having r=[0.2, 0.2, 0.2, 0.2, 0.2], and MZ which is same for all nodes) Please hepl me to understands all this math.
And the second questions: for every node we create a vector r = [0.2, 0.2, 0.2, 0.2, 0.2], let's say we have 5 of them. And for every node we do this multiplications of r=MZr; But should be the same result, because we do 5 times the same opearation( multiple steps of r=MZr, having r=[0.2, 0.2, 0.2, 0.2, 0.2], and MZ which is same for all nodes) Please hepl me to understands all this math.
I am not sure your question but I think what you are driving at is what is known as a Markov Chain. As far as I can tell the data sets given for this problem meet the requirement of a regular Markov Chain.
1) Every Node can get to every node (this means its ergodic) 2) Some Power of the transition matrix has all positive (>=0) values.
If you set up the transition matrix W. You can solve this problem by finding the limit as n->inf of W^n. (then just multiply the percentages you get by some arbitary number.. the example used 300 walkers).
You can google Markov chain to get the wikipedia entry as well as a lot of other materials on them. This link here: http://www.math.wisc.edu/~valko/courses/331/MC2.pdf specifically talks about how to solve for the limit of such a matrix.
One interesting thing about the solution is for an NxN matrix every row will be exactly the same. Lets call this row R. If you then multiply RxW = W.