The DOI matches its Crossref record; 48 of the 48 references it cites were found in a registry or an index.
Link analysis ranking: algorithms, theory, and experiments
Abstract
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 Link Analysis Ranking, where hyperlink structures are used to determine the relative authority 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.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Maximum Likelihood from Incomplete Data Via the EM Algorithm
Dempster, A. P., Laird, N. M., & Rubin, D. B. (1977) · Journal of the Royal Statistical Society Series B: Statistical Methodology · doi:10.1111/j.2517-6161.1977.tb01600.x · Cited by 50,444
The anatomy of a large-scale hypertextual Web search engine
Brin, S., & Page, L. (1998) · Computer Networks and ISDN Systems · doi:10.1016/s0169-7552(98)00110-x · Cited by 16,004
(1999) · Cited by 12,854
Proceedings of the 24th international conference on Machine learning
(2007) · doi:10.1145/1273496 · Cited by 11,630
Authoritative sources in a hyperlinked environment
Kleinberg, J. M. (1999) · Journal of the ACM · doi:10.1145/324133.324140 · Cited by 8,959
Algorithms for Clustering Data
Sarle, W. S. (1990) · Technometrics · doi:10.1080/00401706.1990.10484648 · Cited by 7,865
Markov Chain Monte Carlo in Practice
(1995) · Chapman & Hall/CRC eBooks · doi:10.1201/b14835 · Cited by 7,757
Kendall, M. G. (1957) · Biometrika · doi:10.2307/2333282 · Cited by 6,383
Divergence measures based on the Shannon entropy
Lin, J. (1991) · IEEE Transactions on Information Theory · doi:10.1109/18.61115 · Cited by 5,140
Moran, P. A. P., & Kendall, M. G. (1973) · International Statistical Review / Revue Internationale de Statistique · doi:10.2307/1402637 · Cited by 4,054
A New Status Index Derived from Sociometric Analysis
Katz, L. (1953) · Psychometrika · doi:10.1007/bf02289026 · Cited by 3,866
Markov Chains for Exploring Posterior Distributions
Tierney, L. (1994) · The Annals of Statistics · doi:10.1214/aos/1176325750 · Cited by 3,452
The information bottleneck method
Tishby, N., Pereira, F. C., & Bialek, W. (2000) · arXiv · doi:10.48550/arxiv.physics/0004057 · Cited by 2,626
Bernardo, J. M., & Smith, A. F. M. (1994) · Wiley Series in Probability and Statistics · doi:10.1002/9780470316870 · Cited by 2,178
Probabilistic Latent Semantic Analysis
Hofmann, T. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1301.6705 · Cited by 2,047
Authoritative sources in a hyperlinked environment
Kleinberg, J. M. (1998) · Symposium on Discrete Algorithms · doi:10.5555/314613.315045 · Cited by 1,814
Rank aggregation methods for the Web
Dwork, C., Kumar, R., Naor, M., & Sivakumar, D. (2001) · Proceedings of the 10th international conference on World Wide Web · doi:10.1145/371920.372165 · Cited by 1,793
Bayesian computation via the Gibbs sampler and related Markov chain Monte Carlo methods
Smith, A. F. M., & Roberts, G. O. (1993) · Journal of the Royal Statistical Society Series B: Statistical Methodology · doi:10.1111/j.2517-6161.1993.tb01466.x · Cited by 1,713
Self-citationHaveliwala, T. H. (2002) · Proceedings of the 11th international conference on World Wide Web · doi:10.1145/511446.511513 · Cited by 1,567
Scaling personalized web search
Jeh, G., & Widom, J. (2003) · Proceedings of the twelfth international conference on World Wide Web - WWW '03 · doi:10.1145/775152.775191 · Cited by 1,195
Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI 2017)
Amendola, G., Ricca, F., & Truszczyński, M. (2017) · International Joint Conference on Artificial Intelligence · Cited by 1,179
Govindarajulu, Z., Kendall, M., & Gibbons, J. D. (1992) · Technometrics · doi:10.2307/1269571 · Cited by 1,130
Inferring Web communities from link topology
Gibson, D., Kleinberg, J., & Raghavan, P. (1998) · Proceedings of the ninth ACM conference on Hypertext and hypermedia : links, objects, time and space---structure in hypermedia systems links, objects, time and space---structure in hypermedia systems - HYPERTEXT '98 · doi:10.1145/276627.276652 · Cited by 768
(2003) · doi:10.5555/644108.644113 · Cited by 762
Automatic resource compilation by analyzing hyperlink structure and associated text
Chakrabarti, S., Dom, B., Raghavan, P., Rajagopalan, S., Gibson, D., & Kleinberg, J. (1998) · Computer Networks and ISDN Systems · doi:10.1016/s0169-7552(98)00087-7 · Cited by 697
Improved Algorithms for Topic Distillation in a Hyperlinked Environment
Bharat, K., & Henzinger, M. R. (2017) · ACM SIGIR Forum · doi:10.1145/3130348.3130367 · Cited by 676
Spearman's Footrule as a Measure of Disarray
Diaconis, P., & Graham, R. L. (1977) · Journal of the Royal Statistical Society Series B: Statistical Methodology · doi:10.1111/j.2517-6161.1977.tb01624.x · Cited by 640
Real life information retrieval: a study of user queries on the Web
Jansen, B. J., Spink, A., Bateman, J., & Saracevic, T. (1998) · ACM SIGIR Forum · doi:10.1145/281250.281253 · Cited by 622
The stochastic approach for link-structure analysis (SALSA) and the TKC effect
Lempel, R., & Moran, S. (2000) · Computer Networks · doi:10.1016/s1389-1286(00)00034-7 · Cited by 481
Improved algorithms for topic distillation in a hyperlinked environment
Bharat, K., & Henzinger, M. R. (1998) · Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval · doi:10.1145/290941.290972 · Cited by 444
(1999) · Cited by 397
The Intelligent surfer: Probabilistic Combination of Link and Content Information in PageRank
Richardson, M., & Domingos, P. (2001) · Cited by 356
Azar, Y., Fiat, A., Karlin, A., McSherry, F., & Saia, J. (2001) · Proceedings of the thirty-third annual ACM symposium on Theory of computing · doi:10.1145/380752.380859 · Cited by 289
Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA)
(2021) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9781611976465 · Cited by 288
Stable algorithms for link analysis
Ng, A. Y., Zheng, A. X., & Jordan, M. I. (2001) · Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval · doi:10.1145/383952.384003 · Cited by 286
Learning to Probabilistically Identify Authoritative Documents
Cohn, D. A., & Chang, H. (2000) · International Conference on Machine Learning · Cited by 269
LIMBO: Scalable Clustering of Categorical Data
Andritsos, P., Tsaparas, P., Miller, R. J., & Sevcik, K. C. (2004) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-24741-8_9 · Cited by 261
Self-citationFinding authorities and hubs from link structures on the World Wide Web
Borodin, A., Roberts, G. O., Rosenthal, J. S., & Tsaparas, P. (2001) · Proceedings of the 10th international conference on World Wide Web · doi:10.1145/371920.372096 · Cited by 230
Self-citationComparing and aggregating rankings with ties
Fagin, R., Kumar, R., Mahdian, M., Sivakumar, D., & Vee, E. (2004) · ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS) · doi:10.1145/1055558.1055568 · Cited by 230
Link Analysis, Eigenvectors and Stability
Ng, A. Y., Zheng, A. X., & Jordan, M. I. (2001) · Cited by 206
The quest for correct information on the Web: hyper search engines
Marchiori, M. (1997) · Computer Networks and ISDN Systems · doi:10.1016/s0169-7552(97)00036-6 · Cited by 191
Analysis of a Very Large AltaVista Query Log
Silverstein, C. D., Henzinger, M. R., Marais, H., & Moricz, M. (1998) · Cited by 169
Recognizing Nepotistic Links on the Web
Davison, B. D. (2000) · Cited by 152
Markov‐chain monte carlo: Some practical implications of theoretical results
Roberts, G. O., & Rosenthal, J. S. (1998) · Canadian Journal of Statistics · doi:10.2307/3315667 · Cited by 151
Self-citationWhat is this page known for? Computing Web page reputations
Rafiei, D., & Mendelzon, A. O. (2000) · Computer Networks · doi:10.1016/s1389-1286(00)00078-5 · Cited by 126
A new paradigm for ranking pages on the world wide web
Tomlin, J. A. (2003) · International World Wide Web Conference (WWW) · doi:10.1145/775152.775202 · Cited by 88
Bharat, K. A., & Mihaila, G. A. (2001) · International World Wide Web Conference (WWW) · doi:10.1145/371920.372162 · Cited by 44
Borodin, A., & Tsaparas, P. (2004) · Cited by 23
Self-citation
Cited by
Multiagent systems: algorithmic, game-theoretic, and logical foundations
(2009) · Choice Reviews Online · doi:10.5860/choice.46-5662 · Cited by 1,756
Expertise networks in online communities: structure and algorithms
Zhang, J., Ackerman, M. S., & Adamic, L. (2007) · Proceedings of the 16th international conference on World Wide Web · doi:10.1145/1242572.1242603 · Cited by 789
Truth Discovery with Multiple Conflicting Information Providers on the Web
Yin, X., Han, J., & Yu, P. S. (2008) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2007.190745 · Cited by 648
A Survey on PageRank Computing
Berkhin, P. (2005) · Internet Mathematics · doi:10.1080/15427951.2005.10129098 · Cited by 474
Boldi, P., & Vigna, S. (2014) · Internet Mathematics · doi:10.1080/15427951.2013.865686 · Cited by 419
Metadata
- Authors
- Borodin, A., Roberts, G. O., Rosenthal, J. S., & Tsaparas, P.
- Venue
- ACM Transactions on Internet Technology
- Published
- 2005-02
- Volume
- 5
- Issue
- 1
- Pages
- 231-297
- ISSN
- 1533-5399 (ISSN-L)
- 1557-6051
- OpenAlex
- W2111289574
- Cited by
- 308
- References
- 48
- FWCI
- 68.66
- Type
- journal article
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.