PageRank on directed preferential attachment graph

23 November 2021
Mariana Olvera-Cravioto

We study a family of evolving directed random graphs that includes the directed preferential model and the directed uniform attachment model. The directed preferential model is of particular interest since it is known to produce scale-free graphs with regularly varying in-degree distribution. We start by describing the local weak limits for our family of random graphs in terms of randomly stopped continuous-time branching processes, and then use these limits to establish the asymptotic behavior of the corresponding PageRank distribution. We show that the limiting PageRank distribution decays as a power-law in both models, which is surprising for the uniform attachment model where the in-degree distribution has exponential tails. And even for the preferential attachment model, where the power-law hypothesis suggests that PageRank should follow a power-law, our result shows that the two tail indexes are different, with the PageRank distribution having a heavier tail than the in-degree distribution.

  • Combinatorial Theory Seminar