Page Ranking Systems: Axiomatisation and Experimentation

Abstract

Ranking a set of objects based on the relationships between them is fundamental for use with search engines, e-commerce websites and in the field of bibliometrics. Two of the most prominent search ranking algorithms are PageRank and SALSA (Stochastic Approach to Link-Structure Analysis).

In this thesis, we further explore the connections between page ranking algorithms and the theory of social choice, providing a basis for theoretical assessment of a weighted version of PageRank and we create and assess a new page ranking al- gorithm, combining ideas from both PageRank and SALSA which we call Query- Independent SALSA.

We justify the use of weighted PageRank from a theoretical perspective by providing a set of axioms which characterize the algorithm. We provide a tighter bound for our derivation than that of Altman et al and show that each of our axioms are independent.

We describe a query-independent version of SALSA, using ideas from the PageRank algorithm and test this on a real-world subgraph of the web graph. We find that our new algorithm, Query-Independent Stochastic Approach to Link-Structure Analysis (QISALSA) slightly outperforms PageRank on two measures and under-performs on one measure. We suggest that the approach of combining aspects of both algo-rithms may be less eective than precomputational methods for query-dependent algorithms.