Document (#32011)

Author
Lempel, R.
Moran, S.
Title
SALSA: the stochastic approach for link-structure analysis
Source
ACM transactions on information systems. 19(2001) no.2, S.131-160
Year
2001
Abstract
Today, when searching for information on the WWW, one usually performs a query through a term-based search engine. These engines return, as the query's result, a list of Web pages whose contents matches the query. For broad-topic queries, such searches often result in a huge set of retrieved documents, many of which are irrelevant to the user. However, much information is contained in the link-structure of the WWW. Information such as which pages are linked to others can be used to augment search algorithms. In this context, Jon Kleinberg introduced the notion of two distinct types of Web pages: hubs and authorities. Kleinberg argued that hubs and authorities exhibit a mutually reinforcing relationship: a good hub will point to many authorities, and a good authority will be pointed at by many hubs. In light of this, he dervised an algoirthm aimed at finding authoritative pages. We present SALSA, a new stochastic approach for link-structure analysis, which examines random walks on graphs derived from the link-structure. We show that both SALSA and Kleinberg's Mutual Reinforcement approach employ the same metaalgorithm. We then prove that SALSA is quivalent to a weighted in degree analysis of the link-sturcutre of WWW subgraphs, making it computationally more efficient than the Mutual reinforcement approach. We compare that results of applying SALSA to the results derived through Kleinberg's approach. These comparisions reveal a topological Phenomenon called the TKC effectwhich, in certain cases, prevents the Mutual reinforcement approach from identifying meaningful authorities.
Theme
Suchmaschinen
Retrievalalgorithmen

Similar documents (author)

  1. Moran, J.M.: Influencia dos meios de comunicacao no conhecimento (1994) 5.94 
    5.9401517 = sum of:
  5.9401517 = weight(author_txt:moran in 2444) [ClassicSimilarity], result of:
    5.9401517 = fieldWeight in 2444, product of:
      1.0 = tf(freq=1.0), with freq of:
        1.0 = termFreq=1.0
      9.504243 = idf(docFreq=8, maxDocs=44421)
      0.625 = fieldNorm(doc=2444)
  2. Moran, D.B.: Multimodal user interfaces in the Open Agent Architecture (1998) 5.94 
    5.9401517 = sum of:
  5.9401517 = weight(author_txt:moran in 4838) [ClassicSimilarity], result of:
    5.9401517 = fieldWeight in 4838, product of:
      1.0 = tf(freq=1.0), with freq of:
        1.0 = termFreq=1.0
      9.504243 = idf(docFreq=8, maxDocs=44421)
      0.625 = fieldNorm(doc=4838)
  3. Kilgour, F.G.; Moran, B.B.: Surname plus recallable title word searches for known items by scholars (2000) 4.75 
    4.7521214 = sum of:
  4.7521214 = weight(author_txt:moran in 5296) [ClassicSimilarity], result of:
    4.7521214 = fieldWeight in 5296, product of:
      1.0 = tf(freq=1.0), with freq of:
        1.0 = termFreq=1.0
      9.504243 = idf(docFreq=8, maxDocs=44421)
      0.5 = fieldNorm(doc=5296)
  4. Olson, G.M.; Moran, T.P.: Introduction to this special issue on experimental comparisons of usability evaluation methods (1998) 4.75 
    4.7521214 = sum of:
  4.7521214 = weight(author_txt:moran in 6102) [ClassicSimilarity], result of:
    4.7521214 = fieldWeight in 6102, product of:
      1.0 = tf(freq=1.0), with freq of:
        1.0 = termFreq=1.0
      9.504243 = idf(docFreq=8, maxDocs=44421)
      0.5 = fieldNorm(doc=6102)
  5. Kilgour, F.G.; Moran, B.B.; Barden, J.R.: Retrieval effectiveness of surname-title-word searches for known items by academic library users (1999) 3.56 
    3.5640912 = sum of:
  3.5640912 = weight(author_txt:moran in 4061) [ClassicSimilarity], result of:
    3.5640912 = fieldWeight in 4061, product of:
      1.0 = tf(freq=1.0), with freq of:
        1.0 = termFreq=1.0
      9.504243 = idf(docFreq=8, maxDocs=44421)
      0.375 = fieldNorm(doc=4061)

Similar documents (content)

  1. Haider, J.: ¬The structuring of information through search : sorting waste with Google (2016) 0.14 
    0.13538967 = sum of:
  0.13538967 = product of:
    0.42309275 = sum of:
      0.020573115 = weight(abstract_txt:through in 4073) [ClassicSimilarity], result of:
        0.020573115 = score(doc=4073,freq=3.0), product of:
          0.05430145 = queryWeight, product of:
            1.0044994 = boost
            3.9998152 = idf(docFreq=2211, maxDocs=44421)
            0.013515178 = queryNorm
          0.3788686 = fieldWeight in 4073, product of:
            1.7320508 = tf(freq=3.0), with freq of:
              3.0 = termFreq=3.0
            3.9998152 = idf(docFreq=2211, maxDocs=44421)
            0.0546875 = fieldNorm(doc=4073)
      0.011930151 = weight(abstract_txt:which in 4073) [ClassicSimilarity], result of:
        0.011930151 = score(doc=4073,freq=3.0), product of:
          0.043225404 = queryWeight, product of:
            1.097638 = boost
            2.9137893 = idf(docFreq=6552, maxDocs=44421)
            0.013515178 = queryNorm
          0.2759986 = fieldWeight in 4073, product of:
            1.7320508 = tf(freq=3.0), with freq of:
              3.0 = termFreq=3.0
            2.9137893 = idf(docFreq=6552, maxDocs=44421)
            0.0546875 = fieldNorm(doc=4073)
      0.008504874 = weight(abstract_txt:that in 4073) [ClassicSimilarity], result of:
        0.008504874 = score(doc=4073,freq=3.0), product of:
          0.03796645 = queryWeight, product of:
            1.1878428 = boost
            2.3649352 = idf(docFreq=11344, maxDocs=44421)
            0.013515178 = queryNorm
          0.22401026 = fieldWeight in 4073, product of:
            1.7320508 = tf(freq=3.0), with freq of:
              3.0 = termFreq=3.0
            2.3649352 = idf(docFreq=11344, maxDocs=44421)
            0.0546875 = fieldNorm(doc=4073)
      0.028212847 = weight(abstract_txt:query in 4073) [ClassicSimilarity], result of:
        0.028212847 = score(doc=4073,freq=2.0), product of:
          0.076725505 = queryWeight, product of:
            1.1940262 = boost
            4.754492 = idf(docFreq=1039, maxDocs=44421)
            0.013515178 = queryNorm
          0.36771145 = fieldWeight in 4073, product of:
            1.4142135 = tf(freq=2.0), with freq of:
              2.0 = termFreq=2.0
            4.754492 = idf(docFreq=1039, maxDocs=44421)
            0.0546875 = fieldNorm(doc=4073)
      0.02698204 = weight(abstract_txt:analysis in 4073) [ClassicSimilarity], result of:
        0.02698204 = score(doc=4073,freq=4.0), product of:
          0.06766728 = queryWeight, product of:
            1.3733429 = boost
            3.6456752 = idf(docFreq=3151, maxDocs=44421)
            0.013515178 = queryNorm
          0.39874572 = fieldWeight in 4073, product of:
            2.0 = tf(freq=4.0), with freq of:
              4.0 = termFreq=4.0
            3.6456752 = idf(docFreq=3151, maxDocs=44421)
            0.0546875 = fieldNorm(doc=4073)
      0.058315508 = weight(abstract_txt:approach in 4073) [ClassicSimilarity], result of:
        0.058315508 = score(doc=4073,freq=4.0), product of:
          0.14251533 = queryWeight, product of:
            2.8186128 = boost
            3.741144 = idf(docFreq=2864, maxDocs=44421)
            0.013515178 = queryNorm
          0.40918761 = fieldWeight in 4073, product of:
            2.0 = tf(freq=4.0), with freq of:
              4.0 = termFreq=4.0
            3.741144 = idf(docFreq=2864, maxDocs=44421)
            0.0546875 = fieldNorm(doc=4073)
      0.18229647 = weight(abstract_txt:authorities in 4073) [ClassicSimilarity], result of:
        0.18229647 = score(doc=4073,freq=2.0), product of:
          0.3353544 = queryWeight, product of:
            3.530295 = boost
            7.028639 = idf(docFreq=106, maxDocs=44421)
            0.013515178 = queryNorm
          0.5435935 = fieldWeight in 4073, product of:
            1.4142135 = tf(freq=2.0), with freq of:
              2.0 = termFreq=2.0
            7.028639 = idf(docFreq=106, maxDocs=44421)
            0.0546875 = fieldNorm(doc=4073)
      0.086277746 = weight(abstract_txt:link in 4073) [ClassicSimilarity], result of:
        0.086277746 = score(doc=4073,freq=1.0), product of:
          0.27641672 = queryWeight, product of:
            3.5834072 = boost
            5.707506 = idf(docFreq=400, maxDocs=44421)
            0.013515178 = queryNorm
          0.31212926 = fieldWeight in 4073, product of:
            1.0 = tf(freq=1.0), with freq of:
              1.0 = termFreq=1.0
            5.707506 = idf(docFreq=400, maxDocs=44421)
            0.0546875 = fieldNorm(doc=4073)
    0.32 = coord(8/25)
  2. Wei, F.; Li, W.; Lu, Q.; He, Y.: Applying two-level reinforcement ranking in query-oriented multidocument summarization (2009) 0.12 
    0.122098126 = sum of:
  0.122098126 = product of:
    0.6104906 = sum of:
      0.011223524 = weight(abstract_txt:that in 107) [ClassicSimilarity], result of:
        0.011223524 = score(doc=107,freq=4.0), product of:
          0.03796645 = queryWeight, product of:
            1.1878428 = boost
            2.3649352 = idf(docFreq=11344, maxDocs=44421)
            0.013515178 = queryNorm
          0.2956169 = fieldWeight in 107, product of:
            2.0 = tf(freq=4.0), with freq of:
              4.0 = termFreq=4.0
            2.3649352 = idf(docFreq=11344, maxDocs=44421)
            0.0625 = fieldNorm(doc=107)
      0.022799425 = weight(abstract_txt:query in 107) [ClassicSimilarity], result of:
        0.022799425 = score(doc=107,freq=1.0), product of:
          0.076725505 = queryWeight, product of:
            1.1940262 = boost
            4.754492 = idf(docFreq=1039, maxDocs=44421)
            0.013515178 = queryNorm
          0.29715574 = fieldWeight in 107, product of:
            1.0 = tf(freq=1.0), with freq of:
              1.0 = termFreq=1.0
            4.754492 = idf(docFreq=1039, maxDocs=44421)
            0.0625 = fieldNorm(doc=107)
      0.021607962 = weight(abstract_txt:many in 107) [ClassicSimilarity], result of:
        0.021607962 = score(doc=107,freq=1.0), product of:
          0.08474162 = queryWeight, product of:
            1.5368731 = boost
            4.0797825 = idf(docFreq=2041, maxDocs=44421)
            0.013515178 = queryNorm
          0.2549864 = fieldWeight in 107, product of:
            1.0 = tf(freq=1.0), with freq of:
              1.0 = termFreq=1.0
            4.0797825 = idf(docFreq=2041, maxDocs=44421)
            0.0625 = fieldNorm(doc=107)
      0.17046458 = weight(abstract_txt:mutual in 107) [ClassicSimilarity], result of:
        0.17046458 = score(doc=107,freq=2.0), product of:
          0.26654285 = queryWeight, product of:
            2.7256691 = boost
            7.2355595 = idf(docFreq=86, maxDocs=44421)
            0.013515178 = queryNorm
          0.6395391 = fieldWeight in 107, product of:
            1.4142135 = tf(freq=2.0), with freq of:
              2.0 = termFreq=2.0
            7.2355595 = idf(docFreq=86, maxDocs=44421)
            0.0625 = fieldNorm(doc=107)
      0.38439515 = weight(abstract_txt:reinforcement in 107) [ClassicSimilarity], result of:
        0.38439515 = score(doc=107,freq=3.0), product of:
          0.40040463 = queryWeight, product of:
            3.340713 = boost
            8.868255 = idf(docFreq=16, maxDocs=44421)
            0.013515178 = queryNorm
          0.9600167 = fieldWeight in 107, product of:
            1.7320508 = tf(freq=3.0), with freq of:
              3.0 = termFreq=3.0
            8.868255 = idf(docFreq=16, maxDocs=44421)
            0.0625 = fieldNorm(doc=107)
    0.2 = coord(5/25)
  3. Kleinberg, J.M.: Authoritative sources in a hyperlinked environment (1998) 0.12 
    0.116846405 = sum of:
  0.116846405 = product of:
    0.48686004 = sum of:
      0.01696842 = weight(abstract_txt:through in 1005) [ClassicSimilarity], result of:
        0.01696842 = score(doc=1005,freq=1.0), product of:
          0.05430145 = queryWeight, product of:
            1.0044994 = boost
            3.9998152 = idf(docFreq=2211, maxDocs=44421)
            0.013515178 = queryNorm
          0.31248558 = fieldWeight in 1005, product of:
            1.0 = tf(freq=1.0), with freq of:
              1.0 = termFreq=1.0
            3.9998152 = idf(docFreq=2211, maxDocs=44421)
            0.078125 = fieldNorm(doc=1005)
      0.009920288 = weight(abstract_txt:that in 1005) [ClassicSimilarity], result of:
        0.009920288 = score(doc=1005,freq=2.0), product of:
          0.03796645 = queryWeight, product of:
            1.1878428 = boost
            2.3649352 = idf(docFreq=11344, maxDocs=44421)
            0.013515178 = queryNorm
          0.2612909 = fieldWeight in 1005, product of:
            1.4142135 = tf(freq=2.0), with freq of:
              2.0 = termFreq=2.0
            2.3649352 = idf(docFreq=11344, maxDocs=44421)
            0.078125 = fieldNorm(doc=1005)
      0.019272886 = weight(abstract_txt:analysis in 1005) [ClassicSimilarity], result of:
        0.019272886 = score(doc=1005,freq=1.0), product of:
          0.06766728 = queryWeight, product of:
            1.3733429 = boost
            3.6456752 = idf(docFreq=3151, maxDocs=44421)
            0.013515178 = queryNorm
          0.28481838 = fieldWeight in 1005, product of:
            1.0 = tf(freq=1.0), with freq of:
              1.0 = termFreq=1.0
            3.6456752 = idf(docFreq=3151, maxDocs=44421)
            0.078125 = fieldNorm(doc=1005)
      0.062078405 = weight(abstract_txt:structure in 1005) [ClassicSimilarity], result of:
        0.062078405 = score(doc=1005,freq=2.0), product of:
          0.1289271 = queryWeight, product of:
            2.188926 = boost
            4.3580413 = idf(docFreq=1545, maxDocs=44421)
            0.013515178 = queryNorm
          0.48150006 = fieldWeight in 1005, product of:
            1.4142135 = tf(freq=2.0), with freq of:
              2.0 = termFreq=2.0
            4.3580413 = idf(docFreq=1545, maxDocs=44421)
            0.078125 = fieldNorm(doc=1005)
      0.13211219 = weight(abstract_txt:pages in 1005) [ClassicSimilarity], result of:
        0.13211219 = score(doc=1005,freq=2.0), product of:
          0.2133106 = queryWeight, product of:
            2.8155627 = boost
            5.6056433 = idf(docFreq=443, maxDocs=44421)
            0.013515178 = queryNorm
          0.6193419 = fieldWeight in 1005, product of:
            1.4142135 = tf(freq=2.0), with freq of:
              2.0 = termFreq=2.0
            5.6056433 = idf(docFreq=443, maxDocs=44421)
            0.078125 = fieldNorm(doc=1005)
      0.24650784 = weight(abstract_txt:link in 1005) [ClassicSimilarity], result of:
        0.24650784 = score(doc=1005,freq=4.0), product of:
          0.27641672 = queryWeight, product of:
            3.5834072 = boost
            5.707506 = idf(docFreq=400, maxDocs=44421)
            0.013515178 = queryNorm
          0.89179784 = fieldWeight in 1005, product of:
            2.0 = tf(freq=4.0), with freq of:
              4.0 = termFreq=4.0
            5.707506 = idf(docFreq=400, maxDocs=44421)
            0.078125 = fieldNorm(doc=1005)
    0.24 = coord(6/25)
  4. Bidoki, A.M.Z.; Yazdani, N.: an intelligent ranking algorithm for web pages : DistanceRank (2008) 0.12 
    0.11644622 = sum of:
  0.11644622 = product of:
    0.5822311 = sum of:
      0.009839822 = weight(abstract_txt:which in 3068) [ClassicSimilarity], result of:
        0.009839822 = score(doc=3068,freq=1.0), product of:
          0.043225404 = queryWeight, product of:
            1.097638 = boost
            2.9137893 = idf(docFreq=6552, maxDocs=44421)
            0.013515178 = queryNorm
          0.2276398 = fieldWeight in 3068, product of:
            1.0 = tf(freq=1.0), with freq of:
              1.0 = termFreq=1.0
            2.9137893 = idf(docFreq=6552, maxDocs=44421)
            0.078125 = fieldNorm(doc=3068)
      0.009920288 = weight(abstract_txt:that in 3068) [ClassicSimilarity], result of:
        0.009920288 = score(doc=3068,freq=2.0), product of:
          0.03796645 = queryWeight, product of:
            1.1878428 = boost
            2.3649352 = idf(docFreq=11344, maxDocs=44421)
            0.013515178 = queryNorm
          0.2612909 = fieldWeight in 3068, product of:
            1.4142135 = tf(freq=2.0), with freq of:
              2.0 = termFreq=2.0
            2.3649352 = idf(docFreq=11344, maxDocs=44421)
            0.078125 = fieldNorm(doc=3068)
      0.16180374 = weight(abstract_txt:pages in 3068) [ClassicSimilarity], result of:
        0.16180374 = score(doc=3068,freq=3.0), product of:
          0.2133106 = queryWeight, product of:
            2.8155627 = boost
            5.6056433 = idf(docFreq=443, maxDocs=44421)
            0.013515178 = queryNorm
          0.75853586 = fieldWeight in 3068, product of:
            1.7320508 = tf(freq=3.0), with freq of:
              3.0 = termFreq=3.0
            5.6056433 = idf(docFreq=443, maxDocs=44421)
            0.078125 = fieldNorm(doc=3068)
      0.2774133 = weight(abstract_txt:reinforcement in 3068) [ClassicSimilarity], result of:
        0.2774133 = score(doc=3068,freq=1.0), product of:
          0.40040463 = queryWeight, product of:
            3.340713 = boost
            8.868255 = idf(docFreq=16, maxDocs=44421)
            0.013515178 = queryNorm
          0.6928324 = fieldWeight in 3068, product of:
            1.0 = tf(freq=1.0), with freq of:
              1.0 = termFreq=1.0
            8.868255 = idf(docFreq=16, maxDocs=44421)
            0.078125 = fieldNorm(doc=3068)
      0.12325392 = weight(abstract_txt:link in 3068) [ClassicSimilarity], result of:
        0.12325392 = score(doc=3068,freq=1.0), product of:
          0.27641672 = queryWeight, product of:
            3.5834072 = boost
            5.707506 = idf(docFreq=400, maxDocs=44421)
            0.013515178 = queryNorm
          0.44589892 = fieldWeight in 3068, 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=3068)
    0.2 = coord(5/25)
  5. Picard, J.; Savoy, J.: Enhancing retrieval with hyperlinks : a general model based on propositional argumentation systems (2003) 0.11 
    0.11056849 = sum of:
  0.11056849 = product of:
    0.46070206 = sum of:
      0.007871858 = weight(abstract_txt:which in 2427) [ClassicSimilarity], result of:
        0.007871858 = score(doc=2427,freq=1.0), product of:
          0.043225404 = queryWeight, product of:
            1.097638 = boost
            2.9137893 = idf(docFreq=6552, maxDocs=44421)
            0.013515178 = queryNorm
          0.18211183 = fieldWeight in 2427, product of:
            1.0 = tf(freq=1.0), with freq of:
              1.0 = termFreq=1.0
            2.9137893 = idf(docFreq=6552, maxDocs=44421)
            0.0625 = fieldNorm(doc=2427)
      0.005611762 = weight(abstract_txt:that in 2427) [ClassicSimilarity], result of:
        0.005611762 = score(doc=2427,freq=1.0), product of:
          0.03796645 = queryWeight, product of:
            1.1878428 = boost
            2.3649352 = idf(docFreq=11344, maxDocs=44421)
            0.013515178 = queryNorm
          0.14780845 = fieldWeight in 2427, product of:
            1.0 = tf(freq=1.0), with freq of:
              1.0 = termFreq=1.0
            2.3649352 = idf(docFreq=11344, maxDocs=44421)
            0.0625 = fieldNorm(doc=2427)
      0.03511685 = weight(abstract_txt:structure in 2427) [ClassicSimilarity], result of:
        0.03511685 = score(doc=2427,freq=1.0), product of:
          0.1289271 = queryWeight, product of:
            2.188926 = boost
            4.3580413 = idf(docFreq=1545, maxDocs=44421)
            0.013515178 = queryNorm
          0.27237758 = fieldWeight in 2427, product of:
            1.0 = tf(freq=1.0), with freq of:
              1.0 = termFreq=1.0
            4.3580413 = idf(docFreq=1545, maxDocs=44421)
            0.0625 = fieldNorm(doc=2427)
      0.033323146 = weight(abstract_txt:approach in 2427) [ClassicSimilarity], result of:
        0.033323146 = score(doc=2427,freq=1.0), product of:
          0.14251533 = queryWeight, product of:
            2.8186128 = boost
            3.741144 = idf(docFreq=2864, maxDocs=44421)
            0.013515178 = queryNorm
          0.2338215 = fieldWeight in 2427, product of:
            1.0 = tf(freq=1.0), with freq of:
              1.0 = termFreq=1.0
            3.741144 = idf(docFreq=2864, maxDocs=44421)
            0.0625 = fieldNorm(doc=2427)
      0.23146062 = weight(abstract_txt:hubs in 2427) [ClassicSimilarity], result of:
        0.23146062 = score(doc=2427,freq=1.0), product of:
          0.4117867 = queryWeight, product of:
            3.3878624 = boost
            8.993418 = idf(docFreq=14, maxDocs=44421)
            0.013515178 = queryNorm
          0.5620886 = fieldWeight in 2427, product of:
            1.0 = tf(freq=1.0), with freq of:
              1.0 = termFreq=1.0
            8.993418 = idf(docFreq=14, maxDocs=44421)
            0.0625 = fieldNorm(doc=2427)
      0.14731781 = weight(abstract_txt:authorities in 2427) [ClassicSimilarity], result of:
        0.14731781 = score(doc=2427,freq=1.0), product of:
          0.3353544 = queryWeight, product of:
            3.530295 = boost
            7.028639 = idf(docFreq=106, maxDocs=44421)
            0.013515178 = queryNorm
          0.43928993 = fieldWeight in 2427, product of:
            1.0 = tf(freq=1.0), with freq of:
              1.0 = termFreq=1.0
            7.028639 = idf(docFreq=106, maxDocs=44421)
            0.0625 = fieldNorm(doc=2427)
    0.24 = coord(6/25)