Article

Approximating PageRank from In-Degree

Authors:

Santo Fortunato,

Marián Boguñá,

Alessandro Flammini,

Filippo MenczerAuthors Info & Claims

Algorithms and Models for the Web-Graph: Fourth International Workshop, WAW 2006, Banff, Canada, November 30 - December 1, 2006. Revised Papers

Pages 59 - 71

https://doi.org/10.1007/978-3-540-78808-9_6

Published: 01 November 2007 Publication History

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.

References

[1]

Brin S. and Page L. The anatomy of a large-scale hypertextual Web search engine Computer Networks 1998 30 1–7 107-117

[2]

Sullivan, D.: Nielsen//netratings search engine ratings (August (2005), http://searchenginewatch.com/reports/article.php/2156451

[3]

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)

[4]

Pandurangan G., Raghavan P., and Upfal E. H. Ibarra O. and Zhang L. Using pagerank to characterize Web structure Computing and Combinatorics 2002 Heidelberg Springer 330-339

[5]

Donato D., Laura L., Leonardi S., and Millozzi S. Large scale properties of the webgraph European Physical Journal B 2004 38 239-243

[6]

Garcia-Molina, H.: The Stanford WebBase Project (2005), http://www-diglib.stanford.edu/~testbed/doc2/WebBase/

[7]

Nakamura I. Large scale properties of the webgraph Physical Review 2003 68 045104

[8]

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)

[9]

Binney J., Dowrick N., Fisher A., and Newman M. The theory of critical phenomena. First edn. 1992 Oxford Oxford University Press

[10]

Pastor-Satorras R. and Vespignani A. Evolution and Structure of the Internet. 2004 Cambridge, UK Cambridge University Press

[11]

Laboratory for Web Algorithmics (LAW), University of Milan: WebGraph (2005), http://webgraph.dsi.unimi.it

[12]

Donato D., Leonardi S., and Tsaparas P. Caires L., Italiano G.F., Monteiro L., Palamidessi C., and Yung M. Stability and similarity of link analysis ranking algorithms Automata, Languages and Programming 2005 Heidelberg Springer 717-729

[13]

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)

[14]

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

[15]

Sullivan, D.: Intro to search engine optimization, http://searchenginewatch.com/webmasters/article.php/2167921

[16]

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)

Cited By

Guo XWu Z(2023)Short Video Account Influence Evaluation Model Based on Improved SF-UIR AlgorithmAlgorithms and Architectures for Parallel Processing10.1007/978-981-97-0834-5_1(1-16)Online publication date: 20-Oct-2023
https://dl.acm.org/doi/10.1007/978-981-97-0834-5_1
Mahéo ASutra PTarrant TZhang KGherbi AVenkatasubramanian NVeiga L(2021)The serverless shellProceedings of the 22nd International Middleware Conference: Industrial Track10.1145/3491084.3491426(9-15)Online publication date: 6-Dec-2021
https://dl.acm.org/doi/10.1145/3491084.3491426
Markovich NKrieger U(2021)The PageRank Vector of a Scale-Free Web Network Growing by Preferential AttachmentDistributed Computer and Communication Networks: Control, Computation, Communications10.1007/978-3-030-92507-9_3(24-31)Online publication date: 20-Sep-2021
https://dl.acm.org/doi/10.1007/978-3-030-92507-9_3
Show More Cited By

Recommendations

Re-ranking search results using query logs
CIKM '06: Proceedings of the 15th ACM international conference on Information and knowledge management

This work addresses two common problems in search, frequently occurring with underspecified user queries: the top-ranked results for such queries may not contain documents relevant to the user's search intent, and fresh and relevant pages may not get ...
A Googol of Information about Google

Timothy P. Chartier reviews Google's PageRank and Beyond: The Science of Search Engine Rankings by Amy Langville and Carl Meyer.
Discovering the representative of a search engine
CIKM '01: Proceedings of the tenth international conference on Information and knowledge management

Given a large number of search engines on the Internet, it is difficult for a person to determine which search engines could serve his/her information needs. A common solution is to construct a metasearch engine on top of the search engines. Upon ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

Algorithms and Models for the Web-Graph: Fourth International Workshop, WAW 2006, Banff, Canada, November 30 - December 1, 2006. Revised Papers

Nov 2006

117 pages

ISBN:978-3-540-78807-2

DOI:10.1007/978-3-540-78808-9

© Springer-Verlag Berlin Heidelberg 2008.

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 01 November 2007

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

9
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 17 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Guo XWu Z(2023)Short Video Account Influence Evaluation Model Based on Improved SF-UIR AlgorithmAlgorithms and Architectures for Parallel Processing10.1007/978-981-97-0834-5_1(1-16)Online publication date: 20-Oct-2023
https://dl.acm.org/doi/10.1007/978-981-97-0834-5_1
Mahéo ASutra PTarrant TZhang KGherbi AVenkatasubramanian NVeiga L(2021)The serverless shellProceedings of the 22nd International Middleware Conference: Industrial Track10.1145/3491084.3491426(9-15)Online publication date: 6-Dec-2021
https://dl.acm.org/doi/10.1145/3491084.3491426
Markovich NKrieger U(2021)The PageRank Vector of a Scale-Free Web Network Growing by Preferential AttachmentDistributed Computer and Communication Networks: Control, Computation, Communications10.1007/978-3-030-92507-9_3(24-31)Online publication date: 20-Sep-2021
https://dl.acm.org/doi/10.1007/978-3-030-92507-9_3
Vial DSubramanian V(2019)A Structural Result for Personalized PageRank and its Algorithmic ConsequencesProceedings of the ACM on Measurement and Analysis of Computing Systems10.1145/3341617.33261403:2(1-88)Online publication date: 19-Jun-2019
https://dl.acm.org/doi/10.1145/3341617.3326140
Fraisier OCabanac GPitarch YBesançon RBoughanem MLee DSastry NWeber I(2018)Stance Classification through Proximity-based Community DetectionProceedings of the 29th on Hypertext and Social Media10.1145/3209542.3209549(220-228)Online publication date: 3-Jul-2018
https://dl.acm.org/doi/10.1145/3209542.3209549
Lindner GStaudt CHamann MMeyerhenke HWagner D(2015)Structure-Preserving Sparsification of Social NetworksProceedings of the 2015 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining 201510.1145/2808797.2809313(448-454)Online publication date: 25-Aug-2015
https://dl.acm.org/doi/10.1145/2808797.2809313
Bar-Ilan JLevene M(2015)The hw-rankScientometrics10.1007/s11192-014-1477-2102:3(2247-2253)Online publication date: 1-Mar-2015
https://dl.acm.org/doi/10.1007/s11192-014-1477-2
Avrachenkov KKadavankandy AOstroumova Prokhorenkova LRaigorodskii A(2015)PageRank in Undirected Random GraphsProceedings of the 12th International Workshop on Algorithms and Models for the Web Graph - Volume 947910.1007/978-3-319-26784-5_12(151-163)Online publication date: 10-Dec-2015
https://dl.acm.org/doi/10.1007/978-3-319-26784-5_12
Agrawal RGollapudi SKannan AKenthapadi KHe QIyengar ANejdl WPei JRastogi R(2013)Studying from electronic textbooksProceedings of the 22nd ACM international conference on Information & Knowledge Management10.1145/2505515.2505604(1715-1720)Online publication date: 27-Oct-2013
https://dl.acm.org/doi/10.1145/2505515.2505604

View Options

View options

Media

Figures

Other

Tables

View Table of Contents