Document (#32005)

Author

Agosti, M.
Pretto, L.

Title

¬A theoretical study of a generalized version of kleinberg's HITS algorithm

Source

Advances in mathematical/formal methods in information retrieval. 8(2005) no.2 , S.219-243

Year

2005

Abstract

Kleinberg's HITS (Hyperlink-Induced Topic Search) algorithm (Kleinberg 1999), which was originally developed in a Web context, tries to infer the authoritativeness of a Web page in relation to a specific query using the structure of a subgraph of the Web graph, which is obtained considering this specific query. Recent applications of this algorithm in contexts far removed from that of Web searching (Bacchin, Ferro and Melucci 2002, Ng et al. 2001) inspired us to study the algorithm in the abstract, independently of its particular applications, trying to mathematically illuminate its behaviour. In the present paper we detail this theoretical analysis. The original work starts from the definition of a revised and more general version of the algorithm, which includes the classic one as a particular case. We perform an analysis of the structure of two particular matrices, essential to studying the behaviour of the algorithm, and we prove the convergence of the algorithm in the most general case, finding the analytic expression of the vectors to which it converges. Then we study the symmetry of the algorithm and prove the equivalence between the existence of symmetry and the independence from the order of execution of some basic operations on initial vectors. Finally, we expound some interesting consequences of our theoretical results.

Theme

Suchmaschinen
Retrievalalgorithmen

Object

HITS-Algorithmus

Similar documents (author)

1. Agosti, M.: Hypertext and information retrieval (1993) 5.81

   5.814733 = sum of:
     5.814733 = weight(author_txt:agosti in 4707) [ClassicSimilarity], result of:
       5.814733 = fieldWeight in 4707, product of:
         1.0 = tf(freq=1.0), with freq of:
           1.0 = termFreq=1.0
         9.303573 = idf(docFreq=10, maxDocs=44421)
         0.625 = fieldNorm(doc=4707)
   

2. Agosti, M.; Allan, J.: Introduction to the special issue on methods and tools for the automatic construction of hypertext (1997) 4.65

   4.6517863 = sum of:
     4.6517863 = weight(author_txt:agosti in 1149) [ClassicSimilarity], result of:
       4.6517863 = fieldWeight in 1149, product of:
         1.0 = tf(freq=1.0), with freq of:
           1.0 = termFreq=1.0
         9.303573 = idf(docFreq=10, maxDocs=44421)
         0.5 = fieldNorm(doc=1149)
   

3. Agosti, M.; Smeaton, A.F.: Information retrieval and hypertext (1996) 4.65

   4.6517863 = sum of:
     4.6517863 = weight(author_txt:agosti in 1497) [ClassicSimilarity], result of:
       4.6517863 = fieldWeight in 1497, product of:
         1.0 = tf(freq=1.0), with freq of:
           1.0 = termFreq=1.0
         9.303573 = idf(docFreq=10, maxDocs=44421)
         0.5 = fieldNorm(doc=1497)
   

4. Agosti, M.; Melucci, M.: Information retrieval techniques for the automatic construction of hypertext (2000) 4.65

   4.6517863 = sum of:
     4.6517863 = weight(author_txt:agosti in 5671) [ClassicSimilarity], result of:
       4.6517863 = fieldWeight in 5671, product of:
         1.0 = tf(freq=1.0), with freq of:
           1.0 = termFreq=1.0
         9.303573 = idf(docFreq=10, maxDocs=44421)
         0.5 = fieldNorm(doc=5671)
   

5. Agosti, M.; Colotti, R.; Gradenigo, G.: Issues of data modelling in information retrieval (1991) 3.49

   3.4888396 = sum of:
     3.4888396 = weight(author_txt:agosti in 5093) [ClassicSimilarity], result of:
       3.4888396 = fieldWeight in 5093, product of:
         1.0 = tf(freq=1.0), with freq of:
           1.0 = termFreq=1.0
         9.303573 = idf(docFreq=10, maxDocs=44421)
         0.375 = fieldNorm(doc=5093)
   

Similar documents (content)

1. Quirin, A.; Cordón, O.; Guerrero-Bote, V.P.; Vargas-Quesada, B.; Moya-Anegón, F.: A quick MST-based algorithm to obtain Pathfinder networks (oo, n - 1) (2008) 0.15

   0.15310538 = sum of:
     0.15310538 = product of:
       0.6379391 = sum of:
         0.017526628 = weight(abstract_txt:from in 3371) [ClassicSimilarity], result of:
           0.017526628 = score(doc=3371,freq=4.0), product of:
             0.05081289 = queryWeight, product of:
               1.0126102 = boost
               2.759399 = idf(docFreq=7646, maxDocs=44421)
               0.01818516 = queryNorm
             0.34492487 = fieldWeight in 3371, product of:
               2.0 = tf(freq=4.0), with freq of:
                 4.0 = termFreq=4.0
               2.759399 = idf(docFreq=7646, maxDocs=44421)
               0.0625 = fieldNorm(doc=3371)
         0.022196215 = weight(abstract_txt:specific in 3371) [ClassicSimilarity], result of:
           0.022196215 = score(doc=3371,freq=1.0), product of:
             0.08248035 = queryWeight, product of:
               1.0533798 = boost
               4.305746 = idf(docFreq=1628, maxDocs=44421)
               0.01818516 = queryNorm
             0.26910913 = fieldWeight in 3371, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               4.305746 = idf(docFreq=1628, maxDocs=44421)
               0.0625 = fieldNorm(doc=3371)
         0.029544406 = weight(abstract_txt:applications in 3371) [ClassicSimilarity], result of:
           0.029544406 = score(doc=3371,freq=1.0), product of:
             0.09980402 = queryWeight, product of:
               1.158734 = boost
               4.7363873 = idf(docFreq=1058, maxDocs=44421)
               0.01818516 = queryNorm
             0.2960242 = fieldWeight in 3371, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               4.7363873 = idf(docFreq=1058, maxDocs=44421)
               0.0625 = fieldNorm(doc=3371)
         0.04334475 = weight(abstract_txt:case in 3371) [ClassicSimilarity], result of:
           0.04334475 = score(doc=3371,freq=2.0), product of:
             0.10227721 = queryWeight, product of:
               1.1730031 = boost
               4.794713 = idf(docFreq=998, maxDocs=44421)
               0.01818516 = queryNorm
             0.42379674 = fieldWeight in 3371, product of:
               1.4142135 = tf(freq=2.0), with freq of:
                 2.0 = termFreq=2.0
               4.794713 = idf(docFreq=998, maxDocs=44421)
               0.0625 = fieldNorm(doc=3371)
         0.019455979 = weight(abstract_txt:which in 3371) [ClassicSimilarity], result of:
           0.019455979 = score(doc=3371,freq=2.0), product of:
             0.07554399 = queryWeight, product of:
               1.4256886 = boost
               2.9137893 = idf(docFreq=6552, maxDocs=44421)
               0.01818516 = queryNorm
             0.25754502 = fieldWeight in 3371, product of:
               1.4142135 = tf(freq=2.0), with freq of:
                 2.0 = termFreq=2.0
               2.9137893 = idf(docFreq=6552, maxDocs=44421)
               0.0625 = fieldNorm(doc=3371)
         0.5058711 = weight(abstract_txt:algorithm in 3371) [ClassicSimilarity], result of:
           0.5058711 = score(doc=3371,freq=6.0), product of:
             0.5791984 = queryWeight, product of:
               5.582817 = boost
               5.7050157 = idf(docFreq=401, maxDocs=44421)
               0.01818516 = queryNorm
             0.8733986 = fieldWeight in 3371, product of:
               2.4494898 = tf(freq=6.0), with freq of:
                 6.0 = termFreq=6.0
               5.7050157 = idf(docFreq=401, maxDocs=44421)
               0.0625 = fieldNorm(doc=3371)
       0.24 = coord(6/25)
   

2. Chen, Z.; Fu, B.: On the complexity of Rocchio's similarity-based relevance feedback algorithm (2007) 0.13

   0.1338672 = sum of:
     0.1338672 = product of:
       0.669336 = sum of:
         0.008763314 = weight(abstract_txt:from in 1578) [ClassicSimilarity], result of:
           0.008763314 = score(doc=1578,freq=1.0), product of:
             0.05081289 = queryWeight, product of:
               1.0126102 = boost
               2.759399 = idf(docFreq=7646, maxDocs=44421)
               0.01818516 = queryNorm
             0.17246243 = fieldWeight in 1578, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               2.759399 = idf(docFreq=7646, maxDocs=44421)
               0.0625 = fieldNorm(doc=1578)
         0.029544406 = weight(abstract_txt:applications in 1578) [ClassicSimilarity], result of:
           0.029544406 = score(doc=1578,freq=1.0), product of:
             0.09980402 = queryWeight, product of:
               1.158734 = boost
               4.7363873 = idf(docFreq=1058, maxDocs=44421)
               0.01818516 = queryNorm
             0.2960242 = fieldWeight in 1578, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               4.7363873 = idf(docFreq=1058, maxDocs=44421)
               0.0625 = fieldNorm(doc=1578)
         0.029884497 = weight(abstract_txt:query in 1578) [ClassicSimilarity], result of:
           0.029884497 = score(doc=1578,freq=1.0), product of:
             0.100568466 = queryWeight, product of:
               1.1631632 = boost
               4.754492 = idf(docFreq=1039, maxDocs=44421)
               0.01818516 = queryNorm
             0.29715574 = fieldWeight in 1578, 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=1578)
         0.13934879 = weight(abstract_txt:prove in 1578) [ClassicSimilarity], result of:
           0.13934879 = score(doc=1578,freq=2.0), product of:
             0.2227871 = queryWeight, product of:
               1.7312299 = boost
               7.0764947 = idf(docFreq=101, maxDocs=44421)
               0.01818516 = queryNorm
             0.62547964 = fieldWeight in 1578, product of:
               1.4142135 = tf(freq=2.0), with freq of:
                 2.0 = termFreq=2.0
               7.0764947 = idf(docFreq=101, maxDocs=44421)
               0.0625 = fieldNorm(doc=1578)
         0.461795 = weight(abstract_txt:algorithm in 1578) [ClassicSimilarity], result of:
           0.461795 = score(doc=1578,freq=5.0), product of:
             0.5791984 = queryWeight, product of:
               5.582817 = boost
               5.7050157 = idf(docFreq=401, maxDocs=44421)
               0.01818516 = queryNorm
             0.79730016 = fieldWeight in 1578, product of:
               2.236068 = tf(freq=5.0), with freq of:
                 5.0 = termFreq=5.0
               5.7050157 = idf(docFreq=401, maxDocs=44421)
               0.0625 = fieldNorm(doc=1578)
       0.2 = coord(5/25)
   

