BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Ranking algorithms on directed random networks - Olvera-Cravioto\,
  M (Columbia University)
DTSTART:20130813T123000Z
DTEND:20130813T131500Z
UID:TALK46608@talks.cam.ac.uk
CONTACT:Mustapha Amrani
DESCRIPTION:The probabilistic analysis of information ranking algorithms o
 n directed random networks\, e.g.\, Google's PageRank\, has recently led t
 o natural approximations based on stochastic fixed-point equations whose e
 xplicit solutions can be constructed on weighted branching trees and whose
  tail behavior can be described in great detail.  In this talk we present 
 a model for generating directed random graphs with prescribed degree distr
 ibutions where we can prove that the rank of a randomly chosen node does i
 ndeed converge to the solution of the corresponding fixed-point equation a
 s the number of nodes in the graph grows to infinity. The proof of this re
 sult is based on classical random graph coupling techniques combined with 
 the now extensive literature on the behavior of branching recursions on tr
 ees. The results we present are applicable to a wide class of linear algor
 ithms 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 Ne
 lly Litvak.\n
LOCATION:Seminar Room 1\, Newton Institute
END:VEVENT
END:VCALENDAR