Nelly Litvak

University of Twente, Netherlands

Ranking in large scale-free networks

Abstract. Ranking algorithms are crucial for assessing the importance of a node in a network, and have a wide range of applications, from clustering of networks to link prediction. An example is the famous Google PageRank algorithm for ranking web pages.  In this talk I will discuss several topics related to the mathematical properties of ranking algorithms in large networks.

One of the examples is the distribution of a family of rankings, which includes Google's PageRank in random graphs. It has been observed empirically in many studies that the distribution of the PageRank and In-degree in directed networks are closely related, however, the literature did not provide any rigorous explanation for this phenomenon. We make an important step further by obtaining a complete characterization of PageRank distribution in a random graph created by a Directed Configuration Model. Our results show  remarkable accuracy when compared to the PageRank distribution on the Wikipedia.

Next, I will discuss the problem of finding nodes with highest in-degrees when the network is unknown. This is the case, for example, in the Twitter follower network, that can be only accesses via the Twitter API. We propose Monte Carlo algorithms to find most important nodes using only a very small number of API requests. These methods are surprisingly efficient because of the high variability in the nodes’ degrees.