3. Chandrasekar, R.; Srinivas, B.: Automatic induction of rules for text simplification (1997) 0.13

   0.12602818 = sum of:
     0.12602818 = product of:
       0.6301409 = sum of:
         0.11519254 = weight(abstract_txt:induced in 3873) [ClassicSimilarity], result of:
           0.11519254 = score(doc=3873,freq=1.0), product of:
             0.14975338 = queryWeight, product of:
               1.0036517 = boost
               8.20496 = idf(docFreq=32, maxDocs=44421)
               0.01818516 = queryNorm
             0.769215 = fieldWeight in 3873, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               8.20496 = idf(docFreq=32, maxDocs=44421)
               0.09375 = fieldNorm(doc=3873)
         0.013144971 = weight(abstract_txt:from in 3873) [ClassicSimilarity], result of:
           0.013144971 = score(doc=3873,freq=1.0), product of:
             0.05081289 = queryWeight, product of:
               1.0126102 = boost
               2.759399 = idf(docFreq=7646, maxDocs=44421)
               0.01818516 = queryNorm
             0.25869364 = fieldWeight in 3873, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               2.759399 = idf(docFreq=7646, maxDocs=44421)
               0.09375 = fieldNorm(doc=3873)
         0.03452224 = weight(abstract_txt:structure in 3873) [ClassicSimilarity], result of:
           0.03452224 = score(doc=3873,freq=1.0), product of:
             0.08449604 = queryWeight, product of:
               1.0661736 = boost
               4.3580413 = idf(docFreq=1545, maxDocs=44421)
               0.01818516 = queryNorm
             0.40856636 = fieldWeight in 3873, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               4.3580413 = idf(docFreq=1545, maxDocs=44421)
               0.09375 = fieldNorm(doc=3873)
         0.02918397 = weight(abstract_txt:which in 3873) [ClassicSimilarity], result of:
           0.02918397 = score(doc=3873,freq=2.0), product of:
             0.07554399 = queryWeight, product of:
               1.4256886 = boost
               2.9137893 = idf(docFreq=6552, maxDocs=44421)
               0.01818516 = queryNorm
             0.38631755 = fieldWeight in 3873, product of:
               1.4142135 = tf(freq=2.0), with freq of:
                 2.0 = termFreq=2.0
               2.9137893 = idf(docFreq=6552, maxDocs=44421)
               0.09375 = fieldNorm(doc=3873)
         0.43809718 = weight(abstract_txt:algorithm in 3873) [ClassicSimilarity], result of:
           0.43809718 = score(doc=3873,freq=2.0), product of:
             0.5791984 = queryWeight, product of:
               5.582817 = boost
               5.7050157 = idf(docFreq=401, maxDocs=44421)
               0.01818516 = queryNorm
             0.7563853 = fieldWeight in 3873, product of:
               1.4142135 = tf(freq=2.0), with freq of:
                 2.0 = termFreq=2.0
               5.7050157 = idf(docFreq=401, maxDocs=44421)
               0.09375 = fieldNorm(doc=3873)
       0.2 = coord(5/25)
   

