Loading Events

« All Events

  • This event has passed.

Mariana Olvera-Cravioto, UC Berkeley: PageRank on directed complex networks

January 25 @ 12:30 pm - 2:00 pm

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.

Download the slides from this presentation: Olvera_PageRank

Details

Date:
January 25
Time:
12:30 pm - 2:00 pm
Event Category:

Venue

1011 Evans Hall
Berkeley, CA 94720 United States + Google Map