Search (2 results, page 1 of 1)

0.039321437 = product of:
  0.078642875 = sum of:
    0.078642875 = sum of:
      0.04334968 = weight(_text_:web in 2564) [ClassicSimilarity], result of:
        0.04334968 = score(doc=2564,freq=4.0), product of:
          0.17002425 = queryWeight, product of:
            3.2635105 = idf(docFreq=4597, maxDocs=44218)
            0.052098576 = queryNorm
          0.25496176 = fieldWeight in 2564, product of:
            2.0 = tf(freq=4.0), with freq of:
              4.0 = termFreq=4.0
            3.2635105 = idf(docFreq=4597, maxDocs=44218)
            0.0390625 = fieldNorm(doc=2564)
      0.03529319 = weight(_text_:22 in 2564) [ClassicSimilarity], result of:
        0.03529319 = score(doc=2564,freq=2.0), product of:
          0.18244034 = queryWeight, product of:
            3.5018296 = idf(docFreq=3622, maxDocs=44218)
            0.052098576 = queryNorm
          0.19345059 = fieldWeight in 2564, product of:
            1.4142135 = tf(freq=2.0), with freq of:
              2.0 = termFreq=2.0
            3.5018296 = idf(docFreq=3622, maxDocs=44218)
            0.0390625 = fieldNorm(doc=2564)
  0.5 = coord(1/2)

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.

Date

16. 1.2016 10:22:28

Source

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

0.03297302 = product of:
  0.06594604 = sum of:
    0.06594604 = sum of:
      0.030652853 = weight(_text_:web in 2565) [ClassicSimilarity], result of:
        0.030652853 = score(doc=2565,freq=2.0), product of:
          0.17002425 = queryWeight, product of:
            3.2635105 = idf(docFreq=4597, maxDocs=44218)
            0.052098576 = queryNorm
          0.18028519 = fieldWeight in 2565, product of:
            1.4142135 = tf(freq=2.0), with freq of:
              2.0 = termFreq=2.0
            3.2635105 = idf(docFreq=4597, maxDocs=44218)
            0.0390625 = fieldNorm(doc=2565)
      0.03529319 = weight(_text_:22 in 2565) [ClassicSimilarity], result of:
        0.03529319 = score(doc=2565,freq=2.0), product of:
          0.18244034 = queryWeight, product of:
            3.5018296 = idf(docFreq=3622, maxDocs=44218)
            0.052098576 = queryNorm
          0.19345059 = fieldWeight in 2565, product of:
            1.4142135 = tf(freq=2.0), with freq of:
              2.0 = termFreq=2.0
            3.5018296 = idf(docFreq=3622, maxDocs=44218)
            0.0390625 = fieldNorm(doc=2565)
  0.5 = coord(1/2)

Abstract

This paper introduces a family of link-based ranking algorithms that propagate page importance through links. In these algorithms there is a damping function that decreases with distance, so a direct link implies more endorsement than a link through a long path. PageRank is the most widely known ranking function of this family. The main objective of this paper is to determine whether this family of ranking techniques has some interest per se, and how different choices for the damping function impact on rank quality and on convergence speed. Even though our results suggest that PageRank can be approximated with other simpler forms of rankings that may be computed more efficiently, our focus is of more speculative nature, in that it aims at separating the kernel of PageRank, that is, link-based importance propagation, from the way propagation decays over paths. We focus on three damping functions, having linear, exponential, and hyperbolic decay on the lengths of the paths. The exponential decay corresponds to PageRank, and the other functions are new. Our presentation includes algorithms, analysis, comparisons and experiments that study their behavior under different parameters in real Web graph data. Among other results, we show how to calculate a linear approximation that induces a page ordering that is almost identical to PageRank's using a fixed small number of iterations; comparisons were performed using Kendall's tau on large domain datasets.

Date

16. 1.2016 10:22:28