Κεφάλαιο 9Ανάκτηση Πληροφορίας στον Παγκόσμιο Ιστό

Ο παγκόσμιος ιστός (World Wide Web) αποτελεί πραγματική πρόκληση για πολλές εφαρμογές, διότι διαθέτει μία σειρά από χαρακτηριστικά που φέρνουν στα όρια τη σύγχρονη τεχνολογία (για παράδειγμα το τεράστιο πλήθος των εγγράφων που είναι διαθέσιμα). Στην πράξη ο Παγκόσμιος Ιστός αποτελείται από ένα τεράστιο πλήθος σελίδων που συνδέονται μεταξύ τους με συνδέσμους (links). Στο κεφάλαιο αυτό θα μελετήσουμε τεχνικές Ανάκτησης Πληροφορίας που στοχεύουν στην αποδοτικότερη και αποτελεσματικότερη διαχείριση δεδομένων στον παγκόσμιο ιστό. Πιο συγκεκριμένα, θα εστιάσουμε στη λειτουργία των μηχανών αναζήτησης και των μεθόδων βαθμολόγησης των ιστοσελίδων. Θα εξηγήσουμε την ιστορία των μηχανών αναζήτησης και των τεχνικών που έχουν χρησιμοποιηθεί για τη βελτίωση της ποιότητας των αποτελεσμάτων.

Ο παγκόσμιος ιστός αποτελείται από ένα τεράστιο σύνολο ιστοσελίδων (web pages) οι οποίες διασυνδέονται μεταξύ τους. Η κάθε ιστοσελίδα συνήθως είναι γραμμένη σε γλώσσα HTML (hypertext markup language). Ωστόσο, υπάρχουν και δυναμικές σελίδες των οποίων το περιεχόμενο διαμορφώνεται δυναμικά (για παράδειγμα, σελίδες που είναι γραμμένες σε php ή jsp). Μία ιστοσελίδα αποτελείται κυρίως από περιεχόμενο κειμέμου (text) αλλά μπορεί να περιέχει πιο πολύπλοκα δεδομένα όπως εικόνες, ήχο και βίντεο. Στο κεφάλαιο αυτό μας ενδιαφέρει η δομή του παγκόσμιου ιστού, και για το λόγο αυτό θα εστιάσουμε κυρίως στους συνδέσμους μεταξύ των σελίδων υποθέτοντας ότι το περιεχόμενο είναι απλό κείμενο. Η κάθε ιστοσελίδα προσδιορίζεται μοναδικά από το URL (uniform resource locator) που μπορούμε να πούμε ότι χρησιμοποιείται και ως κλειδί για την ιστοσελίδα.

Ο παγκόσμιος ιστός μπορεί να αναπαρασταθεί απλοϊκά με ένα κατευθυνόμενο γράφημα (directed graph), όπως παρουσιάζεται στο Σχήμα 9.1. Στο παράδειγμα αυτό υπάρχουν 4 ιστοσελίδες Α, B, C και D. Παρατηρούμε ότι κάποιες σελίδες μπορεί να έχουν μόνο εισερχόμενους συνδέσμους (incoming links), κάποιες άλλες μόνο εξερχόμενους συνδέσμους (outgoing links) και κάποιες άλλες να έχουν και τους δύο τύπους συνδέσμων. Το πλήθος των συνδέσμων μπορεί να είναι πολύ διαφορετικό από ιστοσελίδα σε ιστοσελίδα και έχει παρατηρηθεί ότι ακολουθεί κατανομή power law.

Μία μηχανή αναζήτησης παγκόσμιου ιστού (web search engine) αποτελείται από ένα σύνολο τμημάτων λογισμικού και υλικού που έχει ως στόχο την εξυπηρέτηση των πληροφοριακών αναγκών των χρηστών στον παγκόσμιο ιστό. Οι μηχανές αναζήτησης χρησιμοποιούνται κυρίως στον παγκόσμιο ιστό όπου υπάρχουν και εκτενείς ανάγκες από την πλευρά των χρηστών. Επιπλέον, ο όγκος της πληροφορίας που βρίσκεται στον παγκόσμιο ιστό είναι τεράστιος που σε συνδυασμό με την ετερογένεια της πληροφορίας δημιουργεί πολύ σημαντικές προκλήσεις. Ωστόσο, υπάρχουν και μηχανές αναζήτησης ειδικού σκοπού, όπου το πεδίο εφαρμογής είναι περιορισμένο (π.χ., μηχανές αναζήτησης σε προσωπικούς υπολογιστές, μηχανές αναζήτησης για ιατρικά δεδομένα). Στην περίπτωση αυτή οι απαιτήσεις είναι διαφορετικές από την περίπτωση των μηχανών αναζήτησης γενικού σκοπού. Οι σημαντικότερες σύγχρονες μηχανές αναζήτησης είναι αυτές της Google, της Yahoo! και της Microsoft.

