CS594/494 Lecture Notes Supplement


	Example of PageRank from Cho, Garcia-Molina and Page article.

	Suppose you are to compute the IR(P) ranking for a webpage P  
        and the pages T_1, T_2, T_3 that point to it.  Consider the
        following stats defining the linkage patterns:


   			i	c_i
			-       ---
			1	 2
			2	 4
			3	 2


     
        Suppose the graph of links has the following form:

                                      

                       -----------> T_3
                      | 
                      |              |              ^
                      |              |              |
                      |              |              |
                      |              V              |
                      V
                     T_1 <-------->  P  <--------> T_2  ---->
                       
                      ^              |              |
                      |              |              |
                      |              |              |
                      |              V              |
                      |                             |
                      ------------------------------- 

      
          Hence, n=3 and assume the damping factor d=0.80.  The following
          linear system of 4 equations in the 4 unknowns {IR(T_1), IR(T_2),
          IR(T_3), IR(P)} can be defined:

          IR(P)   = 0.20 + 0.80 [ IR(T_1)/2 + IR(T_2)/4 + IR(T_3)/2           ]
          IR(T_1) = 0.20 + 0.80 [             IR(T_2)/4 + IR(T_3)/2 + IR(P)/3 ]
          IR(T_2) = 0.20 + 0.80 [                                     IR(P)/3 ]
          IR(T_3) = 0.20 + 0.80 [ IR(T_1)/2                                   ]


          We can then define the iteration 

                x_old = x_new   (initialized to all 1's)
                x_new = A * x_old + (1-d), where


               [  0     0.20  0.40  0.26 ]
               [  0     0     0     0.26 ]
           A = [  0.40  0     0     0    ]
               [  0.40  0.20  0.40  0    ],

                   T_1   T_2   T_3  P


           x   = [IR(T_1), IR(T_2), IR(T_3), IR(P) ]^T, and  

           d   = [0.80, 0.80, 0.80, 0.80 ]^T.

           Assume the starting vector x_0 = [ 1, 1, 1, 1]^T  and
           running the iteration for 20 steps producing the following:

               x_20 = [ 0.6487, 0.3874, 0.4595, 0.7208 ]^T 

           So, we would have the following rankings for the IR( )
           measure:

                      0.7208 IR(P)
                      0.6487 IR(T_1)
                      0.4595 IR(T_3)
                      0.3874 IR(T_2)

           The rankings reflect the number of inlinks to reach page.

           Results of experiments with different damping factors (d);
           using 20 iterations...

          d:  0.65 |  0.70 |  0.75 |  0.80 |  0.85 |  0.90

         T1:  0.83 |  0.78 |  0.72 |  0.65 |  0.55 |  0.42
         T2:  0.54 |  0.50 |  0.45 |  0.39 |  0.32 |  0.24
         T3:  0.62 |  0.57 |  0.52 |  0.46 |  0.38 |  0.29
          P:  0.91 |  0.86 |  0.80 |  0.72 |  0.62 |  0.48