PageRank algorithm was introduced by Google in 1998 to rank web pages. Unlike earlier ranking based on content, PageRank computes the rank of a page based on the quantity and quality of its incoming hyperlinks. This idea of link analysis revolutionized web search and made an enormous impact on the analysis of other complex networks such as social networks, financial networks, ecological food webs, protein-protein interactions, and networks of neurons in our brain.  Beyond ranking, PageRank is used for detecting network communities, link prediction, name disambiguation,  and as input to downstream machine learning tasks.

In this talk I will present a line of work on PageRank in random graphs, where the vertices are fixed, and the edges exist with a given probability defined by a random graph model. We will consider random graph models that faithfully represent two properties of real-life networks: these models are sparse, that is, the average degree remains bounded when the graph size goes to infinity;  these models are scale-free, that is, there is a group of vertices with degrees much higher than average. I will first present a general result that in such sparse random graphs, PageRank is completely defined by local neighborhood. This enables us to establish the relation between probability distributions of the degrees and the PageRank scores in the graph. Surprisingly, despite the fact that PageRank is strongly related to the (in-)degree,  this relation is different in different models. Moreover, the results are strikingly different for directed and undirected graphs.