Το κεντρικό θέμα στο οποίο στηρίζεται ο αλγόριθμος HITS είναι η διύλιση ευρέων θεμάτων αναζήτησης μέσω της εύρεσης των αξιόπιστων πηγών πληροφορίας (authorities) για αυτά τα θέματα. Μία ιστοσελίδα χαρακτηρίζεται ως authority εάν έχει πολλούς εισερχόμενους συνδέσμους από άλλες αξιόπιστες ιστοσελίδες. Ο αλγόριθμος HITS εκτός από τις αξιόπιστες ιστοσελίδες βρίσκει επίσης και ιστοσελίδες που χαρακτησίζονται ως κομβικές ιστοσελίδες (hubs). Συνοπτικά, ο αλγόριθμος HITS συσχετίζει κάθε ιστοσελίδα $p$ με δύο τιμές $as(p)$ και $hs(p)$ που ποσοτικοποιούν την ποιότητα της ιστοσελίδας $p$ σχετικά με το πόσο αξιόπιστη είναι (authority score) και πόσο κομβική είναι (hab score).

Το βασικό χαρακτηριστικό του αλγορίθμου HITS είναι ότι οι βαθμοί $as(p)$ και $hs(p)$ που δίνει σε μία σελίδα εξαρτώνται από το θέμα για το οποίο ενδιαφέρεται ο χρήστης. Είναι προφανές ότι μία ιστοσελίδα που θεωρείται αξιόπιστη σχετικά με το θέμα ”C++” μπορεί να μη θεωρείται αξιόπιστη για το θέμα ”Java”. Επομένως, ο αλγόριθμος χαρακτηρίζεται ως ευαίσθητος ως προς το θέμα (topic sensitive) και θα πρέπει να εκτελείται εξαρχής εάν αλλάξει το θέμα για το οποίο ενδιαφέρεται ο χρήστης.

Έστω $G(V,E)$ το γράφημα που αναπαριστά τον παγκόσμιο ιστό, όπου $V$ είναι το σύνολο των κορυφών (ιστοσελίδων) και $E$ το σύνολο των ακμών (συνδέσμων). Η εκτέλεση του αλγορίθμου HITS αρχίζει με τον προσδιορισμό ενός υποσυνόλου ιστοσελίδων $R\subset V$ που θεωρούνται σχετικές ως προς κάποιο συγκεκριμένο θέμα που περιγράφεται από τις πληροφοριακές ανάγκες του χρήστη (π.χ., ”C++”). Το σύνολο $R$ χαρακτηρίζεται και ως βασικό σύνολο ιστοσελίδων. Το σύνολο $R$ επαυξάνεται ώστε να δημιουργηθεί το σύνολο $S\subset V$ το οποίο περιλαμβάνει όλες τις ιστοσελίδες που ανήκουν στο $R$ (άρα $R\subset S$) και επιπλέον περιλαμβάνει όλες τις ιστοσελίδες που έχουν εισερχόμενους συνδέσμους από ιστοσελίδες του $R$ και εξερχόμενους συνδέσμους προς ιστοσελίδες του $R$. Η συσχέτιση μεταξύ των συνόλων $R$ και $S$ απεικονίζεται στο Σχήμα 9.3 στο οποίο οι σύνδεσμοι διαφορετικού τύπου απεικονίζονται με διαφορετικές μορφές (π.χ., τα διακεκομμένα βέλη δηλώνουν συνδέσμους από ιστοσελίδες εκτός του συνόλου $R$ προς ιστοσελίδες του συνόλου $R$).

