### Abstract

Original language | English |
---|---|

Pages (from-to) | 175-198 |

Number of pages | 24 |

Journal | Internet mathematics |

Volume | 4 |

Issue number | 2-3 |

DOIs | |

Publication status | Published - 2009 |

### Fingerprint

### Keywords

- Taube-rian theorems
- Power law
- EWI-15650
- MSC-68P10
- MSC-90B15
- MSC-40E05
- METIS-264406
- IR-67788
- In-Degree
- Regular variation
- PageRank
- Stochastic equation

### Cite this

*Internet mathematics*,

*4*(2-3), 175-198. https://doi.org/10.1080/15427951.2007.10129293

}

*Internet mathematics*, vol. 4, no. 2-3, pp. 175-198. https://doi.org/10.1080/15427951.2007.10129293

**In-Degree and PageRank of web pages : why do they follow similar power laws?** / Litvak, Nelly; Scheinhardt, Willem R.W.; Volkovich, Y.

Research output: Contribution to journal › Article › Academic › peer-review

TY - JOUR

T1 - In-Degree and PageRank of web pages

T2 - why do they follow similar power laws?

AU - Litvak, Nelly

AU - Scheinhardt, Willem R.W.

AU - Volkovich, Y.

PY - 2009

Y1 - 2009

N2 - PageRank is a popularity measure designed by Google to rank Web pages. Experiments confirm that PageRank values obey a power law with the same exponent as In-Degree values. This paper presents a novel mathematical model that explains this phenomenon. The relation between PageRank and In-Degree is modelled through a stochastic equation, which is inspired by the original definition of PageRank, and is analogous to the well-known distributional identity for the busy period in the $M/G/1$ queue. Further, we employ the theory of regular variation and Tauberian theorems to analytically prove that the tail distributions of PageRank and In-Degree differ only by a multiple factor, for which we derive a closed-form expression. Our analytical results are in good agreement with experimental data.

AB - PageRank is a popularity measure designed by Google to rank Web pages. Experiments confirm that PageRank values obey a power law with the same exponent as In-Degree values. This paper presents a novel mathematical model that explains this phenomenon. The relation between PageRank and In-Degree is modelled through a stochastic equation, which is inspired by the original definition of PageRank, and is analogous to the well-known distributional identity for the busy period in the $M/G/1$ queue. Further, we employ the theory of regular variation and Tauberian theorems to analytically prove that the tail distributions of PageRank and In-Degree differ only by a multiple factor, for which we derive a closed-form expression. Our analytical results are in good agreement with experimental data.

KW - Taube-rian theorems

KW - Power law

KW - EWI-15650

KW - MSC-68P10

KW - MSC-90B15

KW - MSC-40E05

KW - METIS-264406

KW - IR-67788

KW - In-Degree

KW - Regular variation

KW - PageRank

KW - Stochastic equation

U2 - 10.1080/15427951.2007.10129293

DO - 10.1080/15427951.2007.10129293

M3 - Article

VL - 4

SP - 175

EP - 198

JO - Internet mathematics

JF - Internet mathematics

SN - 1542-7951

IS - 2-3

ER -