We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.

Durham e-Theses
You are in:

Page Ranking Systems: Axiomatisation and Experimentation

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 (2008-2017)
Thesis Date:2015
Copyright:Copyright of this thesis is held by the author
Deposited On:19 Mar 2015 15:38

Social bookmarking: del.icio.usConnoteaBibSonomyCiteULikeFacebookTwitter