Document (#39565)

Author

Boldi, P.
Santini, M.
Vigna, S.

Title

PageRank as a function of the damping factor

Source

http://vigna.di.unimi.it/ftp/papers/PageRankAsFunction.pdf [Proceedings of the ACM World Wide Web Conference (WWW), 2005]

Year

2005

Abstract

PageRank is defined as the stationary state of a Markov chain. The chain is obtained by perturbing the transition matrix induced by a web graph with a damping factor alpha that spreads uniformly part of the rank. The choice of alpha is eminently empirical, and in most cases the original suggestion alpha=0.85 by Brin and Page is still used. Recently, however, the behaviour of PageRank with respect to changes in alpha was discovered to be useful in link-spam detection. Moreover, an analytical justification of the value chosen for alpha is still missing. In this paper, we give the first mathematical analysis of PageRank when alpha changes. In particular, we show that, contrarily to popular belief, for real-world graphs values of alpha close to 1 do not give a more meaningful ranking. Then, we give closed-form formulae for PageRank derivatives of any order, and an extension of the Power Method that approximates them with convergence O(t**k*alpha**t) for the k-th derivative. Finally, we show a tight connection between iterated computation and analytical behaviour by proving that the k-th iteration of the Power Method gives exactly the PageRank value obtained using a Maclaurin polynomial of degree k. The latter result paves the way towards the application of analytical methods to the study of PageRank.

Theme

Suchmaschinen

Object

PageRank

Similar documents (content)

1. Bressan, M.; Peserico, E.: Choose the damping, choose the ranking? (2010) 0.27

   0.274372 = sum of:
     0.274372 = product of:
       0.8574125 = sum of:
         0.011415816 = weight(abstract_txt:show in 2563) [ClassicSimilarity], result of:
           0.011415816 = score(doc=2563,freq=1.0), product of:
             0.04737869 = queryWeight, product of:
               4.4059124 = idf(docFreq=1466, maxDocs=44218)
               0.010753434 = queryNorm
             0.24094833 = fieldWeight in 2563, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               4.4059124 = idf(docFreq=1466, maxDocs=44218)
               0.0546875 = fieldNorm(doc=2563)
         0.010044557 = weight(abstract_txt:that in 2563) [ClassicSimilarity], result of:
           0.010044557 = score(doc=2563,freq=8.0), product of:
             0.027405996 = queryWeight, product of:
               1.0755888 = boost
               2.3694751 = idf(docFreq=11241, maxDocs=44218)
               0.010753434 = queryNorm
             0.36650947 = fieldWeight in 2563, product of:
               2.828427 = tf(freq=8.0), with freq of:
                 8.0 = termFreq=8.0
               2.3694751 = idf(docFreq=11241, maxDocs=44218)
               0.0546875 = fieldNorm(doc=2563)
         0.06485592 = weight(abstract_txt:0.85 in 2563) [ClassicSimilarity], result of:
           0.06485592 = score(doc=2563,freq=1.0), product of:
             0.11972958 = queryWeight, product of:
               1.1240722 = boost
               9.905128 = idf(docFreq=5, maxDocs=44218)
               0.010753434 = queryNorm
             0.54168665 = fieldWeight in 2563, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               9.905128 = idf(docFreq=5, maxDocs=44218)
               0.0546875 = fieldNorm(doc=2563)
         0.016807543 = weight(abstract_txt:changes in 2563) [ClassicSimilarity], result of:
           0.016807543 = score(doc=2563,freq=1.0), product of:
             0.06131704 = queryWeight, product of:
               1.1376249 = boost
               5.0122757 = idf(docFreq=799, maxDocs=44218)
               0.010753434 = queryNorm
             0.27410883 = fieldWeight in 2563, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               5.0122757 = idf(docFreq=799, maxDocs=44218)
               0.0546875 = fieldNorm(doc=2563)
         0.05830776 = weight(abstract_txt:factor in 2563) [ClassicSimilarity], result of:
           0.05830776 = score(doc=2563,freq=5.0), product of:
             0.08217492 = queryWeight, product of:
               1.3169768 = boost
               5.8024845 = idf(docFreq=362, maxDocs=44218)
               0.010753434 = queryNorm
             0.70955664 = fieldWeight in 2563, product of:
               2.236068 = tf(freq=5.0), with freq of:
                 5.0 = termFreq=5.0
               5.8024845 = idf(docFreq=362, maxDocs=44218)
               0.0546875 = fieldNorm(doc=2563)
         0.3500168 = weight(abstract_txt:damping in 2563) [ClassicSimilarity], result of:
           0.3500168 = score(doc=2563,freq=8.0), product of:
             0.23206393 = queryWeight, product of:
               2.2131574 = boost
               9.7509775 = idf(docFreq=6, maxDocs=44218)
               0.010753434 = queryNorm
             1.5082774 = fieldWeight in 2563, product of:
               2.828427 = tf(freq=8.0), with freq of:
                 8.0 = termFreq=8.0
               9.7509775 = idf(docFreq=6, maxDocs=44218)
               0.0546875 = fieldNorm(doc=2563)
         0.055656046 = weight(abstract_txt:analytical in 2563) [ClassicSimilarity], result of:
           0.055656046 = score(doc=2563,freq=1.0), product of:
             0.15593743 = queryWeight, product of:
               2.2219245 = boost
               6.5264034 = idf(docFreq=175, maxDocs=44218)
               0.010753434 = queryNorm
             0.35691267 = fieldWeight in 2563, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               6.5264034 = idf(docFreq=175, maxDocs=44218)
               0.0546875 = fieldNorm(doc=2563)
         0.29030806 = weight(abstract_txt:pagerank in 2563) [ClassicSimilarity], result of:
           0.29030806 = score(doc=2563,freq=2.0), product of:
             0.49373865 = queryWeight, product of:
               6.039362 = boost
               7.602543 = idf(docFreq=59, maxDocs=44218)
               0.010753434 = queryNorm
             0.5879792 = fieldWeight in 2563, product of:
               1.4142135 = tf(freq=2.0), with freq of:
                 2.0 = termFreq=2.0
               7.602543 = idf(docFreq=59, maxDocs=44218)
               0.0546875 = fieldNorm(doc=2563)
       0.32 = coord(8/25)
   

2. Ding, Y.; Yan, E.; Frazho, A.; Caverlee, J.: PageRank for ranking authors in co-citation networks (2009) 0.16

   0.15749034 = sum of:
     0.15749034 = product of:
       0.9843147 = sum of:
         0.005739747 = weight(abstract_txt:that in 3161) [ClassicSimilarity], result of:
           0.005739747 = score(doc=3161,freq=2.0), product of:
             0.027405996 = queryWeight, product of:
               1.0755888 = boost
               2.3694751 = idf(docFreq=11241, maxDocs=44218)
               0.010753434 = queryNorm
             0.20943399 = fieldWeight in 3161, product of:
               1.4142135 = tf(freq=2.0), with freq of:
                 2.0 = termFreq=2.0
               2.3694751 = idf(docFreq=11241, maxDocs=44218)
               0.0625 = fieldNorm(doc=3161)
         0.02980117 = weight(abstract_txt:factor in 3161) [ClassicSimilarity], result of:
           0.02980117 = score(doc=3161,freq=1.0), product of:
             0.08217492 = queryWeight, product of:
               1.3169768 = boost
               5.8024845 = idf(docFreq=362, maxDocs=44218)
               0.010753434 = queryNorm
             0.36265528 = fieldWeight in 3161, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               5.8024845 = idf(docFreq=362, maxDocs=44218)
               0.0625 = fieldNorm(doc=3161)
         0.24496073 = weight(abstract_txt:damping in 3161) [ClassicSimilarity], result of:
           0.24496073 = score(doc=3161,freq=3.0), product of:
             0.23206393 = queryWeight, product of:
               2.2131574 = boost
               9.7509775 = idf(docFreq=6, maxDocs=44218)
               0.010753434 = queryNorm
             1.0555743 = fieldWeight in 3161, product of:
               1.7320508 = tf(freq=3.0), with freq of:
                 3.0 = termFreq=3.0
               9.7509775 = idf(docFreq=6, maxDocs=44218)
               0.0625 = fieldNorm(doc=3161)
         0.703813 = weight(abstract_txt:pagerank in 3161) [ClassicSimilarity], result of:
           0.703813 = score(doc=3161,freq=9.0), product of:
             0.49373865 = queryWeight, product of:
               6.039362 = boost
               7.602543 = idf(docFreq=59, maxDocs=44218)
               0.010753434 = queryNorm
             1.4254768 = fieldWeight in 3161, product of:
               3.0 = tf(freq=9.0), with freq of:
                 9.0 = termFreq=9.0
               7.602543 = idf(docFreq=59, maxDocs=44218)
               0.0625 = fieldNorm(doc=3161)
       0.16 = coord(4/25)
   

3. Yan, E.; Ding, Y.: Discovering author impact : a PageRank perspective (2011) 0.15

   0.1506581 = sum of:
     0.1506581 = product of:
       0.94161314 = sum of:
         0.01956997 = weight(abstract_txt:show in 2704) [ClassicSimilarity], result of:
           0.01956997 = score(doc=2704,freq=1.0), product of:
             0.04737869 = queryWeight, product of:
               4.4059124 = idf(docFreq=1466, maxDocs=44218)
               0.010753434 = queryNorm
             0.4130543 = fieldWeight in 2704, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               4.4059124 = idf(docFreq=1466, maxDocs=44218)
               0.09375 = fieldNorm(doc=2704)
         0.006087921 = weight(abstract_txt:that in 2704) [ClassicSimilarity], result of:
           0.006087921 = score(doc=2704,freq=1.0), product of:
             0.027405996 = queryWeight, product of:
               1.0755888 = boost
               2.3694751 = idf(docFreq=11241, maxDocs=44218)
               0.010753434 = queryNorm
             0.22213829 = fieldWeight in 2704, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               2.3694751 = idf(docFreq=11241, maxDocs=44218)
               0.09375 = fieldNorm(doc=2704)
         0.21214221 = weight(abstract_txt:damping in 2704) [ClassicSimilarity], result of:
           0.21214221 = score(doc=2704,freq=1.0), product of:
             0.23206393 = queryWeight, product of:
               2.2131574 = boost
               9.7509775 = idf(docFreq=6, maxDocs=44218)
               0.010753434 = queryNorm
             0.9141542 = fieldWeight in 2704, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               9.7509775 = idf(docFreq=6, maxDocs=44218)
               0.09375 = fieldNorm(doc=2704)
         0.703813 = weight(abstract_txt:pagerank in 2704) [ClassicSimilarity], result of:
           0.703813 = score(doc=2704,freq=4.0), product of:
             0.49373865 = queryWeight, product of:
               6.039362 = boost
               7.602543 = idf(docFreq=59, maxDocs=44218)
               0.010753434 = queryNorm
             1.4254768 = fieldWeight in 2704, product of:
               2.0 = tf(freq=4.0), with freq of:
                 4.0 = termFreq=4.0
               7.602543 = idf(docFreq=59, maxDocs=44218)
               0.09375 = fieldNorm(doc=2704)
       0.16 = coord(4/25)
   

4. Dominich, S.; Skrop, A.: PageRank and interaction information retrieval (2005) 0.14

   0.14276335 = sum of:
     0.14276335 = product of:
       0.8922709 = sum of:
         0.03887755 = weight(abstract_txt:method in 3268) [ClassicSimilarity], result of:
           0.03887755 = score(doc=3268,freq=5.0), product of:
             0.04944469 = queryWeight, product of:
               1.0215704 = boost
               4.50095 = idf(docFreq=1333, maxDocs=44218)
               0.010753434 = queryNorm
             0.7862836 = fieldWeight in 3268, product of:
               2.236068 = tf(freq=5.0), with freq of:
                 5.0 = termFreq=5.0
               4.50095 = idf(docFreq=1333, maxDocs=44218)
               0.078125 = fieldNorm(doc=3268)
         0.0050732675 = weight(abstract_txt:that in 3268) [ClassicSimilarity], result of:
           0.0050732675 = score(doc=3268,freq=1.0), product of:
             0.027405996 = queryWeight, product of:
               1.0755888 = boost
               2.3694751 = idf(docFreq=11241, maxDocs=44218)
               0.010753434 = queryNorm
             0.18511525 = fieldWeight in 3268, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               2.3694751 = idf(docFreq=11241, maxDocs=44218)
               0.078125 = fieldNorm(doc=3268)
         0.07243926 = weight(abstract_txt:chain in 3268) [ClassicSimilarity], result of:
           0.07243926 = score(doc=3268,freq=1.0), product of:
             0.1280245 = queryWeight, product of:
               1.6438229 = boost
               7.24254 = idf(docFreq=85, maxDocs=44218)
               0.010753434 = queryNorm
             0.56582344 = fieldWeight in 3268, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               7.24254 = idf(docFreq=85, maxDocs=44218)
               0.078125 = fieldNorm(doc=3268)
         0.7758809 = weight(abstract_txt:pagerank in 3268) [ClassicSimilarity], result of:
           0.7758809 = score(doc=3268,freq=7.0), product of:
             0.49373865 = queryWeight, product of:
               6.039362 = boost
               7.602543 = idf(docFreq=59, maxDocs=44218)
               0.010753434 = queryNorm
             1.5714405 = fieldWeight in 3268, product of:
               2.6457512 = tf(freq=7.0), with freq of:
                 7.0 = termFreq=7.0
               7.602543 = idf(docFreq=59, maxDocs=44218)
               0.078125 = fieldNorm(doc=3268)
       0.16 = coord(4/25)
   

5. Bauckhage, C.: Marginalizing over the PageRank damping factor (2014) 0.13

   0.12580408 = sum of:
     0.12580408 = product of:
       0.7862755 = sum of:
         0.026093295 = weight(abstract_txt:show in 928) [ClassicSimilarity], result of:
           0.026093295 = score(doc=928,freq=1.0), product of:
             0.04737869 = queryWeight, product of:
               4.4059124 = idf(docFreq=1466, maxDocs=44218)
               0.010753434 = queryNorm
             0.55073905 = fieldWeight in 928, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               4.4059124 = idf(docFreq=1466, maxDocs=44218)
               0.125 = fieldNorm(doc=928)
         0.008117228 = weight(abstract_txt:that in 928) [ClassicSimilarity], result of:
           0.008117228 = score(doc=928,freq=1.0), product of:
             0.027405996 = queryWeight, product of:
               1.0755888 = boost
               2.3694751 = idf(docFreq=11241, maxDocs=44218)
               0.010753434 = queryNorm
             0.2961844 = fieldWeight in 928, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               2.3694751 = idf(docFreq=11241, maxDocs=44218)
               0.125 = fieldNorm(doc=928)
         0.2828563 = weight(abstract_txt:damping in 928) [ClassicSimilarity], result of:
           0.2828563 = score(doc=928,freq=1.0), product of:
             0.23206393 = queryWeight, product of:
               2.2131574 = boost
               9.7509775 = idf(docFreq=6, maxDocs=44218)
               0.010753434 = queryNorm
             1.2188722 = fieldWeight in 928, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               9.7509775 = idf(docFreq=6, maxDocs=44218)
               0.125 = fieldNorm(doc=928)
         0.46920866 = weight(abstract_txt:pagerank in 928) [ClassicSimilarity], result of:
           0.46920866 = score(doc=928,freq=1.0), product of:
             0.49373865 = queryWeight, product of:
               6.039362 = boost
               7.602543 = idf(docFreq=59, maxDocs=44218)
               0.010753434 = queryNorm
             0.95031786 = fieldWeight in 928, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               7.602543 = idf(docFreq=59, maxDocs=44218)
               0.125 = fieldNorm(doc=928)
       0.16 = coord(4/25)