4. Marshall, B.; Chen, H.; Kaza, S.: Using importance flooding to identify interesting networks of criminal activity (2008) 0.12

   0.12387872 = sum of:
     0.12387872 = product of:
       0.442424 = sum of:
         0.008763314 = weight(abstract_txt:from in 3386) [ClassicSimilarity], result of:
           0.008763314 = score(doc=3386,freq=1.0), product of:
             0.05081289 = queryWeight, product of:
               1.0126102 = boost
               2.759399 = idf(docFreq=7646, maxDocs=44421)
               0.01818516 = queryNorm
             0.17246243 = fieldWeight in 3386, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               2.759399 = idf(docFreq=7646, maxDocs=44421)
               0.0625 = fieldNorm(doc=3386)
         0.022196215 = weight(abstract_txt:specific in 3386) [ClassicSimilarity], result of:
           0.022196215 = score(doc=3386,freq=1.0), product of:
             0.08248035 = queryWeight, product of:
               1.0533798 = boost
               4.305746 = idf(docFreq=1628, maxDocs=44421)
               0.01818516 = queryNorm
             0.26910913 = fieldWeight in 3386, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               4.305746 = idf(docFreq=1628, maxDocs=44421)
               0.0625 = fieldNorm(doc=3386)
         0.023014829 = weight(abstract_txt:structure in 3386) [ClassicSimilarity], result of:
           0.023014829 = score(doc=3386,freq=1.0), product of:
             0.08449604 = queryWeight, product of:
               1.0661736 = boost
               4.3580413 = idf(docFreq=1545, maxDocs=44421)
               0.01818516 = queryNorm
             0.27237758 = fieldWeight in 3386, 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=3386)
         0.029544406 = weight(abstract_txt:applications in 3386) [ClassicSimilarity], result of:
           0.029544406 = score(doc=3386,freq=1.0), product of:
             0.09980402 = queryWeight, product of:
               1.158734 = boost
               4.7363873 = idf(docFreq=1058, maxDocs=44421)
               0.01818516 = queryNorm
             0.2960242 = fieldWeight in 3386, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               4.7363873 = idf(docFreq=1058, maxDocs=44421)
               0.0625 = fieldNorm(doc=3386)
         0.04334475 = weight(abstract_txt:case in 3386) [ClassicSimilarity], result of:
           0.04334475 = score(doc=3386,freq=2.0), product of:
             0.10227721 = queryWeight, product of:
               1.1730031 = boost
               4.794713 = idf(docFreq=998, maxDocs=44421)
               0.01818516 = queryNorm
             0.42379674 = fieldWeight in 3386, product of:
               1.4142135 = tf(freq=2.0), with freq of:
                 2.0 = termFreq=2.0
               4.794713 = idf(docFreq=998, maxDocs=44421)
               0.0625 = fieldNorm(doc=3386)
         0.023495657 = weight(abstract_txt:study in 3386) [ClassicSimilarity], result of:
           0.023495657 = score(doc=3386,freq=2.0), product of:
             0.07783532 = queryWeight, product of:
               1.2532673 = boost
               3.415198 = idf(docFreq=3968, maxDocs=44421)
               0.01818516 = queryNorm
             0.3018637 = fieldWeight in 3386, product of:
               1.4142135 = tf(freq=2.0), with freq of:
                 2.0 = termFreq=2.0
               3.415198 = idf(docFreq=3968, maxDocs=44421)
               0.0625 = fieldNorm(doc=3386)
         0.29206482 = weight(abstract_txt:algorithm in 3386) [ClassicSimilarity], result of:
           0.29206482 = score(doc=3386,freq=2.0), product of:
             0.5791984 = queryWeight, product of:
               5.582817 = boost
               5.7050157 = idf(docFreq=401, maxDocs=44421)
               0.01818516 = queryNorm
             0.5042569 = fieldWeight in 3386, product of:
               1.4142135 = tf(freq=2.0), with freq of:
                 2.0 = termFreq=2.0
               5.7050157 = idf(docFreq=401, maxDocs=44421)
               0.0625 = fieldNorm(doc=3386)
       0.28 = coord(7/25)
   