Αξίζει να σημειωθεί ότι το βασικό σύνολο ιστοσελίδων $R$ εξαρτάται από το θέμα/ερώτημα $Q$ του χρήστη. Επομένως, σε πρώτη φάση θα πρέπει να υπάρχει ένας εύχρηστος τρόπος προσδιορισμού του $R$. Στην πράξη το σύνολο $R$ δημιουργείται χρησιμοποιώντας μία μηχανή αναζήτησης. Πιο συγκεκριμένα, η μηχανή αναζήτησης δέχεται ως είσοδο το ερώτημα $Q$ και δίνει στην έξοδο ένα σύνολο $A$ από ιστοσελίδες. Από το σύνολο $A$ επιλέγονται οι $k$ ιστοσελίδες (π.χ., $k$=200) που σύμφωνα με τη μηχανή αναζήτησης είναι οι πιο σχετικές με το ερώτημα. Με βάση τον τρόπο κατασκευής των συνόλων $R$ και $S$, το σύνολο $S$ ικανοποιεί τις ακόλουθες απαιτήσεις:

• •

  είναι σχετικά μικρό σε σχέση με το σύνολο των ιστοσελίδων του παγκόσμιου ιστού,

• •

  περιέχει ιστοσελίδες που είναι σχετικές με το $Q$, και

• •

  περιέχει πολλές αξιόπιστες ιστοσελίδες (authorities) για το ερώτημα $Q$.

Με την υπόθεση ότι το σύνολο $S$ είναι διαθέσιμο, ο αλγόριθμος HITS λειτουργεί ως εξής. Αρχικά, για κάθε σελίδα $p$ αρχικοποιεί τις τιμές $as(p)$ (authority score) και $hs(p)$ (hub score) στην μονάδα. Στη συνέχεια ακολουθεί κανονικοποίηση των scores έτσι ώστε ${\sum }_{p\in S}as{(p)}^2=1$ και ${\sum }_{p\in S}hs{(p)}^2=1$. Ας υποθέσουμε ότι ο συμβολισμός $p\to q$ δηλώνει ότι η ιστοσελίδα $p$ έχει έναν σύνδεσμο προς την ιστοσελίδα $q$. Στη συνέχεια, ο αλγόριθμος HITS εκτελεί μία σειρά από επαναλήψεις και σε κάθε επανάληψη επαναπροσδιορίζονται οι τιμές $as(p)$ και $hs(p)$, $\forall p\in S$. Ο επαναπροσδιορισμός αυτός πραγματοποιείται σύμφωνα με τους ακόλουθους τύπους:

και

Η φυσική ερμηνεία των παραπάνω τύπων είναι ότι μία ιστοσελίδα $p$ αυξάνει την αξιοπιστία της όταν έχει εισερχόμενους συνδέσμους από κομβικές ιστοσελίδες (hubs) που έχουν υψηλό βαθμό κομβικότητας. Ομοίως, μία ιστοσελίδα αυξάνει το βαθμό κομβικότητας όταν έχει εξερχόμενους συνδέσμους σε ιστοσελίδες με υψηλό βαθμό αξιοπιστίας.

Στο Σχήμα 9.4 δίνεται ένα παράδειγμα επαναπροσδιορισμού των βαθμών αξιοπιστίας και κομβικότητας. Για τον επαναπροσδιορισμό του βαθμού αξιοπιστίας μίας ιστοσελίδας $u$ απαιτείται να γνωρίζουμε τους βαθμούς κομβικότητας για όλες τις σελίδες $q:q\to u$ όπως παρουσιάζεται στο Σχήμα 9.4(α). Στο παράδειγμα του σχήματος, η ιστοσελίδα $u$ έχει εισερχόμενους συνδέσμους από τις ιστοσελίδες $x$, $y$ και $z$. Επομένως, ο βαθμός αξιοπιστίας της $u$ θα είναι: $as(u)=hs(x)+hs(y)+hs(z)$. Αντίστοιχα, στο Σχήμα 9.4(β) δίνεται ο τρόπος υπολογισμού του τρέχοντος βαθμού κομβικότητας της ιστοσελίδας $u$: $hs(u)=as(x)+as(y)+as(z)$.

