Document (#39567)

Author
Haveliwala, T.
Kamvar, S.
Title
¬The second eigenvalue of the Google matrix
Imprint
Stanford : Stanford University
Year
2003
Pages
8 S
Series
Stanford University Technical Report; March 2003
Abstract
We determine analytically the modulus of the second eigenvalue for the web hyperlink matrix used by Google for computing PageRank. Specifically, we prove the following statement: "For any matrix A=(cP + (1-c)E)**T, where P is an nxn row-stochasticmatrix, E is a nonnegative nxn rank-one row-stochastic matrix, and 0<=c<=1, the second eigenvalue of A has modulus Betrag (Lambda_sub2)<=c. Furthermore, if P has at least two irreducible closed subsets, the second eigenvalue Lambda_sub2 = c." This statement has implications for the convergence rate of the standard PageRank algorithm as the web scales, for the stability of PageRank to perturbations to the link structure of the web, for the detection of Google spammers, and for the design of algorithms to speed up PageRank.
Content
Vgl. auch: http://infolab.stanford.edu/~taherh/papers/secondeigenvalue.pdf.
Theme
Suchmaschinen
Object
PageRank

Similar documents (content)

  1. Boldi, P.; Santini, M.; Vigna, S.: PageRank as a function of the damping factor (2005) 0.30 
    0.30045772 = sum of:
  0.30045772 = product of:
    1.0730633 = sum of:
      0.027712349 = weight(abstract_txt:link in 2564) [ClassicSimilarity], result of:
        0.027712349 = score(doc=2564,freq=1.0), product of:
          0.077681035 = queryWeight, product of:
            1.0004387 = boost
            5.707926 = idf(docFreq=398, maxDocs=44218)
            0.013603361 = queryNorm
          0.35674536 = fieldWeight in 2564, product of:
            1.0 = tf(freq=1.0), with freq of:
              1.0 = termFreq=1.0
            5.707926 = idf(docFreq=398, maxDocs=44218)
            0.0625 = fieldNorm(doc=2564)
      0.039503194 = weight(abstract_txt:rank in 2564) [ClassicSimilarity], result of:
        0.039503194 = score(doc=2564,freq=1.0), product of:
          0.09839075 = queryWeight, product of:
            1.1259266 = boost
            6.4238877 = idf(docFreq=194, maxDocs=44218)
            0.013603361 = 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.0465308 = weight(abstract_txt:detection in 2564) [ClassicSimilarity], result of:
        0.0465308 = score(doc=2564,freq=1.0), product of:
          0.1097387 = queryWeight, product of:
            1.1890849 = boost
            6.784232 = idf(docFreq=135, maxDocs=44218)
            0.013603361 = queryNorm
          0.4240145 = fieldWeight in 2564, product of:
            1.0 = tf(freq=1.0), with freq of:
              1.0 = termFreq=1.0
            6.784232 = idf(docFreq=135, maxDocs=44218)
            0.0625 = fieldNorm(doc=2564)
      0.059560828 = weight(abstract_txt:convergence in 2564) [ClassicSimilarity], result of:
        0.059560828 = score(doc=2564,freq=1.0), product of:
          0.1293719 = queryWeight, product of:
            1.2910794 = boost
            7.3661537 = idf(docFreq=75, maxDocs=44218)
            0.013603361 = queryNorm
          0.4603846 = fieldWeight in 2564, product of:
            1.0 = tf(freq=1.0), with freq of:
              1.0 = termFreq=1.0
            7.3661537 = idf(docFreq=75, maxDocs=44218)
            0.0625 = fieldNorm(doc=2564)
      0.06636085 = weight(abstract_txt:closed in 2564) [ClassicSimilarity], result of:
        0.06636085 = score(doc=2564,freq=1.0), product of:
          0.13904032 = queryWeight, product of:
            1.3384537 = boost
            7.636444 = idf(docFreq=57, maxDocs=44218)
            0.013603361 = queryNorm
          0.47727776 = fieldWeight in 2564, product of:
            1.0 = tf(freq=1.0), with freq of:
              1.0 = termFreq=1.0
            7.636444 = idf(docFreq=57, maxDocs=44218)
            0.0625 = fieldNorm(doc=2564)
      0.19181547 = weight(abstract_txt:matrix in 2564) [ClassicSimilarity], result of:
        0.19181547 = score(doc=2564,freq=1.0), product of:
          0.4478596 = queryWeight, product of:
            4.804342 = boost
            6.8527 = idf(docFreq=126, maxDocs=44218)
            0.013603361 = queryNorm
          0.42829376 = fieldWeight in 2564, product of:
            1.0 = tf(freq=1.0), with freq of:
              1.0 = termFreq=1.0
            6.8527 = idf(docFreq=126, maxDocs=44218)
            0.0625 = fieldNorm(doc=2564)
      0.64157975 = weight(abstract_txt:pagerank in 2564) [ClassicSimilarity], result of:
        0.64157975 = score(doc=2564,freq=6.0), product of:
          0.5512342 = queryWeight, product of:
            5.330047 = boost
            7.602543 = idf(docFreq=59, maxDocs=44218)
            0.013603361 = 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.28 = coord(7/25)
  2. Dominich, S.; Skrop, A.: PageRank and interaction information retrieval (2005) 0.27 
    0.26812696 = sum of:
  0.26812696 = product of:
    1.3406348 = sum of:
      0.034640435 = weight(abstract_txt:link in 3268) [ClassicSimilarity], result of:
        0.034640435 = score(doc=3268,freq=1.0), product of:
          0.077681035 = queryWeight, product of:
            1.0004387 = boost
            5.707926 = idf(docFreq=398, maxDocs=44218)
            0.013603361 = queryNorm
          0.4459317 = fieldWeight in 3268, product of:
            1.0 = tf(freq=1.0), with freq of:
              1.0 = termFreq=1.0
            5.707926 = idf(docFreq=398, maxDocs=44218)
            0.078125 = fieldNorm(doc=3268)
      0.11350903 = weight(abstract_txt:stochastic in 3268) [ClassicSimilarity], result of:
        0.11350903 = score(doc=3268,freq=1.0), product of:
          0.17137457 = queryWeight, product of:
            1.4859567 = boost
            8.478011 = idf(docFreq=24, maxDocs=44218)
            0.013603361 = queryNorm
          0.66234463 = fieldWeight in 3268, product of:
            1.0 = tf(freq=1.0), with freq of:
              1.0 = termFreq=1.0
            8.478011 = idf(docFreq=24, maxDocs=44218)
            0.078125 = fieldNorm(doc=3268)
      0.086484425 = weight(abstract_txt:google in 3268) [ClassicSimilarity], result of:
        0.086484425 = score(doc=3268,freq=1.0), product of:
          0.20618567 = queryWeight, product of:
            2.8230777 = boost
            5.3689504 = idf(docFreq=559, maxDocs=44218)
            0.013603361 = queryNorm
          0.41944924 = fieldWeight in 3268, product of:
            1.0 = tf(freq=1.0), with freq of:
              1.0 = termFreq=1.0
            5.3689504 = idf(docFreq=559, maxDocs=44218)
            0.078125 = fieldNorm(doc=3268)
      0.23976932 = weight(abstract_txt:matrix in 3268) [ClassicSimilarity], result of:
        0.23976932 = score(doc=3268,freq=1.0), product of:
          0.4478596 = queryWeight, product of:
            4.804342 = boost
            6.8527 = idf(docFreq=126, maxDocs=44218)
            0.013603361 = queryNorm
          0.5353672 = fieldWeight in 3268, product of:
            1.0 = tf(freq=1.0), with freq of:
              1.0 = termFreq=1.0
            6.8527 = idf(docFreq=126, maxDocs=44218)
            0.078125 = fieldNorm(doc=3268)
      0.8662317 = weight(abstract_txt:pagerank in 3268) [ClassicSimilarity], result of:
        0.8662317 = score(doc=3268,freq=7.0), product of:
          0.5512342 = queryWeight, product of:
            5.330047 = boost
            7.602543 = idf(docFreq=59, maxDocs=44218)
            0.013603361 = 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.2 = coord(5/25)
  3. Kamvar, S.; Haveliwala, T.; Golub, G.: Adaptive methods for the computation of PageRank (2003) 0.26 
    0.25504524 = sum of:
  0.25504524 = product of:
    1.2752261 = sum of:
      0.07190412 = weight(abstract_txt:algorithm in 2560) [ClassicSimilarity], result of:
        0.07190412 = score(doc=2560,freq=3.0), product of:
          0.07761293 = queryWeight, product of:
            5.705423 = idf(docFreq=399, maxDocs=44218)
            0.013603361 = queryNorm
          0.9264452 = fieldWeight in 2560, product of:
            1.7320508 = tf(freq=3.0), with freq of:
              3.0 = termFreq=3.0
            5.705423 = idf(docFreq=399, maxDocs=44218)
            0.09375 = fieldNorm(doc=2560)
      0.050605923 = weight(abstract_txt:furthermore in 2560) [ClassicSimilarity], result of:
        0.050605923 = score(doc=2560,freq=1.0), product of:
          0.08856719 = queryWeight, product of:
            1.0682414 = boost
            6.0947685 = idf(docFreq=270, maxDocs=44218)
            0.013603361 = queryNorm
          0.57138455 = fieldWeight in 2560, product of:
            1.0 = tf(freq=1.0), with freq of:
              1.0 = termFreq=1.0
            6.0947685 = idf(docFreq=270, maxDocs=44218)
            0.09375 = fieldNorm(doc=2560)
      0.06399884 = weight(abstract_txt:speed in 2560) [ClassicSimilarity], result of:
        0.06399884 = score(doc=2560,freq=1.0), product of:
          0.10357462 = queryWeight, product of:
            1.1552066 = boost
            6.590942 = idf(docFreq=164, maxDocs=44218)
            0.013603361 = queryNorm
          0.6179008 = fieldWeight in 2560, product of:
            1.0 = tf(freq=1.0), with freq of:
              1.0 = termFreq=1.0
            6.590942 = idf(docFreq=164, maxDocs=44218)
            0.09375 = fieldNorm(doc=2560)
      0.1263476 = weight(abstract_txt:convergence in 2560) [ClassicSimilarity], result of:
        0.1263476 = score(doc=2560,freq=2.0), product of:
          0.1293719 = queryWeight, product of:
            1.2910794 = boost
            7.3661537 = idf(docFreq=75, maxDocs=44218)
            0.013603361 = queryNorm
          0.97662324 = fieldWeight in 2560, product of:
            1.4142135 = tf(freq=2.0), with freq of:
              2.0 = termFreq=2.0
            7.3661537 = idf(docFreq=75, maxDocs=44218)
            0.09375 = fieldNorm(doc=2560)
      0.9623696 = weight(abstract_txt:pagerank in 2560) [ClassicSimilarity], result of:
        0.9623696 = score(doc=2560,freq=6.0), product of:
          0.5512342 = queryWeight, product of:
            5.330047 = boost
            7.602543 = idf(docFreq=59, maxDocs=44218)
            0.013603361 = queryNorm
          1.7458453 = fieldWeight in 2560, product of:
            2.4494898 = tf(freq=6.0), with freq of:
              6.0 = termFreq=6.0
            7.602543 = idf(docFreq=59, maxDocs=44218)
            0.09375 = fieldNorm(doc=2560)
    0.2 = coord(5/25)
  4. Baeza-Yates, R.; Boldi, P.; Castillo, C.: Generalizing PageRank : damping functions for linkbased ranking algorithms (2006) 0.18 
    0.18456036 = sum of:
  0.18456036 = product of:
    0.7690015 = sum of:
      0.047999196 = weight(abstract_txt:algorithms in 2565) [ClassicSimilarity], result of:
        0.047999196 = score(doc=2565,freq=3.0), product of:
          0.077681035 = queryWeight, product of:
            1.0004387 = boost
            5.707926 = idf(docFreq=398, maxDocs=44218)
            0.013603361 = queryNorm
          0.6179011 = fieldWeight in 2565, product of:
            1.7320508 = tf(freq=3.0), with freq of:
              3.0 = termFreq=3.0
            5.707926 = idf(docFreq=398, maxDocs=44218)
            0.0625 = fieldNorm(doc=2565)
      0.055424698 = weight(abstract_txt:link in 2565) [ClassicSimilarity], result of:
        0.055424698 = score(doc=2565,freq=4.0), product of:
          0.077681035 = queryWeight, product of:
            1.0004387 = boost
            5.707926 = idf(docFreq=398, maxDocs=44218)
            0.013603361 = queryNorm
          0.7134907 = fieldWeight in 2565, product of:
            2.0 = tf(freq=4.0), with freq of:
              4.0 = termFreq=4.0
            5.707926 = idf(docFreq=398, maxDocs=44218)
            0.0625 = fieldNorm(doc=2565)
      0.039503194 = weight(abstract_txt:rank in 2565) [ClassicSimilarity], result of:
        0.039503194 = score(doc=2565,freq=1.0), product of:
          0.09839075 = queryWeight, product of:
            1.1259266 = boost
            6.4238877 = idf(docFreq=194, maxDocs=44218)
            0.013603361 = 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.042665895 = weight(abstract_txt:speed in 2565) [ClassicSimilarity], result of:
        0.042665895 = score(doc=2565,freq=1.0), product of:
          0.10357462 = queryWeight, product of:
            1.1552066 = boost
            6.590942 = idf(docFreq=164, maxDocs=44218)
            0.013603361 = queryNorm
          0.41193387 = fieldWeight in 2565, product of:
            1.0 = tf(freq=1.0), with freq of:
              1.0 = termFreq=1.0
            6.590942 = idf(docFreq=164, maxDocs=44218)
            0.0625 = fieldNorm(doc=2565)
      0.059560828 = weight(abstract_txt:convergence in 2565) [ClassicSimilarity], result of:
        0.059560828 = score(doc=2565,freq=1.0), product of:
          0.1293719 = queryWeight, product of:
            1.2910794 = boost
            7.3661537 = idf(docFreq=75, maxDocs=44218)
            0.013603361 = queryNorm
          0.4603846 = fieldWeight in 2565, product of:
            1.0 = tf(freq=1.0), with freq of:
              1.0 = termFreq=1.0
            7.3661537 = idf(docFreq=75, maxDocs=44218)
            0.0625 = fieldNorm(doc=2565)
      0.5238477 = weight(abstract_txt:pagerank in 2565) [ClassicSimilarity], result of:
        0.5238477 = score(doc=2565,freq=4.0), product of:
          0.5512342 = queryWeight, product of:
            5.330047 = boost
            7.602543 = idf(docFreq=59, maxDocs=44218)
            0.013603361 = 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.24 = coord(6/25)
  5. Bryan, K.; Leise, T.: ¬The $25.000.000.000 eigenvector : the linear algebra behind Google 0.17 
    0.16729742 = sum of:
  0.16729742 = product of:
    1.0456089 = sum of:
      0.041513868 = weight(abstract_txt:algorithm in 1353) [ClassicSimilarity], result of:
        0.041513868 = score(doc=1353,freq=1.0), product of:
          0.07761293 = queryWeight, product of:
            5.705423 = idf(docFreq=399, maxDocs=44218)
            0.013603361 = queryNorm
          0.5348834 = fieldWeight in 1353, product of:
            1.0 = tf(freq=1.0), with freq of:
              1.0 = termFreq=1.0
            5.705423 = idf(docFreq=399, maxDocs=44218)
            0.09375 = fieldNorm(doc=1353)
      0.041568525 = weight(abstract_txt:link in 1353) [ClassicSimilarity], result of:
        0.041568525 = score(doc=1353,freq=1.0), product of:
          0.077681035 = queryWeight, product of:
            1.0004387 = boost
            5.707926 = idf(docFreq=398, maxDocs=44218)
            0.013603361 = queryNorm
          0.53511804 = fieldWeight in 1353, product of:
            1.0 = tf(freq=1.0), with freq of:
              1.0 = termFreq=1.0
            5.707926 = idf(docFreq=398, maxDocs=44218)
            0.09375 = fieldNorm(doc=1353)
      0.40690205 = weight(abstract_txt:matrix in 1353) [ClassicSimilarity], result of:
        0.40690205 = score(doc=1353,freq=2.0), product of:
          0.4478596 = queryWeight, product of:
            4.804342 = boost
            6.8527 = idf(docFreq=126, maxDocs=44218)
            0.013603361 = queryNorm
          0.90854824 = fieldWeight in 1353, product of:
            1.4142135 = tf(freq=2.0), with freq of:
              2.0 = termFreq=2.0
            6.8527 = idf(docFreq=126, maxDocs=44218)
            0.09375 = fieldNorm(doc=1353)
      0.5556244 = weight(abstract_txt:pagerank in 1353) [ClassicSimilarity], result of:
        0.5556244 = score(doc=1353,freq=2.0), product of:
          0.5512342 = queryWeight, product of:
            5.330047 = boost
            7.602543 = idf(docFreq=59, maxDocs=44218)
            0.013603361 = queryNorm
          1.0079644 = fieldWeight in 1353, product of:
            1.4142135 = tf(freq=2.0), with freq of:
              2.0 = termFreq=2.0
            7.602543 = idf(docFreq=59, maxDocs=44218)
            0.09375 = fieldNorm(doc=1353)
    0.16 = coord(4/25)