Determining Factors Behind the PageRank Log-Log Plot

DOI10.1007/978-3-540-77004-6_9MaRDI QIDQ5458304zbMATH OpenOpenAlexFDO

Authors Yana Volkovich, Nelly Litvak, Debora Donato

Publication date 11 April 2008

Published in Algorithms and Models for the Web-Graph (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0704.2694, https://research.utwente.nl/en/publications/determining-factors-behind-the-pagerank-loglog-plot(5a74d085-68c5-4b2f-b164-20e671f5cf94).html

zbMATH Keywords

PageRankPower lawsRanking algorithmsStochastic equationsWeb graphWikipedia

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10)

Abstract: We study the relation between PageRank and other parameters of information networks such as in-degree, out-degree, and the fraction of dangling nodes. We model this relation through a stochastic equation inspired by the original definition of PageRank. Further, we use the theory of regular variation to prove that PageRank and in-degree follow power laws with the same exponent. The difference between these two power laws is in a multiple coefficient, which depends mainly on the fraction of dangling nodes, average in-degree, the power law exponent, and damping factor. The out-degree distribution has a minor effect, which we explicitly quantify. Our theoretical predictions show a good agreement with experimental data on three different samples of the Web.

Recommendations

• In-Degree and PageRank: why do they follow similar power laws?
• Probabilistic Relation between In-Degree and PageRank
• PageRank of Scale-Free Growing Networks
• scientific article; zbMATH DE number 2089988
• PageRank's behavior under degree correlations

Cites work

• A survey of max-type recursive distributional equations
• Approximating PageRank from In-Degree
• Asymptotic properties and absolute continuity of laws stable by random weighted mean.
• Authoritative sources in a hyperlinked environment
• Authority Rankings from HITS, PageRank, and SALSA: Existence, Uniqueness, and Effect of Initialization
• Deeper Inside PageRank
• Emergence of Scaling in Random Networks
• scientific article; zbMATH DE number 43570 (Why is no real title available?)
• scientific article; zbMATH DE number 1093829 (Why is no real title available?)
• scientific article; zbMATH DE number 2089988 (Why is no real title available?)
• PageRank of Scale-Free Growing Networks
• RANDOM WALKS ON DIRECTED NETWORKS: THE CASE OF PAGERANK
• Regularly varying functions
• The Effect of New Links on Google Pagerank
• THE INSPECTION PARADOX

Cited in

(16)

• PageRank on inhomogeneous random digraphs
• PageRank's behavior under degree correlations
• Algorithmic bias amplification via temporal effects: the case of PageRank in evolving networks
• PageRank in Scale-Free Random Graphs
• Information ranking and power laws on trees
• Approximating PageRank from In-Degree
• Probabilistic Relation between In-Degree and PageRank
• Traps and Pitfalls of Topic-Biased PageRank
• Asymptotic analysis for personalized web search
• Characterization of Tail Dependence for In-Degree and PageRank
• Tail behavior of solutions of linear recursions on trees
• About the power law of the PageRank vector component distribution. II: The Buckley-Osthus model, verification of the power law for this model, and setup of real search engines
• Distribution of PageRank Mass Among Principle Components of the Web
• PageRank of Scale-Free Growing Networks
• In-Degree and PageRank: why do they follow similar power laws?
• Rankings in directed configuration models with heavy tailed in-degrees

This page was built for publication: Determining Factors Behind the PageRank Log-Log Plot

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5458304)