{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,22]],"date-time":"2026-06-22T18:04:53Z","timestamp":1782151493617,"version":"3.54.5"},"reference-count":52,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2005,2,1]],"date-time":"2005-02-01T00:00:00Z","timestamp":1107216000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Internet Technol."],"published-print":{"date-parts":[[2005,2]]},"abstract":"<jats:p>The explosive growth and the widespread accessibility of the Web has led to a surge of research activity in the area of information retrieval on the World Wide Web. The seminal papers of Kleinberg [1998, 1999] and Brin and Page [1998] introduced<jats:italic>Link Analysis Ranking<\/jats:italic>, where hyperlink structures are used to determine the relative<jats:italic>authority<\/jats:italic>of a Web page and produce improved algorithms for the ranking of Web search results. In this article we work within the hubs and authorities framework defined by Kleinberg and we propose new families of algorithms. Two of the algorithms we propose use a Bayesian approach, as opposed to the usual algebraic and graph theoretic approaches. We also introduce a theoretical framework for the study of Link Analysis Ranking algorithms. The framework allows for the definition of specific properties of Link Analysis Ranking algorithms, as well as for comparing different algorithms. We study the properties of the algorithms that we define, and we provide an axiomatic characterization of the INDEGREE heuristic which ranks each node according to the number of incoming links. We conclude the article with an extensive experimental evaluation. We study the quality of the algorithms, and we examine how different structures in the graphs affect their performance.<\/jats:p>","DOI":"10.1145\/1052934.1052942","type":"journal-article","created":{"date-parts":[[2005,8,3]],"date-time":"2005-08-03T08:30:55Z","timestamp":1123057855000},"page":"231-297","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":200,"title":["Link analysis ranking: algorithms, theory, and experiments"],"prefix":"10.1145","volume":"5","author":[{"given":"Allan","family":"Borodin","sequence":"first","affiliation":[{"name":"University of Toronto, Toronto, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Gareth O.","family":"Roberts","sequence":"additional","affiliation":[{"name":"Lancaster University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jeffrey S.","family":"Rosenthal","sequence":"additional","affiliation":[{"name":"University of Toronto, Toronto, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Panayiotis","family":"Tsaparas","sequence":"additional","affiliation":[{"name":"University of Helsinki, Helsinki, Finland"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2005,2]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Proceedings of the 42nd Foundation of Computer Science (FOCS","author":"Achlioptas D.","year":"2001","unstructured":"Achlioptas , D. , Fiat , A. , Karlin , A. , and McSherry , F. 2001 . Web search through hub synthesis . In Proceedings of the 42nd Foundation of Computer Science (FOCS 2001). Las Vegas, NY. Achlioptas, D., Fiat, A., Karlin, A., and McSherry, F. 2001. Web search through hub synthesis. In Proceedings of the 42nd Foundation of Computer Science (FOCS 2001). Las Vegas, NY."},{"key":"e_1_2_1_2_1","volume-title":"LIMBO: Scalable clustering of categorical data. Submitted for publication.","author":"Andritsos P.","year":"2003","unstructured":"Andritsos , P. , Tsaparas , P. , Miller , R. , and Sevcik , K . 2003 . LIMBO: Scalable clustering of categorical data. Submitted for publication. Andritsos, P., Tsaparas, P., Miller, R., and Sevcik, K. 2003. LIMBO: Scalable clustering of categorical data. Submitted for publication."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/380752.380859"},{"key":"e_1_2_1_4_1","doi-asserted-by":"crossref","unstructured":"Bernardo J. and Smith A. 1994. Bayesian Theory. John Wiley & Sons Chichester England. Bernardo J. and Smith A. 1994. Bayesian Theory. John Wiley & Sons Chichester England.","DOI":"10.1002\/9780470316870"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/290941.290972"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/371920.372162"},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the 11th International Word Wide Web Conference (WWW","author":"Bianchini M.","year":"2002","unstructured":"Bianchini , M. , Gori , M. , and Scarselli , F . 2002. PageRank: A circuital analysis . In Proceedings of the 11th International Word Wide Web Conference (WWW 2002 ). Poster Session. Hawai. Bianchini, M., Gori, M., and Scarselli, F. 2002. PageRank: A circuital analysis. In Proceedings of the 11th International Word Wide Web Conference (WWW 2002). Poster Session. Hawai."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/371920.372096"},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of the 7th International World Wide Web Conference","author":"Brin S.","unstructured":"Brin , S. and Page , L . 1998. The anatomy of a large-scale hypertextual Web search engine . In Proceedings of the 7th International World Wide Web Conference . Brisbane, Australia. Brin, S. and Page, L. 1998. The anatomy of a large-scale hypertextual Web search engine. In Proceedings of the 7th International World Wide Web Conference. Brisbane, Australia."},{"key":"e_1_2_1_10_1","volume-title":"Advanced School and Workshop on Models and Algorithms for the World Wide Web","author":"Broder A.","year":"2002","unstructured":"Broder , A. 2002 . Web searching technology overview . In Advanced School and Workshop on Models and Algorithms for the World Wide Web . Udine, Italy. Broder, A. 2002. Web searching technology overview. In Advanced School and Workshop on Models and Algorithms for the World Wide Web. Udine, Italy."},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the 7th International World Wide Web Conference.","author":"Chakrabarti S.","unstructured":"Chakrabarti , S. , Dom , B. , Gibson , D. , Kleinberg , J. , Raghavan , P. , and Rajagopalan , S . 1998. Automatic resource compilation by analysing hyperlink structure and associated text . In Proceedings of the 7th International World Wide Web Conference. Chakrabarti, S., Dom, B., Gibson, D., Kleinberg, J., Raghavan, P., and Rajagopalan, S. 1998. Automatic resource compilation by analysing hyperlink structure and associated text. In Proceedings of the 7th International World Wide Web Conference."},{"key":"e_1_2_1_12_1","volume-title":"Workshop on Algorithms for the Web","author":"Chien S.","unstructured":"Chien , S. , Dwork , C. , Kumar , R. , Simon , D. , and Sivakumar , D . 2002. Towards exploiting link evolution . In Workshop on Algorithms for the Web . Vancuver, Canada. Chien, S., Dwork, C., Kumar, R., Simon, D., and Sivakumar, D. 2002. Towards exploiting link evolution. In Workshop on Algorithms for the Web. Vancuver, Canada."},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of the 17th International Conference on Machine Learning","author":"Cohn D.","unstructured":"Cohn , D. and Chang , H . 2000. Learning to probabilistically identify authoritative documents . In Proceedings of the 17th International Conference on Machine Learning . Stanford University, 167--174. Cohn, D. and Chang, H. 2000. Learning to probabilistically identify authoritative documents. In Proceedings of the 17th International Conference on Machine Learning. Stanford University, 167--174."},{"key":"e_1_2_1_14_1","volume-title":"AAAI-2000 Workshop on Artificial Intelligence for Web Search. AAAI Press","author":"Davison B.","year":"2000","unstructured":"Davison , B. 2000 . Recognizing nepotistic links on the web . In AAAI-2000 Workshop on Artificial Intelligence for Web Search. AAAI Press , Austin, TX. Davison, B. 2000. Recognizing nepotistic links on the web. In AAAI-2000 Workshop on Artificial Intelligence for Web Search. AAAI Press, Austin, TX."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.2517-6161.1977.tb01600.x"},{"key":"e_1_2_1_16_1","doi-asserted-by":"crossref","first-page":"262","DOI":"10.1111\/j.2517-6161.1977.tb01624.x","article-title":"Spearman's footrule as a measure of disarray","volume":"39","author":"Diaconis P.","year":"1977","unstructured":"Diaconis , P. and Graham , R. 1977 . Spearman's footrule as a measure of disarray . J. Roy. Statist. Soc. 39 , 2, 262 -- 268 . Diaconis, P. and Graham, R. 1977. Spearman's footrule as a measure of disarray. J. Roy. Statist. Soc. 39, 2, 262--268.","journal-title":"J. Roy. Statist. Soc."},{"key":"e_1_2_1_17_1","volume-title":"ACM-SIAM Symposium on Discrete Algorithms (SODA).","author":"Drineas P.","unstructured":"Drineas , P. , Frieze , A. , Kannan , R. , Vempala , S. , and Vinay , V . 1999. Clustering in large graphs and matrices . In ACM-SIAM Symposium on Discrete Algorithms (SODA). Drineas, P., Frieze, A., Kannan, R., Vempala, S., and Vinay, V. 1999. Clustering in large graphs and matrices. In ACM-SIAM Symposium on Discrete Algorithms (SODA)."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/371920.372165"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1055558.1055568"},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA).","author":"Fagin R.","unstructured":"Fagin , R. , Kumar , R. , and Sivakumar , D . 2003. Comparing top k lists . In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA). Fagin, R., Kumar, R., and Sivakumar, D. 2003. Comparing top k lists. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA)."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/276627.276652"},{"key":"e_1_2_1_22_1","doi-asserted-by":"crossref","unstructured":"Gilks W. Richardson S. and Spiegelhalter D. 1996. Markov Chain Monte Carlo in practice. Chapman and Hall London. Gilks W. Richardson S. and Spiegelhalter D. 1996. Markov Chain Monte Carlo in practice. Chapman and Hall London.","DOI":"10.1201\/b14835"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/511446.511513"},{"key":"e_1_2_1_24_1","volume-title":"Proceedings of Uncertainty in Artificial Intelligence, UAI'99","author":"Hofmann T.","year":"1999","unstructured":"Hofmann , T. 1999 . Probabilistic latent semantic analysis . In Proceedings of Uncertainty in Artificial Intelligence, UAI'99 . Stockholm, Sweden. Hofmann, T. 1999. Probabilistic latent semantic analysis. In Proceedings of Uncertainty in Artificial Intelligence, UAI'99. Stockholm, Sweden."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/345508.345660"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/281250.281253"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/775152.775191"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02289026"},{"key":"e_1_2_1_29_1","volume-title":"Rank Correlation Methods","author":"Kendall M. G.","unstructured":"Kendall , M. G. 1970. Rank Correlation Methods . Griffin , London, UK . Kendall, M. G. 1970. Rank Correlation Methods. Griffin, London, UK."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.5555\/314613.315045"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/324133.324140"},{"key":"e_1_2_1_32_1","volume-title":"Proceedings of the 9th International Computing and Combinatorics Conference.","author":"Lee H. C.","unstructured":"Lee , H. C. and Borodin , A . 2003. Perturbation of the hyperlinked environment . In Proceedings of the 9th International Computing and Combinatorics Conference. Lee, H. C. and Borodin, A. 2003. Perturbation of the hyperlinked environment. In Proceedings of the 9th International Computing and Combinatorics Conference."},{"key":"e_1_2_1_33_1","volume-title":"Proceedings of the 9th International World Wide Web Conference.","author":"Lempel R.","unstructured":"Lempel , R. and Moran , S . 2000. The stochastic approach for link-structure analysis (SALSA) and the TKC effect . In Proceedings of the 9th International World Wide Web Conference. Lempel, R. and Moran, S. 2000. The stochastic approach for link-structure analysis (SALSA) and the TKC effect. In Proceedings of the 9th International World Wide Web Conference."},{"key":"e_1_2_1_34_1","volume-title":"Tech. Rep. CS-2001-22. Technion---Israel Institute of Technology.","author":"Lempel R.","year":"2001","unstructured":"Lempel , R. and Moran , S . 2001 . Rank stability and rank similarity of Web link-based ranking algorithms. Tech. Rep. CS-2001-22. Technion---Israel Institute of Technology. Lempel, R. and Moran, S. 2001. Rank stability and rank similarity of Web link-based ranking algorithms. Tech. Rep. CS-2001-22. Technion---Israel Institute of Technology."},{"key":"e_1_2_1_35_1","volume-title":"2nd Workshop on Algorithms and Models for the Web-Graph (WAW2003)","author":"Lempel R.","unstructured":"Lempel , R. and Moran , S . 2003. Rank stability and rank similarity of Web link-based ranking algorithms . In 2nd Workshop on Algorithms and Models for the Web-Graph (WAW2003) . Budapest, Hungary. Lempel, R. and Moran, S. 2003. Rank stability and rank similarity of Web link-based ranking algorithms. In 2nd Workshop on Algorithms and Models for the Web-Graph (WAW2003). Budapest, Hungary."},{"key":"e_1_2_1_36_1","first-page":"145","article-title":"Divergence measures based on the Shannon entropy","volume":"37","author":"Lin J.","year":"1991","unstructured":"Lin , J. 1991 . Divergence measures based on the Shannon entropy . Mach. Learn. 37 , 1, 145 -- 151 . Lin, J. 1991. Divergence measures based on the Shannon entropy. Mach. Learn. 37, 1, 145--151.","journal-title":"Mach. Learn."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0169-7552(97)00036-6"},{"key":"e_1_2_1_38_1","first-page":"9","article-title":"What do the neighbours think? Computing Web page reputations","volume":"23","author":"Mendelzon A.","year":"2000","unstructured":"Mendelzon , A. and Rafiei , D. 2000 . What do the neighbours think? Computing Web page reputations . IEEE Data Eng. Bull. 23 , 3, 9 -- 16 . Mendelzon, A. and Rafiei, D. 2000. What do the neighbours think? Computing Web page reputations. IEEE Data Eng. Bull. 23, 3, 9--16.","journal-title":"IEEE Data Eng. Bull."},{"key":"e_1_2_1_39_1","volume-title":"Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI)","author":"Ng A. Y.","unstructured":"Ng , A. Y. , Zheng , A. X. , and Jordan , M. I . 2001a. Link analysis, eigenvectors, and stability . In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI) . Seattle, Washington. Ng, A. Y., Zheng, A. X., and Jordan, M. I. 2001a. Link analysis, eigenvectors, and stability. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI). Seattle, Washington."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/383952.384003"},{"key":"e_1_2_1_41_1","unstructured":"Page L. Brin S. Motwani R. and Winograd T. 1998. The PageRank citation ranking: Bringing order to the web. Tech. rep. Stanford Digital Library Technologies Project. Page L. Brin S. Motwani R. and Winograd T. 1998. The PageRank citation ranking: Bringing order to the web. Tech. rep. Stanford Digital Library Technologies Project."},{"key":"e_1_2_1_42_1","volume-title":"Proceedings of the 9th International World Wide Web Conference","author":"Rafiei D.","unstructured":"Rafiei , D. and Mendelzon , A . 2000. What is this page known for? Computing Web page reputations . In Proceedings of the 9th International World Wide Web Conference . Amsterdam, Netherlands. Rafiei, D. and Mendelzon, A. 2000. What is this page known for? Computing Web page reputations. In Proceedings of the 9th International World Wide Web Conference. Amsterdam, Netherlands."},{"key":"e_1_2_1_43_1","unstructured":"Richardson M. and Domingos P. 2002. The intelligent surfer: Probabilistic combination of link and content information in PageRank. In Advances in Neural Information Processing Systems (NIPS) 14. Richardson M. and Domingos P. 2002. The intelligent surfer: Probabilistic combination of link and content information in PageRank. In Advances in Neural Information Processing Systems (NIPS) 14."},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.2307\/3315667"},{"key":"e_1_2_1_45_1","first-page":"199","article-title":"Downweighting tightly knit communities in World Wide Web rankings","volume":"3","author":"Roberts G. O.","year":"2003","unstructured":"Roberts , G. O. and Rosenthal , J. S. 2003 . Downweighting tightly knit communities in World Wide Web rankings . Adv. Appl. Statist. 3 , 199 -- 216 . Roberts, G. O. and Rosenthal, J. S. 2003. Downweighting tightly knit communities in World Wide Web rankings. Adv. Appl. Statist. 3, 199--216.","journal-title":"Adv. Appl. Statist."},{"key":"e_1_2_1_46_1","first-page":"1998","article-title":"Analysis of a very large AltaVista query log","author":"Silverstein C.","year":"1998","unstructured":"Silverstein , C. , Henzinger , M. , Marais , H. , and Moricz , M. 1998 . Analysis of a very large AltaVista query log . Tech. Rep. 1998 - 1014 . Digital SRC. Silverstein, C., Henzinger, M., Marais, H., and Moricz, M. 1998. Analysis of a very large AltaVista query log. Tech. Rep. 1998-014. Digital SRC.","journal-title":"Tech. Rep."},{"key":"e_1_2_1_47_1","unstructured":"Slonim N. and Tishby N. 1999. Agglomerative Information Bottleneck. In Advances in Neural Information Processing Systems (NIPS). Breckenridge CO. Slonim N. and Tishby N. 1999. Agglomerative Information Bottleneck. In Advances in Neural Information Processing Systems (NIPS). Breckenridge CO."},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.2517-6161.1993.tb01466.x"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1214\/aos\/1176325750"},{"key":"e_1_2_1_50_1","volume-title":"37th Annual Allerton Conference on Communication, Control and Computing. Urban-Champaign, IL.","author":"Tishby N.","unstructured":"Tishby , N. , Pereira , F. C. , and Bialek , W . 1999. The Information Bottleneck method . In 37th Annual Allerton Conference on Communication, Control and Computing. Urban-Champaign, IL. Tishby, N., Pereira, F. C., and Bialek, W. 1999. The Information Bottleneck method. In 37th Annual Allerton Conference on Communication, Control and Computing. Urban-Champaign, IL."},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/775152.775202"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/1055558.1055569"}],"container-title":["ACM Transactions on Internet Technology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1052934.1052942","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1052934.1052942","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T22:43:28Z","timestamp":1750286608000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1052934.1052942"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,2]]},"references-count":52,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2005,2]]}},"alternative-id":["10.1145\/1052934.1052942"],"URL":"https:\/\/doi.org\/10.1145\/1052934.1052942","relation":{},"ISSN":["1533-5399","1557-6051"],"issn-type":[{"value":"1533-5399","type":"print"},{"value":"1557-6051","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,2]]},"assertion":[{"value":"2005-02-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}