Abstract
Several link-based algorithms, such as PageRank [7], HITS [4] and SALSA [5], have been developed to evaluate the popularity of web pages. These algorithms can be interpreted as computing the steady-state distribution of various Markov processes over web pages. The PageRank and HITS algorithms tend to over-rank tightly interlinked collections of pages, such as well-organized message boards. We show that this effect can be alleviated using a number of modifications to the underlying Markov process. Specifically, rather than weight all outlinks from a given page equally, greater weight is given to links between pages that are, in other respects, further off in the web, and less weight is given to links between pages that are nearby. We have experimented with a number of variants of this idea, using a number of different measures of ”distance” in the Web, and a number of different weighting schemes. We show that these revised algorithms often do avoid the over-ranking problem and give better overall rankings.
This work is supported by NSF grant #IIS-0097537. There is an extended version of this paper as NYU computer science dept. technical report TR2003-846, online at http://csdocs.cs.nyu.edu/Dienst/UI/2.0/Describe/ncstrl.nyu cs/TR2003-846.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Albert, R., Jeong, H., Barabasi, A.: Diameter of the world-wide-web. Nature 401, 130–131 (1999)
Borodin, A., Roberts, G., Rosenthal, J., Tsaparas, P.: Finding authorities and hubs from link structure on the world wide web. In: Proc. 10th World Wide Web Conference (2001)
Broder, A., Kumar, R., Maghoul, F., Raghavan, P., Rajagopalan, S., Stata, R., Tomkins, A., Wiener, J.: Graph structure in the web. Computer Networks and ISDN Systems 30, 309–320 (2000)
Kleinberg, L.: Authoritative sources in a hyperlinked environment. In: Proc. 9th ACM-SIAM Symposium on Discrete Algorithms (1998)
Lempel, R., Moran, S.: The stochastic approach for link-structure analysis (salsa) and the tkc effect. In: Proc. 9th International World Wide Web Conference (2000)
Ng, A., Zheng, A., Jordan, M.: Stable algorithms for link analysis. In: Proc. ACM SIGIR (2001)
Page, L., Brin, S., Motwani, R., Winograd, T.: The pagerank citation ranking: bringing order to the web. Stanford Digital Library working paper, 1997-0072 (1997)
Wang, Z.: Improved link-based algorithm for ranking web pages. NYU Computer Science Dept. technical report TR2003-846, extended version (2003)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Wang, Z. (2004). Improved Link-Based Algorithms for Ranking Web Pages. In: Li, Q., Wang, G., Feng, L. (eds) Advances in Web-Age Information Management. WAIM 2004. Lecture Notes in Computer Science, vol 3129. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-27772-9_30
Download citation
DOI: https://doi.org/10.1007/978-3-540-27772-9_30
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-22418-1
Online ISBN: 978-3-540-27772-9
eBook Packages: Springer Book Archive