Στο Σχήμα 9.5 δίνεται ο ψευδοκώδικας του αλγορίθμου HITS που συνοψίζει τη διαδικασία που περιγράφηκε προηγουμένως. Παρατηρήστε ότι αλγόριθμος είναι επαναληπτικός και εκτελείται για $k$ επαναλήψεις. Σε κάθε επανάληψη, γίνεται ένας ακριβέστερος προσδιορισμός των βαρών. Με βάση αποτελέσματα από τη Γραμμική Άλγεβρα δεν είναι δύσκολο να αποδειχθεί ότι μετά από έναν ικανοποιητικό αριθμό επαναλήψεων το διάνυσμα που περιέχει τους βαθμούς αξιοπιστίας συγκλίνει στο σημαντικότερο ιδιοδιάνυσμα του πίνακα $A^{T}A$ ενώ το διάνυσμα που περιέχει τους βαθμούς κομβικότητας συγκλίνει στο σημαντικότερο ιδιοδιάνυσμα του πίνακα $A{A}^T$. Σημειώνεται ότι $A$ είναι ο πίνακας γειτνίασης, ο οποίος έχει διαστάσεις $|S|\times |S|$ και αποτελείται από άσσους και μηδενικά. Αν το στοιχείο που βρίσκεται στη γραμμή $i$ και τη στήλη $j$ είναι 1, σημαίνει ότι υπάρχει ένας σύνδεσμος από την $i$-οστή ιστοσελίδα προς την $j$-οστή σελίδα. Επίσης, $A^T$ είναι ο ανάστροφος πίνακας του $A$. Επομένως, οι βαθμοί αξιοπίστίας και κομβικότητας θα μπορούσαν να υπολογιστούν χρησιμοποιώντας αποτελέσματα της Γραμμικής Άλγεβρας (π.χ., λύνοντας συστήματα εξισώσεων). Ωστόσο, στην πράξη προτιμάται ο επαναληπτικός αλγόριθμος διότι τις περισσότερες φορές δεν απαιτείται πλήρης σύγκλιση ώστε να προσδιοριστούν οι βαθμοί ακριβώς. Επειδή μπορεί να υπάρχει ανοχή σε μικρές διαφοροποιήσεις, συνήθως το πλήθος των επαναλήψεων που ρυθμίζεται από την παράμετρο $k$ είναι σχετικά μικρό (π.χ., στην πράξη 20-30 επαναλήψεις είναι αρκετές για να έχουμε μία πολύ καλή προσέγγιση).

Το αποτέλεσμα του αλγορίθμου HITS είναι τα διανύσματα $as$ και $hs$ που περιέχουν τους βαθμούς αξιοπιστίας και κομβικότητας αντίστοιχα. Στη συνέχεια, θα πρέπει να επιλεγούν οι ιστοσελίδες που έχουν το μεγαλύτερο βαθμό αξιοπιστίας ως απάντηση στο ερώτημα $Q$. Επομένως, από τις $|S|$ ιστοσελίδες, επιλέγονται οι πρώτες $t$ ως προς το βαθμό αξιοπιστίας και επιστρέφονται στο χρήστη.

Το 1998 οι Brin και Page (ιδρυτές της Google) χρησιμοποίησαν μία διαφορετική τεχνική για τη βαθμολογία των ιστοσελίδων, η οποία είναι γνωστή στη βιβλιογραφία ως PageRank. Σε αντίθεση με τον αλγόριθμο HITS, ο αλγόριθμος PageRank δίνει σε κάθε ιστοσελίδα $p$ δίνεται έναν μόνο βαθμό $rank(p)$ που ποσοτικοποιεί το βαθμό αξιοπιστίας της ιστοσελίδας $p$. Επιπλέον, σε αντίθεση με τον αλγόριθμο HITS, ο αλγόριθμος PageRank εφαρμόζεται στο σύνολο του παγκόσμιου ιστού και όχι μόνο σε ένα υποσύνολο αυτού. Ωστόσο, ο βαθμός αξιοπιστίας μίας ιστοσελίδας δεν εξαρτάται από κάποιο συγκεκριμένο ερώτημα καθώς λαμβάνονται υπόψη μόνο οι σύνδεσμοι μεταξύ των ιστοσελίδων.

