Ο αλγόριθμος PageRank

Ο αλγόριθμος PageRank Φανταστείτε ότι ψάχνετε για την πιο δημοφιλή και αξιόπιστη σελίδα στο διαδίκτυο. Ο αλγόριθμος PageRank βοηθά να βρούμε ποιες σελίδες είναι πιο «σημαντικές». Πώς Λειτουργεί; Ο αλγόριθμος στηρίζεται στις παρακάτω παραδοχές: Κάθε σελίδα στο διαδίκτυο μπορεί να συνδέεται με άλλες σελίδες. Αυτοί οι σύνδεσμοι είναι σαν ψήφοι εμπιστοσύνης. Όσο περισσότερες σελίδες συνδέονται με μία συγκεκριμένη σελίδα, τόσο πιο σημαντική θεωρείται. Όμως, δεν έχουν όλοι οι ψήφοι την ίδια αξία! Αν μια σελίδα που ήδη θεωρείται πολύ σημαντική συνδέεται με μια άλλη, τότε της δίνει μεγαλύτερη βαρύτητα. Ένα Απλό Παράδειγμα Ας προσπαθήσουμε να κατανοήσουμε τη λειτουργία του με τη βοήθεια του παρακάτω παραδείγματος: Έστω ότι υπάρχουν 4 ιστοσελίδες: Α, Β, C και D. Η Α έχει συνδέσμους προς τις Β και C. Η Β έχει σύνδεσμο προς την D. Η C έχει συνδέσμους προς τις A, B, D. Η D έχει σύνδεσμο προς την C. Αρχικά, ο PageRank θεωρεί ότι όλες οι σελίδες έχουν την ίδια σημασία. Για παράδειγμα, αν υπάρχουν 4 σελίδες, η κάθε μία ξεκινά με βαθμολογία 1/4 (25%). Πώς υπολογίζεται η νέα βαθμολογία; Ο PageRank υπολογίζει τη σημασία μιας σελίδας με βάση: Πόσες άλλες σελίδες συνδέονται προς αυτήν (εισερχόμενοι σύνδεσμοι). Πόσο σημαντικές είναι αυτές οι σελίδες. Πόσους εξερχόμενους συνδέσμους έχει κάθε σελίδα (αν μια σελίδα συνδέεται με πολλές άλλες, ο κάθε σύνδεσμος της δίνει μικρότερη βαρύτητα). Κάθε σελίδα μοιράζει το PageRank της στις σελίδες προς τις οποίες συνδέεται. 1ος Γύρος Υπολογισμού Όλες οι σελίδες ξεκινούν με 1/4 (ή 0.25). Η A μοιράζει το PageRank της στις δύο σελίδες που συνδέεται (B και C). Άρα κάθε μία παίρνει 0.25/2 = 0.125 από την A. Η B έχει σύνδεσμο μόνο προς την D, άρα όλο το PageRank της (0.25) πάει στη D. Η C έχει συνδέσμους προς A, B, D. Άρα κάθε μία από αυτές παίρνει 0.25/3 = 0.0833 από την C. Η D έχει σύνδεσμο μόνο προς την C, άρα όλο το PageRank της (0.25) πάει στη C. Μετά τον 1ο γύρο οι νέες βαθμολογίες είναι: A = 0.0833 B = 0.125 + 0.0833 = 0.2083 C = 0.125 + 0.25 = 0.375 D = 0.25 + 0.0833 = 0.3333 2ος Γύρος Υπολογισμού Τώρα επαναλαμβάνουμε τη διαδικασία με τις νέες τιμές. A λαμβάνει PageRank από C (που είχε 0.375). Επειδή η C έχει 3 συνδέσμους, δίνει στην A 0.375/3 = 0.125. B λαμβάνει από A (0.0833/2 = 0.0417) και από C (0.375/3 = 0.125). Άρα νέο PageRank της B: 0.1667. C λαμβάνει από D (0.3333/1 = 0.3333) και από A (0.0833/2 = 0.0417). Άρα νέο PageRank της C: 0.375. D λαμβάνει από B (0.1667) και από C (0.375/3 = 0.125). Άρα νέο PageRank της D: 0.2917. Τελική Κατάταξη των Σελίδων Μετά από αρκετές επαναλήψεις, οι βαθμολογίες σταθεροποιούνται: C = 0.40 D = 0.30 B = 0.20 A = 0.10 Αυτό σημαίνει ότι η C είναι η πιο σημαντική σελίδα, επειδή έχει πολλούς εισερχόμενους συνδέσμους από σελίδες που θεωρούνται επίσης σημαντικές. Τι καταλαβαίνουμε; Για να είναι μια σελίδα σημαντική: Πρέπει να τη συστήνουν πολλές άλλες σελίδες. Πρέπει να τη συστήνουν σελίδες που είναι ήδη δημοφιλείς. Πρέπει και η ίδια να συστήνει άλλες σελίδες. Έτσι, με τη χρήση του PageRank καθορίζεται ποιες σελίδες θα εμφανίζονται πρώτες στα αποτελέσματα αναζήτησης.