The DOI matches its Crossref record; 5 of the 6 references it cites were found in a registry or an index.
The distribution of pageRank follows a power-law only for particular values of the damping factor
Abstract
The empirical distribution of PageRank in a large sample of Web pages does not follow a powerlaw except for particular choices of the damping factor. The tail, comprising 5%10 % of the nodes, always follows a power law, but the distribution for the remaining 90%95 % of pages varies. This was observed in several Web samples having from 1 to 50 million pages with damping factors from 0.1 to 0.9 and the resulting behavior was very similar, specially if we restrict the sample to the main strongly connected component. DoublePareto Model As in [Mitzenmacher 2003], we can fit the powerlaw to the body and the tail of the distribution separately, as in the figure on the right. Given that the minimum value of PageRank is the baseline probability (1-α / N) if we assume the following: (i) The exponent of the body is equal to the exponent of the tail (ii)The distribution is normalized to 1, as in the case of PageRank (iii) N>> 1... we can show that the intersection point of the first figure, 1-F(1/N) does Conjecture not depend on N: 1-F(1/N) ≃ (1-α) θ-1 In a graph with powerlaw exponent θ for the indegree, calculating PageRank with: If we accept the hypothesis in [Pandurangan et al. 2002], that is, the powerlaw exponent for the distribution of the tail of the PageRank values is the same as for the indegree of pages, then: α = 1 θ – 1 In our collection of 1 million nodes with θ=2.2 and α=0.85, the Yields a powerlaw over the entire range of values value predicted for 1F(1/N) is 0.10 and the observed 0.12 In the WebBase collection of 130 million documents with θ=2.07 and α=0.85 the predicted value is 0.13, and the 0.16 Examples: θ=2.1, then α=0.90 yields a powerlaw θ=2.2, then α=0.83 yields a powerlawLognormal + Baseline Model Let X be a random variable distributed according to a lognormal distribution. We propose the following model for the PageRank distribution: X + (1-α)/N To obtain the lognormal parameters, we fit this to the distribution of PageRank with α=0.99. Then using the same parameters, we can fit the PageRank distribution obtained with other damping factors with high precision. Fit with our model: Fit with a powerlaw:
Overview
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
Citations
Cites
(1999) · Cited by 12,854
Newman (2005) · doi:10.1080/00107510500052444 · Cited by 5,749
A Simple General Approach to Inference About the Tail of a Distribution
Hill, B. M. (1975) · The Annals of Statistics · doi:10.1214/aos/1176343247 · Cited by 3,086
WebBase: a repository of Web pages
Hirai, J., Raghavan, S., Garcia-Molina, H., & Paepcke, A. (2000) · Computer Networks · doi:10.1016/s1389-1286(00)00063-3 · Cited by 183
Using PageRank to Characterize Web Structure
Pandurangan, G., Raghavan, P., & Upfal, E. (2002) · Lecture Notes in Computer Science · doi:10.1007/3-540-45655-4_36 · Cited by 164
Research works printed but not linked: 1
- E. Efthimiadis and C. Castillo . Charting the Greek Web . In Proc. of ASIST , Providence, Rhode Island, USA , Nov. 2004 . E. Efthimiadis and C. Castillo. Charting the Greek Web. In Proc. of ASIST, Providence, Rhode Island, USA, Nov. 2004.
Cited by
Web graph similarity for anomaly detection
Papadimitriou, P., Dasdan, A., & Garcia-Molina, H. (2010) · Journal of Internet Services and Applications · doi:10.1007/s13174-010-0003-x · Cited by 224
“The increasing sizes of subsets were motivated by the power law distribution of the quality scores [1].”
BackgroundTemporal Analysis of the Wikigraph
Buriol, L. S., Castillo, C., Donato, D., Leonardi, S., & Millozzi, S. (2006) · IEEE/WIC/ACM International Conference on Web Intelligence · doi:10.1109/wi.2006.164 · Cited by 138
“The ta il of the distribution of PageRank for the usual parameter settin g follows a power-law [22].”
BackgroundSelf-citationXin, R., Chen, P., & Zhao, Z. (2023) · Journal of Systems and Software · doi:10.1016/j.jss.2023.111724 · Cited by 164
In-Degree and PageRank: Why Do They Follow Similar Power Laws?
Litvak, N., Scheinhardt, W. R. W., & Volkovich, Y. (2007) · Internet Mathematics · doi:10.1080/15427951.2007.10129293 · Cited by 62
Power Law Distributions in Information Retrieval
Petersen, C., Simonsen, J. G., & Lioma, C. (2016) · ACM Transactions on Information Systems · doi:10.1145/2816815 · Cited by 46
“The process by which power laws emerge varies from, for example, the choice of dampening factor in the PageRank computation [Becchetti and Castillo 2006], to models of behavioral psychology (e.g., preferential attachment : New objects tend to attach to popular objects [Barab´asi et al. 1999]).”
Background
Metadata
- Authors
- Becchetti, L., & Castillo, C.
- Affiliations
- Sapienza University of Rome (IT)
- Venue
- Proceedings of the 15th international conference on World Wide Web
- Publisher
- ACM
- Published
- 2006-05-23
- Pages
- 941-942
- OpenAlex
- W2119485457
- Cited by
- 48
- References
- 6
- Citations by year
- 2026: 1 · 2025: 2 · 2024: 4 · 2023: 3 · 2022: 1 · 2021: 1 · 2020: 2 · 2019: 1 · 2018: 2 · 2016: 3 · 2015: 7 · 2014: 2 · 2013: 2 · 2012: 1
- FWCI
- 7.28
- Type
- conference paper
- Language
- en
- Open access
- closed
- Locations
- International World Wide Web Conference (WWW) (publishedVersion)
- IRIS Research product catalog (Sapienza University of Rome) (submittedVersion)
- Topics
- Physical Sciences › Physics and Astronomy › Statistical and Nonlinear Physics › Complex Network Analysis Techniques
- Physical Sciences › Computer Science › Information Systems › Information Retrieval and Search Behavior
- Physical Sciences › Computer Science › Information Systems › Web visibility and informetrics
- Keywords
- damping factor, power-law distribution, web graph, lognormal distribution, tail distribution
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: The distribution of pageRank follows a power-law only for particular values of the damping factor. https://app.cochat.ai/papers/10.1145/1135777.1135955
- The paper
- Becchetti, L., & Castillo, C. (2006). The distribution of pageRank follows a power-law only for particular values of the damping factor. Proceedings of the 15th international conference on World Wide Web. https://doi.org/10.1145/1135777.1135955
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.