Ο αλγόριθμος PageRank αποτελεί προσομοίωση ενός τυχαίου περιπάτου (random walk) στο γράφημα που αναπαριστά τον παγκόσμιο ιστό. Στο Σχήμα 9.6 παρουσιάζεται τμήμα του παγκόσμιου ιστού που αποτελείται από πέντε ιστοσελίδες. Η τιμή που υπάρχει δίπλα σε κάθε σύνδεσμο αναπαριστά την πιθανότητα μετάβασης (transition probability). Έστω ότι ένας τυχαίος περιηγητής βρίσκεται στην ιστοσελίδα Α. Η ιστοσελίδα A έχει τρεις εξερχόμενους συνδέσμους που οδηγούν στις σελίδες B, D και E. Εφόσον ο περιηγητής θεωρείται τυχαίος, αυτό σημαίνει ότι δεν υπάρχει κάποια ιδιαίτερη προτίμηση σχετικά με την ιστοσελίδα που θα επισκεφθεί στη συνέχεια. Επομένως, η επιλογή είναι εντελώς τυχαία, και η τυχαιότητα αυτή δηλώνεται με την πιθανότητα επίσκεψης της κάθε ιστοσελίδας. Έτσι λοιπόν, από την ιστοσελίδα A ή ιστοσελίδα B έχει πιθανότητα επίσκεψης 1/3 και το ίδιο ισχύει για τις ιστοσελίδες D και E. Έστω τώρα ότι ο περιοηγητής βρίσκεται στην ιστοσελίδα C. Επειδή η C έχει μόνο έναν εξερχόμενο σύνδεσμο προς την ιστοσελίδα A, η πιθανότητα να επισκευθεί την A είναι 1, καθώς δεν υπάρχει άλλη επιλογή.

Οι πιθανότητες μετάβασης μπορούν να αναπαρασταθούν χρησιμοποιώντας τον πίνακα μεταβάσεων (transition matrix). Για το γράφημα του Σχήματος 9.6 ο πίνακας μεταβάσεων είναι ο ακόλουθος:

Στον πίνακα αυτόν, η σειρά των ιστοσελίδων είναι A, B, C, D και E. Επομένως, η πρώτη στήλη δείχνει ότι ένας περιηγητής που βρίσκεται στη ιστοσελίδα A στο επόμενο βήμα θα βρεθεί σε μία από τις ιστοσελίδες B, D ή E με την ίδια πιθανότητα 1/3. Η δεύτερη στήλη δείχνει ότι ένας περιηγητής που βρίσκεται στην ιστοσελίδα $B$ μπορεί να μεταβεί μόνο στην ιστοσελίδα C με πιθανότητα 1. Η τρίτη στήλη δείχνει ότι αν ο περιηγητής βρίσκεται στην ιστοσελίδα C θα βρεθεί στη σελίδα $A$ με πιθανότητα 1. Η τέταρτη στήλη αναφέρει ότι αν ο περιηγητής βρίσκεται στην ιστοσελίδα D θα μεταβεί είτε στη σελίδα C πιθανότητα 1. Τέλος, η πέμπτη στήλη αναφέρει ότι αν ο περιηγητής βρίσκεται στην ιστοσελίδα E τότε μπορεί να μεταβεί είτε στην ιστοσελίδα A ή D με την ίδια πιθανότητα 1/2. Παρατηρήστε ότι το άθροισμα των τιμών κάθε στήλης ισούται με 1.

Η κατανομή της πιθανότητας για τη ιστοσελίδα όπου θα βρεθεί ένας τυχαίος περιηγητής περιγράφεται με ένα διάνυσμα-στήλη, του οποίου το στοιχείο στη θέση $j$ είναι η πιθανότητα ο περιηγητής να βρεθεί στη $j$-οστή ιστοσελίδα. Η πιθανότητα αυτή είναι η τιμή της συνάρτησης που υλοποιεί ο αλγόριθμος PageRank. Έστω ότι ο περιηγητής ξεκινά την περιήγηση από μία οποιαδήποτε από τις $n$ ιστοσελίδες με την ίδια πιθανότητα. Τότε, το αρχικό διάνυσμα ${𝐯}_0$ θα έχει την τιμή 1/$n$ σε όλες τις θέσεις. Εάν $M$ είναι ο πίνακας μεταβάσεων, τότε μετά από ένα βήμα η κατανομή της πιθανότητας γίνεται $M{𝐯}_0$, μετά από δύο βήματα η κατανομή θα είναι $M(M{𝐯}_0)=M^2{𝐯}_0$ κ.λ.π. Γενικά, πολλαπλασιάζοντας το αρχικό διάνυσμα ${𝐯}_0$ με τον πίνακα $M$ συνολικά $i$ φορές, παίρνουμε την κατανομή μετά από $i$ βήματα.

