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.30051956 = sum of:
  0.30051956 = product of:
    1.0732841 = sum of:
      0.027713997 = weight(abstract_txt:link in 3564) [ClassicSimilarity], result of:
        0.027713997 = score(doc=3564,freq=1.0), product of:
          0.07769137 = queryWeight, product of:
            1.0013076 = boost
            5.707506 = idf(docFreq=400, maxDocs=44421)
            0.013594364 = queryNorm
          0.35671914 = fieldWeight in 3564, product of:
            1.0 = tf(freq=1.0), with freq of:
              1.0 = termFreq=1.0
            5.707506 = idf(docFreq=400, maxDocs=44421)
            0.0625 = fieldNorm(doc=3564)
      0.039410572 = weight(abstract_txt:rank in 3564) [ClassicSimilarity], result of:
        0.039410572 = score(doc=3564,freq=1.0), product of:
          0.09824606 = queryWeight, product of:
            1.1260008 = boost
            6.418264 = idf(docFreq=196, maxDocs=44421)
            0.013594364 = queryNorm
          0.4011415 = fieldWeight in 3564, product of:
            1.0 = tf(freq=1.0), with freq of:
              1.0 = termFreq=1.0
            6.418264 = idf(docFreq=196, maxDocs=44421)
            0.0625 = fieldNorm(doc=3564)
      0.046337944 = weight(abstract_txt:detection in 3564) [ClassicSimilarity], result of:
        0.046337944 = score(doc=3564,freq=1.0), product of:
          0.10944548 = queryWeight, product of:
            1.1884476 = boost
            6.774214 = idf(docFreq=137, maxDocs=44421)
            0.013594364 = queryNorm
          0.42338836 = fieldWeight in 3564, product of:
            1.0 = tf(freq=1.0), with freq of:
              1.0 = termFreq=1.0
            6.774214 = idf(docFreq=137, maxDocs=44421)
            0.0625 = fieldNorm(doc=3564)
      0.059688717 = weight(abstract_txt:convergence in 3564) [ClassicSimilarity], result of:
        0.059688717 = score(doc=3564,freq=1.0), product of:
          0.12956911 = queryWeight, product of:
            1.2930993 = boost
            7.370734 = idf(docFreq=75, maxDocs=44421)
            0.013594364 = queryNorm
          0.4606709 = fieldWeight in 3564, product of:
            1.0 = tf(freq=1.0), with freq of:
              1.0 = termFreq=1.0
            7.370734 = idf(docFreq=75, maxDocs=44421)
            0.0625 = fieldNorm(doc=3564)
      0.06561775 = weight(abstract_txt:closed in 3564) [ClassicSimilarity], result of:
        0.06561775 = score(doc=3564,freq=1.0), product of:
          0.13801327 = queryWeight, product of:
            1.3345706 = boost
            7.607123 = idf(docFreq=59, maxDocs=44421)
            0.013594364 = queryNorm
          0.47544518 = fieldWeight in 3564, product of:
            1.0 = tf(freq=1.0), with freq of:
              1.0 = termFreq=1.0
            7.607123 = idf(docFreq=59, maxDocs=44421)
            0.0625 = fieldNorm(doc=3564)
      0.19159524 = weight(abstract_txt:matrix in 3564) [ClassicSimilarity], result of:
        0.19159524 = score(doc=3564,freq=1.0), product of:
          0.4475585 = queryWeight, product of:
            4.806578 = boost
            6.849437 = idf(docFreq=127, maxDocs=44421)
            0.013594364 = queryNorm
          0.42808983 = fieldWeight in 3564, product of:
            1.0 = tf(freq=1.0), with freq of:
              1.0 = termFreq=1.0
            6.849437 = idf(docFreq=127, maxDocs=44421)
            0.0625 = fieldNorm(doc=3564)
      0.64292 = weight(abstract_txt:pagerank in 3564) [ClassicSimilarity], result of:
        0.64292 = score(doc=3564,freq=6.0), product of:
          0.5520531 = queryWeight, product of:
            5.3382826 = boost
            7.607123 = idf(docFreq=59, maxDocs=44421)
            0.013594364 = queryNorm
          1.1645981 = fieldWeight in 3564, product of:
            2.4494898 = tf(freq=6.0), with freq of:
              6.0 = termFreq=6.0
            7.607123 = idf(docFreq=59, maxDocs=44421)
            0.0625 = fieldNorm(doc=3564)
    0.28 = coord(7/25)
  2. Dominich, S.; Skrop, A.: PageRank and interaction information retrieval (2005) 0.27 
    0.26842356 = sum of:
  0.26842356 = product of:
    1.3421178 = sum of:
      0.0346425 = weight(abstract_txt:link in 4268) [ClassicSimilarity], result of:
        0.0346425 = score(doc=4268,freq=1.0), product of:
          0.07769137 = queryWeight, product of:
            1.0013076 = boost
            5.707506 = idf(docFreq=400, maxDocs=44421)
            0.013594364 = queryNorm
          0.44589892 = fieldWeight in 4268, product of:
            1.0 = tf(freq=1.0), with freq of:
              1.0 = termFreq=1.0
            5.707506 = idf(docFreq=400, maxDocs=44421)
            0.078125 = fieldNorm(doc=4268)
      0.11372494 = weight(abstract_txt:stochastic in 4268) [ClassicSimilarity], result of:
        0.11372494 = score(doc=4268,freq=1.0), product of:
          0.17160785 = queryWeight, product of:
            1.4881603 = boost
            8.482592 = idf(docFreq=24, maxDocs=44421)
            0.013594364 = queryNorm
          0.66270244 = fieldWeight in 4268, product of:
            1.0 = tf(freq=1.0), with freq of:
              1.0 = termFreq=1.0
            8.482592 = idf(docFreq=24, maxDocs=44421)
            0.078125 = fieldNorm(doc=4268)
      0.08621523 = weight(abstract_txt:google in 4268) [ClassicSimilarity], result of:
        0.08621523 = score(doc=4268,freq=1.0), product of:
          0.2057768 = queryWeight, product of:
            2.822539 = boost
            5.3628736 = idf(docFreq=565, maxDocs=44421)
            0.013594364 = queryNorm
          0.4189745 = fieldWeight in 4268, product of:
            1.0 = tf(freq=1.0), with freq of:
              1.0 = termFreq=1.0
            5.3628736 = idf(docFreq=565, maxDocs=44421)
            0.078125 = fieldNorm(doc=4268)
      0.23949404 = weight(abstract_txt:matrix in 4268) [ClassicSimilarity], result of:
        0.23949404 = score(doc=4268,freq=1.0), product of:
          0.4475585 = queryWeight, product of:
            4.806578 = boost
            6.849437 = idf(docFreq=127, maxDocs=44421)
            0.013594364 = queryNorm
          0.53511226 = fieldWeight in 4268, product of:
            1.0 = tf(freq=1.0), with freq of:
              1.0 = termFreq=1.0
            6.849437 = idf(docFreq=127, maxDocs=44421)
            0.078125 = fieldNorm(doc=4268)
      0.86804116 = weight(abstract_txt:pagerank in 4268) [ClassicSimilarity], result of:
        0.86804116 = score(doc=4268,freq=7.0), product of:
          0.5520531 = queryWeight, product of:
            5.3382826 = boost
            7.607123 = idf(docFreq=59, maxDocs=44421)
            0.013594364 = queryNorm
          1.5723871 = fieldWeight in 4268, product of:
            2.6457512 = tf(freq=7.0), with freq of:
              7.0 = termFreq=7.0
            7.607123 = idf(docFreq=59, maxDocs=44421)
            0.078125 = fieldNorm(doc=4268)
    0.2 = coord(5/25)
  3. Kamvar, S.; Haveliwala, T.; Golub, G.: Adaptive methods for the computation of PageRank (2003) 0.26 
    0.25536108 = sum of:
  0.25536108 = product of:
    1.2768054 = sum of:
      0.07190886 = weight(abstract_txt:algorithm in 3560) [ClassicSimilarity], result of:
        0.07190886 = score(doc=3560,freq=3.0), product of:
          0.07762358 = queryWeight, product of:
            1.0008707 = boost
            5.7050157 = idf(docFreq=401, maxDocs=44421)
            0.013594364 = queryNorm
          0.9263791 = fieldWeight in 3560, product of:
            1.7320508 = tf(freq=3.0), with freq of:
              3.0 = termFreq=3.0
            5.7050157 = idf(docFreq=401, maxDocs=44421)
            0.09375 = fieldNorm(doc=3560)
      0.049923398 = weight(abstract_txt:furthermore in 3560) [ClassicSimilarity], result of:
        0.049923398 = score(doc=3560,freq=1.0), product of:
          0.087777235 = queryWeight, product of:
            1.0643196 = boost
            6.066678 = idf(docFreq=279, maxDocs=44421)
            0.013594364 = queryNorm
          0.5687511 = fieldWeight in 3560, product of:
            1.0 = tf(freq=1.0), with freq of:
              1.0 = termFreq=1.0
            6.066678 = idf(docFreq=279, maxDocs=44421)
            0.09375 = fieldNorm(doc=3560)
      0.06397418 = weight(abstract_txt:speed in 3560) [ClassicSimilarity], result of:
        0.06397418 = score(doc=3560,freq=1.0), product of:
          0.103557676 = queryWeight, product of:
            1.1560384 = boost
            6.58948 = idf(docFreq=165, maxDocs=44421)
            0.013594364 = queryNorm
          0.61776376 = fieldWeight in 3560, product of:
            1.0 = tf(freq=1.0), with freq of:
              1.0 = termFreq=1.0
            6.58948 = idf(docFreq=165, maxDocs=44421)
            0.09375 = fieldNorm(doc=3560)
      0.12661889 = weight(abstract_txt:convergence in 3560) [ClassicSimilarity], result of:
        0.12661889 = score(doc=3560,freq=2.0), product of:
          0.12956911 = queryWeight, product of:
            1.2930993 = boost
            7.370734 = idf(docFreq=75, maxDocs=44421)
            0.013594364 = queryNorm
          0.9772305 = fieldWeight in 3560, product of:
            1.4142135 = tf(freq=2.0), with freq of:
              2.0 = termFreq=2.0
            7.370734 = idf(docFreq=75, maxDocs=44421)
            0.09375 = fieldNorm(doc=3560)
      0.96438 = weight(abstract_txt:pagerank in 3560) [ClassicSimilarity], result of:
        0.96438 = score(doc=3560,freq=6.0), product of:
          0.5520531 = queryWeight, product of:
            5.3382826 = boost
            7.607123 = idf(docFreq=59, maxDocs=44421)
            0.013594364 = queryNorm
          1.7468972 = fieldWeight in 3560, product of:
            2.4494898 = tf(freq=6.0), with freq of:
              6.0 = termFreq=6.0
            7.607123 = idf(docFreq=59, maxDocs=44421)
            0.09375 = fieldNorm(doc=3560)
    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.1847839 = sum of:
  0.1847839 = product of:
    0.769933 = sum of:
      0.047814243 = weight(abstract_txt:algorithms in 3565) [ClassicSimilarity], result of:
        0.047814243 = score(doc=3565,freq=3.0), product of:
          0.077488594 = queryWeight, product of:
            5.7000527 = idf(docFreq=403, maxDocs=44421)
            0.013594364 = queryNorm
          0.6170488 = fieldWeight in 3565, product of:
            1.7320508 = tf(freq=3.0), with freq of:
              3.0 = termFreq=3.0
            5.7000527 = idf(docFreq=403, maxDocs=44421)
            0.0625 = fieldNorm(doc=3565)
      0.055427995 = weight(abstract_txt:link in 3565) [ClassicSimilarity], result of:
        0.055427995 = score(doc=3565,freq=4.0), product of:
          0.07769137 = queryWeight, product of:
            1.0013076 = boost
            5.707506 = idf(docFreq=400, maxDocs=44421)
            0.013594364 = queryNorm
          0.7134383 = fieldWeight in 3565, product of:
            2.0 = tf(freq=4.0), with freq of:
              4.0 = termFreq=4.0
            5.707506 = idf(docFreq=400, maxDocs=44421)
            0.0625 = fieldNorm(doc=3565)
      0.039410572 = weight(abstract_txt:rank in 3565) [ClassicSimilarity], result of:
        0.039410572 = score(doc=3565,freq=1.0), product of:
          0.09824606 = queryWeight, product of:
            1.1260008 = boost
            6.418264 = idf(docFreq=196, maxDocs=44421)
            0.013594364 = queryNorm
          0.4011415 = fieldWeight in 3565, product of:
            1.0 = tf(freq=1.0), with freq of:
              1.0 = termFreq=1.0
            6.418264 = idf(docFreq=196, maxDocs=44421)
            0.0625 = fieldNorm(doc=3565)
      0.04264945 = weight(abstract_txt:speed in 3565) [ClassicSimilarity], result of:
        0.04264945 = score(doc=3565,freq=1.0), product of:
          0.103557676 = queryWeight, product of:
            1.1560384 = boost
            6.58948 = idf(docFreq=165, maxDocs=44421)
            0.013594364 = queryNorm
          0.4118425 = fieldWeight in 3565, product of:
            1.0 = tf(freq=1.0), with freq of:
              1.0 = termFreq=1.0
            6.58948 = idf(docFreq=165, maxDocs=44421)
            0.0625 = fieldNorm(doc=3565)
      0.059688717 = weight(abstract_txt:convergence in 3565) [ClassicSimilarity], result of:
        0.059688717 = score(doc=3565,freq=1.0), product of:
          0.12956911 = queryWeight, product of:
            1.2930993 = boost
            7.370734 = idf(docFreq=75, maxDocs=44421)
            0.013594364 = queryNorm
          0.4606709 = fieldWeight in 3565, product of:
            1.0 = tf(freq=1.0), with freq of:
              1.0 = termFreq=1.0
            7.370734 = idf(docFreq=75, maxDocs=44421)
            0.0625 = fieldNorm(doc=3565)
      0.524942 = weight(abstract_txt:pagerank in 3565) [ClassicSimilarity], result of:
        0.524942 = score(doc=3565,freq=4.0), product of:
          0.5520531 = queryWeight, product of:
            5.3382826 = boost
            7.607123 = idf(docFreq=59, maxDocs=44421)
            0.013594364 = queryNorm
          0.95089036 = fieldWeight in 3565, product of:
            2.0 = tf(freq=4.0), with freq of:
              4.0 = termFreq=4.0
            7.607123 = idf(docFreq=59, maxDocs=44421)
            0.0625 = fieldNorm(doc=3565)
    0.24 = coord(6/25)
  5. Bryan, K.; Leise, T.: ¬The $25.000.000.000 eigenvector : the linear algebra behind Google 0.17 
    0.16740921 = sum of:
  0.16740921 = product of:
    1.0463076 = sum of:
      0.041516602 = weight(abstract_txt:algorithm in 2353) [ClassicSimilarity], result of:
        0.041516602 = score(doc=2353,freq=1.0), product of:
          0.07762358 = queryWeight, product of:
            1.0008707 = boost
            5.7050157 = idf(docFreq=401, maxDocs=44421)
            0.013594364 = queryNorm
          0.53484523 = fieldWeight in 2353, product of:
            1.0 = tf(freq=1.0), with freq of:
              1.0 = termFreq=1.0
            5.7050157 = idf(docFreq=401, maxDocs=44421)
            0.09375 = fieldNorm(doc=2353)
      0.041571 = weight(abstract_txt:link in 2353) [ClassicSimilarity], result of:
        0.041571 = score(doc=2353,freq=1.0), product of:
          0.07769137 = queryWeight, product of:
            1.0013076 = boost
            5.707506 = idf(docFreq=400, maxDocs=44421)
            0.013594364 = queryNorm
          0.5350787 = fieldWeight in 2353, product of:
            1.0 = tf(freq=1.0), with freq of:
              1.0 = termFreq=1.0
            5.707506 = idf(docFreq=400, maxDocs=44421)
            0.09375 = fieldNorm(doc=2353)
      0.4064349 = weight(abstract_txt:matrix in 2353) [ClassicSimilarity], result of:
        0.4064349 = score(doc=2353,freq=2.0), product of:
          0.4475585 = queryWeight, product of:
            4.806578 = boost
            6.849437 = idf(docFreq=127, maxDocs=44421)
            0.013594364 = queryNorm
          0.9081157 = fieldWeight in 2353, product of:
            1.4142135 = tf(freq=2.0), with freq of:
              2.0 = termFreq=2.0
            6.849437 = idf(docFreq=127, maxDocs=44421)
            0.09375 = fieldNorm(doc=2353)
      0.55678505 = weight(abstract_txt:pagerank in 2353) [ClassicSimilarity], result of:
        0.55678505 = score(doc=2353,freq=2.0), product of:
          0.5520531 = queryWeight, product of:
            5.3382826 = boost
            7.607123 = idf(docFreq=59, maxDocs=44421)
            0.013594364 = queryNorm
          1.0085715 = fieldWeight in 2353, product of:
            1.4142135 = tf(freq=2.0), with freq of:
              2.0 = termFreq=2.0
            7.607123 = idf(docFreq=59, maxDocs=44421)
            0.09375 = fieldNorm(doc=2353)
    0.16 = coord(4/25)