Document (#39564)

Author
Bressan, M.
Peserico, E.
Title
Choose the damping, choose the ranking?
Source
Journal of discrete algorithms. 8(2010) no.2, S.199-213
Year
2010
Abstract
To what extent can changes in PageRank's damping factor affect node ranking? We prove that, at least on some graphs, the top k nodes assume all possible k! orderings as the damping factor varies, even if it varies within an arbitrarily small interval (e.g. [0.84999,0.85001][0.84999,0.85001]). Thus, the rank of a node for a given (finite set of discrete) damping factor(s) provides very little information about the rank of that node as the damping factor varies over a continuous interval. We bypass this problem introducing lineage analysis and proving that there is a simple condition, with a "natural" interpretation independent of PageRank, that allows one to verify "in one shot" if a node outperforms another simultaneously for all damping factors and all damping variables (informally, time variant damping factors). The novel notions of strong rank and weak rank of a node provide a measure of the fuzziness of the rank of that node, of the objective orderability of a graph's nodes, and of the quality of results returned by different ranking algorithms based on the random surfer model. We deploy our analytical tools on a 41M node snapshot of the .it Web domain and on a 0.7M node snapshot of the CiteSeer citation graph. Among other findings, we show that rank is indeed relatively stable in both graphs; that "classic" PageRank (d=0.85) marginally outperforms Weighted In-degree (d->0), mainly due to its ability to ferret out "niche" items; and that, for both the Web and CiteSeer, the ideal damping factor appears to be 0.8-0.9 to obtain those items of high importance to at least one (model of randomly surfing) user, but only 0.5-0.6 to obtain those items important to every (model of randomly surfing) user.
Content
This paper addresses the fundamental question of how the ranking induced by PageRank can be affected by variations of the damping factor. This introduction briefly reviews the PageRank algorithm (Section 1.1) and the crucial difference between score and rank (Section 1.2) before presenting an overview of our results and the organization of the rest of the paper (Section 1.3). Vgl. auch: doi:10.1016/j.jda.2009.11.001. http://www.sciencedirect.com/science/article/pii/S1570866709000926.
Theme
Suchmaschinen
Object
PageRank

Similar documents (content)

  1. Ding, Y.; Yan, E.; Frazho, A.; Caverlee, J.: PageRank for ranking authors in co-citation networks (2009) 0.34 
    0.34058797 = sum of:
  0.34058797 = product of:
    1.2163856 = sum of:
      0.02324023 = weight(abstract_txt:factors in 3161) [ClassicSimilarity], result of:
        0.02324023 = score(doc=3161,freq=3.0), product of:
          0.04327341 = queryWeight, product of:
            1.017561 = boost
            4.9611073 = idf(docFreq=841, maxDocs=44218)
            0.008571998 = queryNorm
          0.5370556 = fieldWeight in 3161, product of:
            1.7320508 = tf(freq=3.0), with freq of:
              3.0 = termFreq=3.0
            4.9611073 = idf(docFreq=841, maxDocs=44218)
            0.0625 = fieldNorm(doc=3161)
      0.14485778 = weight(abstract_txt:pagerank in 3161) [ClassicSimilarity], result of:
        0.14485778 = score(doc=3161,freq=9.0), product of:
          0.10162058 = queryWeight, product of:
            1.5593396 = boost
            7.602543 = idf(docFreq=59, maxDocs=44218)
            0.008571998 = 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.040910814 = weight(abstract_txt:ranking in 3161) [ClassicSimilarity], result of:
        0.040910814 = score(doc=3161,freq=2.0), product of:
          0.08266985 = queryWeight, product of:
            1.7225391 = boost
            5.598813 = idf(docFreq=444, maxDocs=44218)
            0.008571998 = queryNorm
          0.49486983 = fieldWeight in 3161, product of:
            1.4142135 = tf(freq=2.0), with freq of:
              2.0 = termFreq=2.0
            5.598813 = idf(docFreq=444, maxDocs=44218)
            0.0625 = fieldNorm(doc=3161)
      0.008269426 = weight(abstract_txt:that in 3161) [ClassicSimilarity], result of:
        0.008269426 = score(doc=3161,freq=2.0), product of:
          0.039484642 = queryWeight, product of:
            1.9439899 = boost
            2.3694751 = idf(docFreq=11241, maxDocs=44218)
            0.008571998 = 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.053669296 = weight(abstract_txt:factor in 3161) [ClassicSimilarity], result of:
        0.053669296 = score(doc=3161,freq=1.0), product of:
          0.14798984 = queryWeight, product of:
            2.975335 = boost
            5.8024845 = idf(docFreq=362, maxDocs=44218)
            0.008571998 = 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.15136299 = weight(abstract_txt:rank in 3161) [ClassicSimilarity], result of:
        0.15136299 = score(doc=3161,freq=3.0), product of:
          0.21766123 = queryWeight, product of:
            3.9527655 = boost
            6.4238877 = idf(docFreq=194, maxDocs=44218)
            0.008571998 = queryNorm
          0.69540626 = fieldWeight in 3161, product of:
            1.7320508 = tf(freq=3.0), with freq of:
              3.0 = termFreq=3.0
            6.4238877 = idf(docFreq=194, maxDocs=44218)
            0.0625 = fieldNorm(doc=3161)
      0.794075 = weight(abstract_txt:damping in 3161) [ClassicSimilarity], result of:
        0.794075 = score(doc=3161,freq=3.0), product of:
          0.75226825 = queryWeight, product of:
            9.0 = boost
            9.7509775 = idf(docFreq=6, maxDocs=44218)
            0.008571998 = 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.28 = coord(7/25)
  2. Boldi, P.; Santini, M.; Vigna, S.: PageRank as a function of the damping factor (2005) 0.27 
    0.27242857 = sum of:
  0.27242857 = product of:
    0.8513393 = sum of:
      0.05339421 = weight(abstract_txt:0.85 in 2564) [ClassicSimilarity], result of:
        0.05339421 = score(doc=2564,freq=1.0), product of:
          0.086249 = queryWeight, product of:
            1.0158087 = boost
            9.905128 = idf(docFreq=5, maxDocs=44218)
            0.008571998 = queryNorm
          0.6190705 = fieldWeight in 2564, product of:
            1.0 = tf(freq=1.0), with freq of:
              1.0 = termFreq=1.0
            9.905128 = idf(docFreq=5, maxDocs=44218)
            0.0625 = fieldNorm(doc=2564)
      0.03952797 = weight(abstract_txt:graphs in 2564) [ClassicSimilarity], result of:
        0.03952797 = score(doc=2564,freq=1.0), product of:
          0.08892782 = queryWeight, product of:
            1.4587091 = boost
            7.11192 = idf(docFreq=97, maxDocs=44218)
            0.008571998 = queryNorm
          0.444495 = fieldWeight in 2564, product of:
            1.0 = tf(freq=1.0), with freq of:
              1.0 = termFreq=1.0
            7.11192 = idf(docFreq=97, maxDocs=44218)
            0.0625 = fieldNorm(doc=2564)
      0.11827587 = weight(abstract_txt:pagerank in 2564) [ClassicSimilarity], result of:
        0.11827587 = score(doc=2564,freq=6.0), product of:
          0.10162058 = queryWeight, product of:
            1.5593396 = boost
            7.602543 = idf(docFreq=59, maxDocs=44218)
            0.008571998 = queryNorm
          1.1638969 = fieldWeight in 2564, product of:
            2.4494898 = tf(freq=6.0), with freq of:
              6.0 = termFreq=6.0
            7.602543 = idf(docFreq=59, maxDocs=44218)
            0.0625 = fieldNorm(doc=2564)
      0.028928313 = weight(abstract_txt:ranking in 2564) [ClassicSimilarity], result of:
        0.028928313 = score(doc=2564,freq=1.0), product of:
          0.08266985 = queryWeight, product of:
            1.7225391 = boost
            5.598813 = idf(docFreq=444, maxDocs=44218)
            0.008571998 = queryNorm
          0.34992582 = fieldWeight in 2564, product of:
            1.0 = tf(freq=1.0), with freq of:
              1.0 = termFreq=1.0
            5.598813 = idf(docFreq=444, maxDocs=44218)
            0.0625 = fieldNorm(doc=2564)
      0.011694735 = weight(abstract_txt:that in 2564) [ClassicSimilarity], result of:
        0.011694735 = score(doc=2564,freq=4.0), product of:
          0.039484642 = queryWeight, product of:
            1.9439899 = boost
            2.3694751 = idf(docFreq=11241, maxDocs=44218)
            0.008571998 = queryNorm
          0.2961844 = fieldWeight in 2564, product of:
            2.0 = tf(freq=4.0), with freq of:
              4.0 = termFreq=4.0
            2.3694751 = idf(docFreq=11241, maxDocs=44218)
            0.0625 = fieldNorm(doc=2564)
      0.053669296 = weight(abstract_txt:factor in 2564) [ClassicSimilarity], result of:
        0.053669296 = score(doc=2564,freq=1.0), product of:
          0.14798984 = queryWeight, product of:
            2.975335 = boost
            5.8024845 = idf(docFreq=362, maxDocs=44218)
            0.008571998 = queryNorm
          0.36265528 = fieldWeight in 2564, 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=2564)
      0.087389454 = weight(abstract_txt:rank in 2564) [ClassicSimilarity], result of:
        0.087389454 = score(doc=2564,freq=1.0), product of:
          0.21766123 = queryWeight, product of:
            3.9527655 = boost
            6.4238877 = idf(docFreq=194, maxDocs=44218)
            0.008571998 = queryNorm
          0.40149298 = fieldWeight in 2564, product of:
            1.0 = tf(freq=1.0), with freq of:
              1.0 = termFreq=1.0
            6.4238877 = idf(docFreq=194, maxDocs=44218)
            0.0625 = fieldNorm(doc=2564)
      0.45845944 = weight(abstract_txt:damping in 2564) [ClassicSimilarity], result of:
        0.45845944 = score(doc=2564,freq=1.0), product of:
          0.75226825 = queryWeight, product of:
            9.0 = boost
            9.7509775 = idf(docFreq=6, maxDocs=44218)
            0.008571998 = queryNorm
          0.6094361 = fieldWeight in 2564, product of:
            1.0 = tf(freq=1.0), with freq of:
              1.0 = termFreq=1.0
            9.7509775 = idf(docFreq=6, maxDocs=44218)
            0.0625 = fieldNorm(doc=2564)
    0.32 = coord(8/25)
  3. Baeza-Yates, R.; Boldi, P.; Castillo, C.: Generalizing PageRank : damping functions for linkbased ranking algorithms (2006) 0.21 
    0.20913675 = sum of:
  0.20913675 = product of:
    1.0456837 = sum of:
      0.09657185 = weight(abstract_txt:pagerank in 2565) [ClassicSimilarity], result of:
        0.09657185 = score(doc=2565,freq=4.0), product of:
          0.10162058 = queryWeight, product of:
            1.5593396 = boost
            7.602543 = idf(docFreq=59, maxDocs=44218)
            0.008571998 = queryNorm
          0.95031786 = fieldWeight in 2565, product of:
            2.0 = tf(freq=4.0), with freq of:
              4.0 = termFreq=4.0
            7.602543 = idf(docFreq=59, maxDocs=44218)
            0.0625 = fieldNorm(doc=2565)
      0.050105307 = weight(abstract_txt:ranking in 2565) [ClassicSimilarity], result of:
        0.050105307 = score(doc=2565,freq=3.0), product of:
          0.08266985 = queryWeight, product of:
            1.7225391 = boost
            5.598813 = idf(docFreq=444, maxDocs=44218)
            0.008571998 = queryNorm
          0.6060893 = fieldWeight in 2565, product of:
            1.7320508 = tf(freq=3.0), with freq of:
              3.0 = termFreq=3.0
            5.598813 = idf(docFreq=444, maxDocs=44218)
            0.0625 = fieldNorm(doc=2565)
      0.017542101 = weight(abstract_txt:that in 2565) [ClassicSimilarity], result of:
        0.017542101 = score(doc=2565,freq=9.0), product of:
          0.039484642 = queryWeight, product of:
            1.9439899 = boost
            2.3694751 = idf(docFreq=11241, maxDocs=44218)
            0.008571998 = queryNorm
          0.44427657 = fieldWeight in 2565, product of:
            3.0 = tf(freq=9.0), with freq of:
              9.0 = termFreq=9.0
            2.3694751 = idf(docFreq=11241, maxDocs=44218)
            0.0625 = fieldNorm(doc=2565)
      0.087389454 = weight(abstract_txt:rank in 2565) [ClassicSimilarity], result of:
        0.087389454 = score(doc=2565,freq=1.0), product of:
          0.21766123 = queryWeight, product of:
            3.9527655 = boost
            6.4238877 = idf(docFreq=194, maxDocs=44218)
            0.008571998 = queryNorm
          0.40149298 = fieldWeight in 2565, product of:
            1.0 = tf(freq=1.0), with freq of:
              1.0 = termFreq=1.0
            6.4238877 = idf(docFreq=194, maxDocs=44218)
            0.0625 = fieldNorm(doc=2565)
      0.794075 = weight(abstract_txt:damping in 2565) [ClassicSimilarity], result of:
        0.794075 = score(doc=2565,freq=3.0), product of:
          0.75226825 = queryWeight, product of:
            9.0 = boost
            9.7509775 = idf(docFreq=6, maxDocs=44218)
            0.008571998 = queryNorm
          1.0555743 = fieldWeight in 2565, 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=2565)
    0.2 = coord(5/25)
  4. Bauckhage, C.: Marginalizing over the PageRank damping factor (2014) 0.17 
    0.17285499 = sum of:
  0.17285499 = product of:
    1.0803437 = sum of:
      0.0551583 = weight(abstract_txt:obtain in 928) [ClassicSimilarity], result of:
        0.0551583 = score(doc=928,freq=1.0), product of:
          0.0699555 = queryWeight, product of:
            1.2937812 = boost
            6.3078156 = idf(docFreq=218, maxDocs=44218)
            0.008571998 = queryNorm
          0.78847694 = fieldWeight in 928, product of:
            1.0 = tf(freq=1.0), with freq of:
              1.0 = termFreq=1.0
            6.3078156 = idf(docFreq=218, maxDocs=44218)
            0.125 = fieldNorm(doc=928)
      0.09657185 = weight(abstract_txt:pagerank in 928) [ClassicSimilarity], result of:
        0.09657185 = score(doc=928,freq=1.0), product of:
          0.10162058 = queryWeight, product of:
            1.5593396 = boost
            7.602543 = idf(docFreq=59, maxDocs=44218)
            0.008571998 = 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.011694735 = weight(abstract_txt:that in 928) [ClassicSimilarity], result of:
        0.011694735 = score(doc=928,freq=1.0), product of:
          0.039484642 = queryWeight, product of:
            1.9439899 = boost
            2.3694751 = idf(docFreq=11241, maxDocs=44218)
            0.008571998 = 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.9169189 = weight(abstract_txt:damping in 928) [ClassicSimilarity], result of:
        0.9169189 = score(doc=928,freq=1.0), product of:
          0.75226825 = queryWeight, product of:
            9.0 = boost
            9.7509775 = idf(docFreq=6, maxDocs=44218)
            0.008571998 = 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.16 = coord(4/25)
  5. Yan, E.; Ding, Y.: Discovering author impact : a PageRank perspective (2011) 0.14 
    0.13783114 = sum of:
  0.13783114 = product of:
    0.86144465 = sum of:
      0.020126628 = weight(abstract_txt:factors in 2704) [ClassicSimilarity], result of:
        0.020126628 = score(doc=2704,freq=1.0), product of:
          0.04327341 = queryWeight, product of:
            1.017561 = boost
            4.9611073 = idf(docFreq=841, maxDocs=44218)
            0.008571998 = queryNorm
          0.4651038 = fieldWeight in 2704, product of:
            1.0 = tf(freq=1.0), with freq of:
              1.0 = termFreq=1.0
            4.9611073 = idf(docFreq=841, maxDocs=44218)
            0.09375 = fieldNorm(doc=2704)
      0.14485778 = weight(abstract_txt:pagerank in 2704) [ClassicSimilarity], result of:
        0.14485778 = score(doc=2704,freq=4.0), product of:
          0.10162058 = queryWeight, product of:
            1.5593396 = boost
            7.602543 = idf(docFreq=59, maxDocs=44218)
            0.008571998 = 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.008771051 = weight(abstract_txt:that in 2704) [ClassicSimilarity], result of:
        0.008771051 = score(doc=2704,freq=1.0), product of:
          0.039484642 = queryWeight, product of:
            1.9439899 = boost
            2.3694751 = idf(docFreq=11241, maxDocs=44218)
            0.008571998 = 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.6876892 = weight(abstract_txt:damping in 2704) [ClassicSimilarity], result of:
        0.6876892 = score(doc=2704,freq=1.0), product of:
          0.75226825 = queryWeight, product of:
            9.0 = boost
            9.7509775 = idf(docFreq=6, maxDocs=44218)
            0.008571998 = 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.16 = coord(4/25)