Presented by: 
Mariana Olvera-Cravioto (Columbia University)
Date: 
Mon 13 Apr, 2:00 pm - 2:45 pm
Venue: 
Hawken Building (50), room N202

The probabilistic analysis of information ranking algorithms on directed random networks, e.g., Google's PageRank, has recently led to natural approximations based on stochastic fixed-point equations on weighted branching trees whose tail behavior can be described in great detail. Using a directed configuration model we show that the rank of a randomly chosen node does indeed converge to the stochastic fixed-point equation heuristic as the number of nodes in the graph grows to infinity. As a consequence, our work provides the first ever rigorous proof of the so-called “power-law” hypothesis, which states that PageRank has a power-law tail proportional to that of the in-degree in any scale-free graph. The proof of this result is based on classical random graph coupling techniques combined with the now extensive literature on the behavior of branching recursions on trees. The results we present are applicable to a wide class of linear algorithms on directed graphs, and have the potential to be extended to other max-plus type of recursions. This is joint work with Ningyuan Chen and Nelly Litvak.