Power-law hypothesis for PageRank on undirected graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911960897945600 |
|---|---|
| author | Henning, Florian van der Hofstad, Remco Litvak, Nelly |
| author_facet | Henning, Florian van der Hofstad, Remco Litvak, Nelly |
| contents | Based on observations in the web-graph, the power-law hypothesis states that PageRank has a power-law distribution with the same exponent as the in-degree. While this hypothesis has been analytically verified for many random graph models, such as directed configuration models and generalized random graphs, surprisingly it has recently been disproven for the directed preferential attachment model. In this paper, we prove that in undirected networks, the graph-normalized PageRank is always upper bounded by the degree. Furthermore, we prove that the corresponding (asymptotic) lower bound holds true under reasonable assumptions on the local weak limit, but not in general, and we provide a counterexample. Our result shows that PageRank always has a lighter tail than the degree, which contrasts the case of the directed preferential attachment model, where PageRank has a heavier tail instead. We end the paper with a discussion, where we extend our results to directed networks with a bounded ratio of in- and out-degrees, and reflect on our methods by contrasting the undirected and directed preferential attachment model. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_13730 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Power-law hypothesis for PageRank on undirected graphs Henning, Florian van der Hofstad, Remco Litvak, Nelly Probability 05C80 (Primary) 60J80, 60B20 (Secondary) Based on observations in the web-graph, the power-law hypothesis states that PageRank has a power-law distribution with the same exponent as the in-degree. While this hypothesis has been analytically verified for many random graph models, such as directed configuration models and generalized random graphs, surprisingly it has recently been disproven for the directed preferential attachment model. In this paper, we prove that in undirected networks, the graph-normalized PageRank is always upper bounded by the degree. Furthermore, we prove that the corresponding (asymptotic) lower bound holds true under reasonable assumptions on the local weak limit, but not in general, and we provide a counterexample. Our result shows that PageRank always has a lighter tail than the degree, which contrasts the case of the directed preferential attachment model, where PageRank has a heavier tail instead. We end the paper with a discussion, where we extend our results to directed networks with a bounded ratio of in- and out-degrees, and reflect on our methods by contrasting the undirected and directed preferential attachment model. |
| title | Power-law hypothesis for PageRank on undirected graphs |
| topic | Probability 05C80 (Primary) 60J80, 60B20 (Secondary) |
| url | https://arxiv.org/abs/2407.13730 |