Αλγόριθμοι κατάταξης στον παγκόσμιο ιστό

Abstract

Το αντικείμενο αυτής της εργασίας είναι η επισκόπηση, η αναλυτική παρουσίαση και η μελέτη των πιο θεμελιωδών αλγορίθμων ανάλυσης υπερσυνδέσμων που χρησιμοποιούνται σήμερα για την κατάταξη των αποτελεσμάτων των μηχανών αναζήτησης βάσει της δημοφιλίας τους και της αξιοπιστίας τους.Αλγόριθμοι όπως ο HITS του Kleinberg, ο PageRank των Brin και Page ο SALSA των Lempel και Moran και άλλοι χρησιμοποιούν την υπερσυνδεσμοδομή του παγκόσμιου ιστού για να κατατάξουν τις ιστοσελίδες όσον αφορά την αξιοπιστία και την δημοφιλία τους. Όλοι αυτοί οι αλγόριθμοι βασίζονται σε έναν υπολογισμό: Την εύρεση του ιδιοδιανύσματος της επικρατούσας ιδιοτιμής ενός πίνακα με διάσταση 8 δισεκατομμυρίων ο οποίος μοντελοποιεί τη δομή του Παγκόσμιου Ιστού. Αυτό θα κάνουμε και εμείς σε αυτή την εργασία, θα προσπαθήσουμε να βρούμε αυτό το ιδιοδιάνυσμα.

Web search differs from traditional information retrieval tasks in several major ways, making effective and efficient web search a challenging task. Web page ranking has become a central ingredient of search engines. The seminal papers of Kleinberg and Brin and Page introduced Link Analysis Ranking that exploits the hyperlink structure of the Web to determine the relative authority of a Web page and produce improved algorithms for the ranking of Web search results.The most famous applications of ranking algorithms are Google's PageRank algorithm and eBay's reputation system. This thesis deals with the analysis and comparison of web page ranking algorithms based on various parameters to find out their advantages and limitations for the ranking of web pages. All these algorithms are based on the computation of the dominant eigenvector of a matrix with 8 billion rows. In this thesis we also study the properties of the mathematical objects such as eigenvectors and eigenvalues, which constitute the basis of these algorithms.