Michael Brinkmeier
Abstract
PageRank, one part of the search engine Google, is one of the most prominent link-based rankings of documents in the World Wide Web. Usually it is described as a Markov chain modeling a specific random surfer. In this article, an alternative representation as a power series is given. Nonetheless, it is possible to interpret the values as probabilities in a random surfer setting, differing from the usual one.Using the new description we restate and extend some results concerning the convergence of the standard iteration used for PageRank. Furthermore we take a closer look at sinks and sources, leading to some suggestions for faster implementations.
- Arasu, A., Novak, J., Tomkins, A., and Tomlin, J. 2001. Pagerank computation and the structure of the Web: Experiments and algorithms. citeseer.ist.psu.edu/arasu02pagerank.html.Google Scholar
- Bianchini, M., Gori, M., and Scarselli, F. 2005. Inside PageRank. ACM Trans. Internet Tech. 5, 92--128. Google Scholar
- Brin, S. and Page, L. 1998. The anatomy of a large-scale hypertextual Web search engine. In Proceedings of the 7th World Wide Web Conference (WWW7). Google Scholar
- Brin, S., Page, L., Motwani, R., and Winograd, T. 1999. The PageRank citation ranking: Bringing order to the Web. Tech. rep. 1999-66, Stanford Digital Library Technologies Project. http://dbpubs.stanford.edu:8090/pub/1999-66.Google Scholar
- Brinkmeier, M. 2005. Distributed calculation of Pagerank using strongly connected components. In Proceedings of Innovative Internet Computing Systems (IICS). Lecture Notes in Computer Science, vol. 3908. A. Bui, M. Bui, T. Böhme, and H. Unger, Eds. Springer, 29--40. Google Scholar
- Fogaras, D. 2003. Where to start browsing the Web? In Proceedings of Innovative Internet Computing Systems (IICS). Lecture Notes in Computer Science, vol. 2877. T. Böhme, G. Heyer, and H. Unger, Eds. Springer, 65--79.Google Scholar
- Haveliwala, T. and Kamvar, S. 2003. The second eigenvalue of the Google matrix. Tech. rep. 2003-20, Stanford University. http://dbpubs.stanford.edu/pub/2003--20.Google Scholar
- Haveliwala, T., Kamvar, S., and Jeh, G. 2003. An analytical comparison of approaches to personalizing pagerank. Tech. rep., Stanford University.Google Scholar
- Haveliwala, T. H. 2002. Topic-sensitive pagerank. In Proceedings of the 11th WWW Conference (WWW11). 517--526. Google Scholar
- Haveliwala, T. H. 2003. Topic-sensitive pagerank: A context-sensitive ranking algorithm for Web search. IEEE Trans. Knowl. Data Eng. 15, 4, 784--796. Google Scholar
- Jeh, G. and Widom, J. 2002. SimRank : A measure of structural-context similarity. In Proceedings of the 8th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Google Scholar
- Jeh, G. and Widom, J. 2003. Scaling personalized Web search. In Proceedings of the 12th International WWW Conference. Google Scholar
- Kamvar, S., Haveliwala, T., and Golub, G. 2003. Adaptive methods for the computation of Pagerank. Tech. rep., Stanford University.Google Scholar
- Kamvar, S. D., Haveliwala, T. H., Manning, C. D., and Golub, G. H. 2003a. Exploiting the block structure of the web for computing pagerank. Tech. Rep. 2003-17, Stanford University. http://dbpubs.stanford.edu:8090/pub/2003--17.Google Scholar
- Kamvar, S. D., Haveliwala, T. H., Manning, C. D., and Golub, G. H. 2003b. Extrapolation methods for accelerating Pagerank computations. In WWW. 261--270. Google Scholar
- Webgraph. Webgraph. University of Milano, http://webgraph.dsi.unimi.it/.Google Scholar
Index Terms
- PageRank revisited
Recommendations
Topic-sensitive PageRank
WWW '02: Proceedings of the 11th international conference on World Wide WebIn the original PageRank algorithm for improving the ranking of search-query results, a single PageRank vector is computed, using the link structure of the Web, to capture the relative "importance" of Web pages, independent of any particular search ...
Beyond PageRank: machine learning for static ranking
WWW '06: Proceedings of the 15th international conference on World Wide WebSince the publication of Brin and Page's paper on PageRank, many in the Web community have depended on PageRank for the static (query-independent) ordering of Web pages. We show that we can significantly outperform PageRank using features that are ...
Inside PageRank
Although the interest of a Web page is strictly related to its content and to the subjective readers' cultural background, a measure of the page authority can be provided that only depends on the topological structure of the Web. PageRank is a ...
Comments