Ας δούμε στη συνέχεια για ποιό λόγο πολλαπλασιάζοντας το διάνυσμα $𝐯$ με τον πίνακα $M$ παίρνουμε την κατανομή του επόμενου βήματος. Η πιθανότητα ${𝐱}_i$ ένας περιηγητής να βρεθεί στην ιστοσελίδα $i$ στο επόμενο βήμα είναι ${\sum }_j{m}_{ij}{𝐯}_j$, όπου $m_{ij}$ είναι η πιθανότητα ο περιηγητής που βρίσκεται στην ιστοσελίδα $j$ να μεταβεί στο επόμενο βήμα στην ιστοσελίδα $i$ και ${𝐯}_j$ είναι η πιθανότητα ο περιηγητής να βρίσκεται στην ιστοσελίδα $j$ στο προηγούμενο βήμα.

Η συμπεριφορά αυτή αποτελεί ένα παράδειγμα εφαρμογής της θεωρίας των διεργασιών Markov. Είναι γνωστό ότι η κατανομή πιθανότητας για έναν περιηγητής προσεγγίζει την οριακή κατανομή $𝐯$ που ικανοποιεί τη σχέση $𝐯=M𝐯$, με την προϋπόθεση ότι ικανοποιούνται οι ακόλουθες απαιτήσεις:

• •

  ο γράφος είναι ισχυρά συνεκτικός, που σημαίνει ότι για κάθε ζεύγος ιστοσελίδων $u,v$ μπορούμε να μεταβούμε από την $u$ στην $v$.

• •

  δεν υπάρχουν ιστοσελίδες χωρίς εξερχόμενους συνδέσμους.

Παρατηρήστε ότι το γράφημα του Σχήματος 9.6 ικανοποιεί και τις δύο συνθήκες.

Η οριακή κατάσταση επιτυγχάνεται όταν δεν έχουμε αλλαγή στην κατανομή μετά από πολλαπλασιασμό με τον πίνακα $M$. Με άλλα λόγια, το διάνυσμα $𝐯$ που περιγράφει την κατανομή στην οριακή κατάσταση είναι ένα ιδιοδιάνυσμα του πίνακα $M$ (ένα ιδιοδιάνυσμα $𝐯$ του $M$ ικανοποιεί τη σχέση $𝐯=\lambda M𝐯$ για κάποια τιμή $\lambda$ που ονομάζεται ιδιοτιμή). Επειδή ο πίνακας $M$ είναι στοχαστικός, που σημαίνει ότι το άθροισμα των τιμών της κάθε στήλης είναι 1, το διάνυσμα $𝐯$ είναι το κύριο ιδιοδιάνυσμα (αντιστοιχεί δηλαδή στη μεγαλύτερη ιδιοτιμή του πίνακα). Επίσης, λόγω της στοχαστικότητας του $M$, γνωρίζουμε ότι η ιδιοτιμή που αντιστοιχεί στο κύριο ιδιοδιάνυσμα είναι 1.

Το κύριο ιδιοδιάνυσμα του $M$ καταγράφει την πιθανότητα ο περιηγητής να βρεθεί σε κάθε ιστοσελίδα μετά από ένα αρκετά μεγάλο χρονικό διάστημα. Σημειώνεται ότι διαίσθηση πίσω από τη μέθοδο PageRank είναι ότι όσο πιθανότερο είναι ο περιηγητής να βρεθεί σε μία ιστοσελίδα, τόσο σημαντικότερη θεωρείται η ιστοσελίδα αυτή. Ο υπολογισμός του κύριου ιδιοδιανύσματος μπορεί να γίνει με διαδοχικούς πολλαπλασιασμούς του διανύσματος ${𝐯}_0$ με τον πίνακα $M$. Η διαδικασία τερματίζεται όταν η διαφορά του επόμενου από το προηγούμενο διάνυσμα είναι πολύ μικρή. Στην πράξη, για την περίπτωση του παγκόσμιου ιστού, 50-100 επαναλήψεις είναι αρκετές για να συγκλίνει ο αλγόριθμος.

