Ranking

We face rankings in our daily life rather often, e.g. consumer organizations rank products according to their qualities, scientists are ranked upon their publications, musicians aim for a top chart position, soccer teams compete for wins in order to climb up in the league table and so on. Thus, the central idea of a ranking is to arrange subjects in such a way that “better” subjects have higher positions. Obviously, most of the rankings are based on an intuitive order, e.g. more victories of a team lead to a higher place in the soccer league, the higher quality index should result in a more valuable ranking for consumption of goods and services. Apart from these examples, rankings can also be derived just out of the relations between the objects under consideration. Depending on a particular application—we consider Google problem, brand loyalty, and social status—those interrelations give rise to transition probabilities and, hence, to the definition of a ranking as the leading eigenvector of a corresponding stochastic matrix. In this chapter we explain the mathematics behind ranking. First, we focus on the existence of a ranking by using the duality of linear programming. This leads to Perron-Frobenius theorem from linear algebra. Second, a dynamic procedure known as PageRank is studied. The latter enables us to approximate rankings by iterative schemes in a fast and computationally cheap manner, which is crucial for big data applications.