Section: New Results

Random Graph and Matrix Models

Participants : Konstantin Avrachenkov, Maximilien Dreveton.

In [5], K. Avrachenkov, together with A. Kadavankandy (CentraleSupélec) and N. Litvak (Univ. of Twente, The Netherlands), analyse a mean-field model of Personalized PageRank on the Erdös-Rényi random graph containing a denser planted Erdös-Rényi subgraph. They investigate the regimes where the values of Personalized PageRank concentrate around the mean-field value. They also study the optimization of the damping factor, the only parameter in Personalized PageRank. Their theoretical results help to understand the applicability of Personalized PageRank and its limitations for local graph clustering.