Abstract: The talk will center around a set of recent results on the analysis of Google’s PageRank algorithm on directed complex networks. In particular, it will focus on the so-called power-law hypothesis, which states that the distribution of the ranks produced by PageRank on a scale-free graph (whose in-degree distribution follows a power-law) also follows a power-law with the same tail-index as the in-degree. We show that the distribution of PageRank on both the directed configuration model and the inhomogeneous random digraph does indeed follow a power-law whenever the in-degree does, and we provide explicit asymptotic limits for it. Moreover, our asymptotic expressions exhibit qualitatively different behaviors depending on the level of dependence between the in-degree and out-degree of each vertex. On graphs where the in-degree and out-degree are close to independent, our main theorem predicts that PageRank will tend to grant high ranks to vertices with large in-degrees, but also to vertices who have highly-ranked inbound neighbors. However, when the in-degree and out-degree are positively correlated, the latter can potentially disappear, strengthening the impact of high-degree vertices on the ranks produced by the algorithm.
- Slides
- Start date: 2018-01-25 12:30:00
- End date: 2018-01-25 14:00:00
- Venue: 1011 Evans Hall
- Address: 1011 Evans Hall, Berkeley, CA, 94720