Tuesday, January 25th @ 12:30-2:00 PM (1011 Evans Hall)
PageRank on directed complex networks
Mariana Olvera-Cravioto, UC Berkeley
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.