HEPPENSTALL, ALAN (2015) Page Ranking Systems: Axiomatisation and Experimentation. Masters thesis, Durham University.
|PDF - Accepted Version|
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.
|Item Type:||Thesis (Masters)|
|Award:||Master of Science|
|Keywords:||page ranking, pagerank, salsa, page ranking systems, search engines|
|Faculty and Department:||Faculty of Science > Engineering and Computing Science, School of|
|Copyright:||Copyright of this thesis is held by the author|
|Deposited On:||19 Mar 2015 15:38|