5. Cathey, R.J.; Jensen, E.C.; Beitzel, S.M.; Frieder, O.; Grossman, D.: Exploiting parallelism to support scalable hierarchical clustering (2007) 0.12

   0.12231856 = sum of:
     0.12231856 = product of:
       0.61159277 = sum of:
         0.030649368 = weight(abstract_txt:case in 1448) [ClassicSimilarity], result of:
           0.030649368 = score(doc=1448,freq=1.0), product of:
             0.10227721 = queryWeight, product of:
               1.1730031 = boost
               4.794713 = idf(docFreq=998, maxDocs=44421)
               0.01818516 = queryNorm
             0.29966956 = fieldWeight in 1448, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               4.794713 = idf(docFreq=998, maxDocs=44421)
               0.0625 = fieldNorm(doc=1448)
         0.058200855 = weight(abstract_txt:version in 1448) [ClassicSimilarity], result of:
           0.058200855 = score(doc=1448,freq=2.0), product of:
             0.12448226 = queryWeight, product of:
               1.2940869 = boost
               5.2896495 = idf(docFreq=608, maxDocs=44421)
               0.01818516 = queryNorm
             0.46754336 = fieldWeight in 1448, product of:
               1.4142135 = tf(freq=2.0), with freq of:
                 2.0 = termFreq=2.0
               5.2896495 = idf(docFreq=608, maxDocs=44421)
               0.0625 = fieldNorm(doc=1448)
         0.013757454 = weight(abstract_txt:which in 1448) [ClassicSimilarity], result of:
           0.013757454 = score(doc=1448,freq=1.0), product of:
             0.07554399 = queryWeight, product of:
               1.4256886 = boost
               2.9137893 = idf(docFreq=6552, maxDocs=44421)
               0.01818516 = queryNorm
             0.18211183 = fieldWeight in 1448, 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=1448)
         0.047190085 = weight(abstract_txt:theoretical in 1448) [ClassicSimilarity], result of:
           0.047190085 = score(doc=1448,freq=1.0), product of:
             0.1561093 = queryWeight, product of:
               1.774883 = boost
               4.83662 = idf(docFreq=957, maxDocs=44421)
               0.01818516 = queryNorm
             0.30228874 = fieldWeight in 1448, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               4.83662 = idf(docFreq=957, maxDocs=44421)
               0.0625 = fieldNorm(doc=1448)
         0.461795 = weight(abstract_txt:algorithm in 1448) [ClassicSimilarity], result of:
           0.461795 = score(doc=1448,freq=5.0), product of:
             0.5791984 = queryWeight, product of:
               5.582817 = boost
               5.7050157 = idf(docFreq=401, maxDocs=44421)
               0.01818516 = queryNorm
             0.79730016 = fieldWeight in 1448, product of:
               2.236068 = tf(freq=5.0), with freq of:
                 5.0 = termFreq=5.0
               5.7050157 = idf(docFreq=401, maxDocs=44421)
               0.0625 = fieldNorm(doc=1448)
       0.2 = coord(5/25)