Θα εφαρμόσουμε την προηγούμενη διαδικασία για το γράφημα του Σχήματος 9.6. Το αρχικό διάνυσμα βαθμών ${𝐯}_0$ περιέχει σε όλες τις θέσεις την τιμή 1/5. Το αποτέλεσμα των διαδοχικών πολλαπλασιασμών με τον πίνακα μεταβάσεων $\mathrm{{\rm M}}$ έχει ως εξής:

Ο αναγνώστης μπορεί να παρατηρήσει τη μεταβολή των τιμών και την τάση για σύγκλιση. Φυσικά ο αριθμός των επαναλήψεων που απαιτούνται εξαρτάται άμεσα από την ακρίβεια που χρησιμοποιούμε. Στην πράξη, η πλήρης σύγκλιση επιτυχγάνεται όταν δεν υπάρχει μεταβολή των τιμών λαμβάνοντας υπόψη την ακρίβεια των πραγματικών αριθμών διπλής ακρίβειας. Στο παράδειγμα αυτό χρησιμοποιήθηκαν τέσσερα ψηφία μετά την υποδιαστολή.

Στο κεφάλαιο αυτό μελετήσαμε θέματα που αφορούν στην αναζήτηση πληροφορίας στον παγκόσμιο ιστό. Συγκεκριμένα, εξετάσαμε τις προκλήσεις που επιφέρει ο παγκόσμιος ιστός στην Ανάκτηση Πληροφορίας και μελετήσαμε αναλυτικά τους αλγορίθμους προσδιορισμού του βαθμού αξιοπιστίας των ιστοσελίδων HITS και PageRank. Ο ενδιαφερόμενος αναγνώστης μπορεί να μελετήσει την εργασία του Kleinberg στην οποία μελετήθηκε για πρώτη φορά ο αλγόριθμος HITS [34].Επίσης, αξίζει να μελετηθούν και οι εργασίες [5] και [46] όπου αναλύεται ο αλγόριθμος PageRank και τα βασικά τμήματα της μηχανής αναζήτησης της Google. Επίσης, τα βιβλία [6, 8] αποτελούν πολύ σημαντικά βοηθήματα για την Ανάκτηση Πληροφορίας στον παγκόσμιο ιστό και τις μηχανές αναζήτησης.

• 9.1

  Ποιές είναι οι βασικές προκλήσεις που επιφέρει ο παγκόσμιος ιστός στη λειτουργία των μηχανών αναζήτησης;

• 9.2

  Ποιά είναι τα βασικά τμήματα από τα οποία αποτελείται μία μηχανή αναζήτησης;

• 9.3

  Να εξηγήσετε τους λόγους για τους οποίους οι πρώιμες μηχανές αναζήτησης δεν επαρκούσαν για τις πληροφοριακές ανάγκες των χρηστών.

• 9.4

  Πως λειτουργεί ο αλγόριθμος HITS και ποιά η χρησιμότητά του;

• 9.6

  Πως λειτουργει ο αλγόριθμος PageRank;

• 9.7

  Ποιές οι βασικές διαφορές των αλγορίθμων HITS και PageRank;

• 9.8

  Να κατασκευάσετε ένα γράφημα με τέσσερις κορυφές και με ένα αδιέξοδο και να υπολογίσετε το διάνυσμα των βαθμών σύμφωνα με τον αλγόριθμο PageRank. Ποιές είναι οι παρατηρήσεις σας;

• 9.9

  Να υλοποιήσετε τον αλγόριθμο PageRank σε μία γλώσσα προγραμματισμού και να τον δοκιμάσετε για διαφορετικές τιμές της παραμέτρου $\alpha$ σε γραφήματα που θα βρείτε στον ιστότοπο http://snap.stanford.edu.

• 9.10

  Να σχεδιάσετε μία μέθοδο η οποία θα μπορεί να ”ξεγελάσει” τον αλγόριθμο PageRank και θα δίνει με τεχνητό τρόπο μεγαλύτερο βαθμό σε συγκεκριμένες ιστοσελίδες.