Abstract
PageRank is a key element in the success of search engines, allowing to rank the most important hits in the top screen of results. One key aspect that distinguishes PageRank from other prestige measures such as in-degree is its global nature. From the information provider perspective, this makes it difficult or impossible to predict how their pages will be ranked. Consequently a market has emerged for the optimization of search engine results. Here we study the accuracy with which PageRank can be approximated by in-degree, a local measure made freely available by search engines. Theoretical and empirical analyses lead to conclude that given the weak degree correlations in the Web link graph, the approximation can be relatively accurate, giving service and information providers an effective new marketing tool.
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
Brin, S., Page, L.: The anatomy of a large-scale hypertextual Web search engine. Computer Networks 30(1–7), 107–117 (1998)
Sullivan, D.: Nielsen//netratings search engine ratings (August (2005), http://searchenginewatch.com/reports/article.php/2156451
Amento, B., Terveen, L., Hill, W.: Does “authority” mean quality? Predicting expert quality ratings of Web documents. In: Proc. 23rd ACM SIGIR Conf. on Research and Development in Information Retrieval, pp. 296–303 (2000)
Pandurangan, G., Raghavan, P., Upfal, E.: Using pagerank to characterize Web structure. In: H. Ibarra, O., Zhang, L. (eds.) COCOON 2002. LNCS, vol. 2387, pp. 330–339. Springer, Heidelberg (2002)
Donato, D., Laura, L., Leonardi, S., Millozzi, S.: Large scale properties of the webgraph. European Physical Journal B 38, 239–243 (2004)
Garcia-Molina, H.: The Stanford WebBase Project (2005), http://www-diglib.stanford.edu/~testbed/doc2/WebBase/
Nakamura, I.: Large scale properties of the webgraph. Physical Review 68 (2003) 045104
Volkovich, Y., Litvak, N., Donato, D.: Determining factors behind the PageRank log-log plot. Technical Report 1823, Department of Applied Mathematics, University of Twente (2007)
Binney, J., Dowrick, N., Fisher, A., Newman, M.: The theory of critical phenomena. First edn. Oxford University Press, Oxford (1992)
Pastor-Satorras, R., Vespignani, A.: Evolution and Structure of the Internet. Cambridge University Press, Cambridge, UK (2004)
Laboratory for Web Algorithmics (LAW), University of Milan: WebGraph (2005), http://webgraph.dsi.unimi.it
Donato, D., Leonardi, S., Tsaparas, P.: Stability and similarity of link analysis ranking algorithms. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005. LNCS, vol. 3580, pp. 717–729. Springer, Heidelberg (2005)
Serrano, M., Maguitman, A., Boguñá, M., Fortunato, S., Vespignani, A.: Decoding the structure of the WWW: Facts versus bias. In: ACM Transactions on the Web (In press)
Websidestory: User navigation behavior to effect link popularity (May, Cited by Search Engine Round Table According to this source, Websidestory Vice President Jay McCarthy announced at the Search Engine Strategies Conference (Toronto 2005) that the number of page referrals from search engines has surpassed those from other pages (2005), http://www.seroundtable.com/archives/001901.html
Sullivan, D.: Intro to search engine optimization, http://searchenginewatch.com/webmasters/article.php/2167921
Qiu, F., Liu, Z., Cho, J.: Analysis of user web traffic with a focus on search activities. In: Proc. International Workshop on the Web and Databases (WebDB). (2005)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Fortunato, S., Boguñá, M., Flammini, A., Menczer, F. (2008). Approximating PageRank from In-Degree. In: Aiello, W., Broder, A., Janssen, J., Milios, E. (eds) Algorithms and Models for the Web-Graph. WAW 2006. Lecture Notes in Computer Science, vol 4936. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-78808-9_6
Download citation
DOI: https://doi.org/10.1007/978-3-540-78808-9_6
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-78807-2
Online ISBN: 978-3-540-78808-9
eBook Packages: Computer ScienceComputer Science (R0)