Αλγόριθμος κατάταξης συνδέσμων PageRank και γραμμική άλγεβρα. Αλγόριθμοι κατάταξης Yandex: ιστορικό ανάπτυξης Αλγόριθμοι κατάταξης Yandex

Το PageRank είναι μια αριθμητική τιμή που χαρακτηρίζει τη «σημασία» της ιστοσελίδας ενός ιστότοπου. Όσο περισσότεροι σύνδεσμοι οδηγούν σε μια σελίδα ιστότοπου και όσο υψηλότερη είναι η ποιότητα τους, τόσο πιο «σημαντική» γίνεται η σελίδα. Επιπλέον, το «βάρος» της σελίδας Α καθορίζεται από το βάρος του συνδέσμου που μεταδίδεται από τη σελίδα Β. Έτσι, το PageRank είναι μια μέθοδος υπολογισμού του βάρους μιας σελίδας με τον υπολογισμό της σημασίας των συνδέσμων προς αυτήν.

Αυτή η μέθοδος υπολογισμού κατοχυρώθηκε με δίπλωμα ευρεσιτεχνίας από τους προγραμματιστές και συνιδρυτές της μηχανής αναζήτησης Google Sergey Brin και Larry Page. Διαβάστε αναλυτικότερα το κείμενο της μελέτης (στα αγγλικά). Στα ρώσικα .

Τι είναι το βάρος σελίδας ιστότοπου;

Κάτω από το βάρος της σελίδας είναι ο βαθμός σημασίας της. Αν κάνουμε μια αναλογία με τις ανθρώπινες σχέσεις, τότε η φράση «η λέξη του έχει βάρος» θα αντικατοπτρίζει την ουσία της έννοιας «βάρος σελίδας ιστότοπου».

Το βάρος της σελίδας εκφράζεται σε συγκεκριμένους αριθμούς και μπορεί να υπολογιστεί.

Συμβατικά, υπάρχουν δύο τύποι βάρους σελίδας:

1. Στατικό βάρος (ένας ορισμένος αριθμός), το οποίο υπολογίζεται με βάση παράγοντες ανεξάρτητους από το ερώτημα - αυτοί είναι όλοι παράγοντες που δεν σχετίζονται με το ερώτημα αναζήτησης. Για παράδειγμα, η ηλικία του ιστότοπου, οι σελίδες του, η ημερομηνία ευρετηρίασης των σελίδων, ο αριθμός των εσωτερικών και εξωτερικών συνδέσμων που οδηγούν στη σελίδα.
2. Δυναμικό βάρος, το οποίο υπολογίζεται με βάση παράγοντες που εξαρτώνται από το ερώτημα - αυτοί είναι όλοι οι παράγοντες που σχετίζονται με το ερώτημα αναζήτησης (κείμενο). Το κείμενο αιτήματος συγκρίνεται με το κείμενο της σελίδας του ιστότοπου, επομένως, παράγοντες που εξαρτώνται από το αίτημα είναι αυτοί που εξαρτώνται κυρίως από τα στοιχεία κειμένου της σελίδας - τίτλος τίτλος, περιγραφή περιγραφής, κείμενο σε αυτό, άγκυρες (κείμενα) συνδέσμων που δείχνουν σε αυτό και προέρχονται από αυτό.

Ο αλγόριθμος PageRank καθορίζει το στατικό βάρος μιας σελίδας και όχι το δυναμικό. Με άλλα λόγια, το στατικό βάρος μιας σελίδας είναι το PageRank της. Μπορεί να υπάρχει μια σελίδα στον ιστότοπο χωρίς περιεχόμενο, αλλά αν τουλάχιστον ένας σύνδεσμος οδηγεί σε αυτήν, τότε θα έχει στατικό βάρος.

Το στατικό βάρος θεωρείται από τις μηχανές αναζήτησης στο παρασκήνιο και εκχωρείται στη σελίδα του ιστότοπου. Μετά από ορισμένο χρόνο υπολογίζεται εκ νέου. Το δυναμικό βάρος δεν υπολογίζεται στο παρασκήνιο, αλλά εν κινήσει όταν ο χρήστης υποβάλλει ένα ερώτημα αναζήτησης στη μηχανή αναζήτησης για να βρει αποτελέσματα.

Πώς μοιάζει ο τύπος PageRank;

Κανείς δεν γνωρίζει πώς ακριβώς υπολογίζει η Google το PageRank. Αλλά μπορείτε να εστιάσετε σε αυτή τη φόρμουλα που προτείνουν οι Sergey Brin και Larry Page στη μελέτη τους.

PR(A)=(1-d)+d(PR(T_1)/C(T_1) +⋯+PR(T_n)/C(T_n)) , Οπου

PR(A) - βάρος της σελίδας αποδοχής Α (προς την οποία τοποθετείται ο σύνδεσμος)

PR(T_n) - βάρος της σελίδας δότη που συνδέεται με τη σελίδα Α (από την οποία τοποθετείται ο σύνδεσμος)

C(T_n) - αριθμός συνδέσμων από τη σελίδα δότη

D είναι ο συντελεστής εξασθένησης, που συνήθως λαμβάνεται ίσος με 0,85. Στο πιθανοτικό μοντέλο, υπονοεί ότι ο χρήστης δεν θα ακολουθήσει καθόλου τον σύνδεσμο, αλλά θα κλείσει τη σελίδα του ιστότοπου. Σε αυτό το γεγονός αποδόθηκε πιθανότητα 15%. Το υπόλοιπο 85% δίνεται σε συνδέσμους.

Το 1-d είναι ένα στοιχείο που απαιτείται για να διασφαλιστεί ότι ο τύπος δεν θα γίνει μηδενικός εάν το βάρος των σελίδων δότη σύνδεσης είναι ίσο με 0. Αυτό σημαίνει ότι ακόμη και η πιο ασήμαντη σελίδα στον ιστότοπο μπορεί να μεταδώσει κάποιο ελάχιστο βάρος μέσω του συνδέσμου .

Ο τύπος μπορεί να γραφτεί ως εξής

Το βάρος της σελίδας αποδοχής του ιστότοπου είναι ίσο με το άθροισμα των βαρών που μεταδίδονται μέσω συνδέσμων από τις σελίδες δωρητή στη σελίδα αποδοχής.

Παράδειγμα

Εάν ένας ιστότοπος προωθείται στον τομέα της πώλησης ρολό, τότε πρέπει να βρούμε σελίδες σε ιστότοπους χορηγών με υψηλό PageRank. Κατά την προβολή, δεν αναλύω την τιμή PageRank κάθε σελίδας του ιστότοπου με τον οποίο θέλω να πραγματοποιήσω επικοινωνία, επειδή... μια τέτοια σελίδα μπορεί να βρίσκεται σε ανεπιθύμητο ιστότοπο. Επικεντρώνομαι στο θέμα της σελίδας δωρητή και ότι μια τέτοια σελίδα βρίσκεται στη μηχανή αναζήτησης TOP 10 για ερωτήματα θεματικών πληροφοριών που σχετίζονται με το προϊόν/υπηρεσία που προωθείται και στους δείκτες με τους οποίους ελέγχω κάθε ιστότοπο δυνητικού δωρητή πριν γράψω μια πρόταση στον ιδιοκτήτη του ή στον υπεύθυνο για την ανάρτηση υλικού σε αυτό, σχετικά με τη δημοσίευση ενός συνδέσμου ή αναφοράς.

Εάν μια σελίδα βρίσκεται στην πρώτη σελίδα των αποτελεσμάτων αναζήτησης, τότε ο αλγόριθμος αναζήτησης τη θεώρησε υψηλής ποιότητας για να βρίσκεται στο TOP 10 για το ερώτημα αναζήτησης που μας ενδιαφέρει. Θα πρέπει να προσπαθήσετε να πάρετε έναν ενεργό σύνδεσμο ή αναφορά από μια τέτοια σελίδα, γιατί έχει ήδη επισκεψιμότητα από την αναζήτηση και ένας σύνδεσμος που τοποθετείται σε μια τέτοια σελίδα θα έχει μεγάλη πιθανότητα να ακολουθηθεί από τους χρήστες λόγω του ότι βρίσκεται στην TOP.

Κυκλοφόρησε ένα νέο βιβλίο, το Social Media Content Marketing: How to Get Inside Your Followers' Heads and Make Them Fall Fall with Your Brand.

Αλγόριθμοι κατάταξης - μέθοδοι αξιολόγησης της ποιότητας των τοποθεσιών

Το TOP 10 θα πρέπει να περιλαμβάνει μόνο εκείνους τους ιστότοπους που απαντούν στο αίτημα του χρήστη όσο το δυνατόν πληρέστερα. Τα αποτελέσματα υψηλής ποιότητας διασφαλίζονται από ειδικούς μαθηματικούς τύπους που καθορίζουν τη «χρησιμότητα» ενός συγκεκριμένου ιστότοπου. Οι μηχανές αναζήτησης δεν αποκαλύπτουν πληροφορίες σχετικά με τους αλγόριθμους τους, παρέχουν στους webmasters μόνο γενικές συστάσεις για τη βελτίωση και τη βελτιστοποίηση ιστότοπων. Ωστόσο, οι βελτιστοποιητές έχουν μάθει να εντοπίζουν ορισμένα πρότυπα βάσει των οποίων αναπτύσσεται μια στρατηγική.

κίνηση.

Περισσότερα βίντεο στο κανάλι μας - μάθετε το διαδικτυακό μάρκετινγκ με τη SEMANTICA

Ποια κριτήρια λαμβάνει υπόψη ο αλγόριθμος κατάταξης;

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

• μοναδικότητα και βελτιστοποίηση κειμένων (παρουσία φράσεων κλειδιά, ναυτία, περιεκτικότητα σε νερό).
• Ηλικία τομέα?
• την ποσότητα και την ποιότητα των εισερχόμενων συνδέσμων.
• τύπος CMS που χρησιμοποιείται.
• ταχύτητα φόρτωσης σελίδας ιστότοπου.
• παρουσία σφαλμάτων στον κώδικα.

Κατανοώντας πώς λειτουργεί ο αλγόριθμος της μηχανής αναζήτησης, ένας webmaster μπορεί να επηρεάσει την κατάταξη του ιστότοπού του. Για να γίνει αυτό, είναι απαραίτητο να «προσαρμόσετε» τις σελίδες του έργου web στις απαιτήσεις του PS. Συγκεκριμένα, θα χρειαστεί να ενσωματώσετε φράσεις κλειδιά στις μετα-ετικέτες τίτλου και περιγραφής, καθώς και απευθείας στο κείμενο της σελίδας. Εάν κάνετε προώθηση με βάση ένα αίτημα γεωγραφικής εξάρτησης, τότε, εκτός από τα κλειδιά, θα πρέπει να προσθέσετε και το όνομα της επιθυμητής πόλης ή περιοχής.

Αυτό είναι ενδιαφέρον! Η μηχανή αναζήτησης αναβαθμίζεται περιοδικά, γεγονός που οδηγεί σε ριζική αλλαγή στους υπάρχοντες αλγόριθμους. Τέτοια μέτρα αποσκοπούν στην καταπολέμηση των ανεπιθύμητων μηνυμάτων αναζήτησης. Συχνά, μια αλλαγή στον αλγόριθμο Yandex οδηγεί σε επιδείνωση των θέσεων των τοποθεσιών που προωθούνται με μεθόδους "μαύρες" και "γκρίζες".

Κυρώσεις αναζήτησης

Εάν ένας webmaster προσπαθεί ξεκάθαρα να χειραγωγήσει τους αλγόριθμους Yandex, τότε η μηχανή αναζήτησης μπορεί να του επιβάλει διάφορες κυρώσεις. Μπορεί να προκύψουν τα ακόλουθα προβλήματα:

• Χαμηλότερη κατάταξη στα αποτελέσματα αναζήτησης
• Κακή ευρετηρίαση νέων σελίδων (ή απώλεια παλαιών εγγράφων από το ευρετήριο)
• Πλήρης ή μερική ΑΠΑΓΟΡΕΥΣΗ

Οι αλγόριθμοι Yandex επιβάλλουν κυρώσεις για υπερβολική βελτιστοποίηση κειμένων, για παράδειγμα, για δημοσίευση λιστών με φράσεις-κλειδιά σε σελίδες. Το φίλτρο μπορεί να εφαρμοστεί για να αναμειχθεί το "αόρατο" κείμενο στο φόντο. Επίσης υπόκεινται σε κυρώσεις οι ιστότοποι και οι πλατφόρμες του Διαδικτύου που αντιγράφουν περιεχόμενο άλλων ανθρώπων.

Νέος αλγόριθμος Yandex – Minusinsk

Αυτός ο αλγόριθμος περιλαμβάνει την απαισιοδοξία ενός έργου web για τη χρήση συνδέσμων SEO. Μιλάμε για ιστότοπους που αγοράζουν χιλιάδες συνδέσμους χρησιμοποιώντας αυτοματοποιημένες ανταλλαγές όπως το Sape. Από την άποψη της Yandex, ένας σύνδεσμος θεωρείται "SEO" εάν οδηγεί από έναν ιστότοπο δωρητών χαμηλής ποιότητας και έχει εμπορική άγκυρα.

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

Σύνολο

Για πολύ μεγάλο χρονικό διάστημα, οι αλγόριθμοι κατάταξης Yandex παρέμειναν «μυστικό» για τους χρήστες. Οι ειδικοί των μηχανών αναζήτησης Yandex προτίμησαν να μην ενημερώνουν τους χρήστες του Διαδικτύου για αλλαγές στους αλγόριθμους κατάταξης.

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

1 2007

Και μόνο το 2007, οι υπάλληλοι της Yandex άρχισαν να ενημερώνουν τους χρήστες τους για την εισαγωγή καινοτομιών στον αλγόριθμο αναζήτησης. Αυτό κάνει την προώθηση ιστότοπου λίγο πιο εύκολη για πολλούς webmasters.

Αξίζει να σημειωθεί ότι οι αλγόριθμοι κατάταξης Yandex αλλάζουν συνεχώς. Χάρη σε αυτές τις αλλαγές, προστίθεται νεότερη και πιο προηγμένη λειτουργικότητα, η οποία κάνει την εργασία με αυτήν τη μηχανή αναζήτησης πολύ πιο εύκολη. Επίσης, χάρη στις αλλαγές στους αλγόριθμους κατάταξης, τα σφάλματα εξαλείφονται, τα φίλτρα και οι περιοριστές ενημερώνονται και η ακριβέστερη παράδοση των πληροφοριών προσαρμόζεται ώστε να ταιριάζει καλύτερα με το αρχικό αίτημα.

2 Μαΐου 2008

Τον Μάιο του 2008, οι ειδικοί της Yandex κυκλοφόρησαν έναν νέο αλγόριθμο που ονομάζεται "Magadan".

Αλγόριθμος Magadan

Σε αυτόν τον αλγόριθμο, ο αριθμός των παραγόντων κατάταξης έχει διπλασιαστεί και ο ταξινομητής με βάση την τοποθεσία του χρήστη (γεωστόχευση) έχει βελτιωθεί σημαντικά. Επίσης στον αλγόριθμο Magadan υπάρχουν τέτοιες καινοτόμες λύσεις όπως η προσθήκη ταξινομητών για περιεχόμενο και συνδέσμους. Η ταχύτητα της μηχανής αναζήτησης στην αναζήτηση πληροφοριών με βάση τα εισαγόμενα βασικά ερωτήματα έχει αυξηθεί σημαντικά (χάρη σε αυτόν τον αλγόριθμο, η μηχανή αναζήτησης είναι σε θέση να παρέχει πληροφορίες ακόμη και με κείμενα που έχουν προεπαναστατική ορθογραφία).

Τον Ιούλιο του ίδιου έτους, κυκλοφόρησε μια νέα έκδοση του αλγορίθμου Magadan, η οποία περιελάμβανε πρόσθετους παράγοντες κατάταξης, για παράδειγμα, τον προσδιορισμό της μοναδικότητας του κειμένου και των πληροφοριών, τον προσδιορισμό του αν το περιεχόμενο είναι πορνογραφικό κ.λπ.

3 Σεπτεμβρίου 2008

Ήδη τον Σεπτέμβριο του 2008, η εταιρεία Yandex κυκλοφόρησε έναν νέο αλγόριθμο που ονομάζεται "Nakhodka".

Χάρη στην εμφάνιση αυτού του αλγορίθμου, η εργασία με λεξικά στο σύστημα αναζήτησης Yandex έχει βελτιωθεί σημαντικά και η ποιότητα της κατάταξης για ερωτήματα που περιέχουν λέξεις διακοπής (συνδέσεις και προθέσεις) έχει αυξηθεί σημαντικά. Επίσης, σε αυτόν τον αλγόριθμο, αναπτύχθηκε μια εντελώς νέα προσέγγιση στη μηχανική μάθηση (η μηχανή άρχισε να διακρίνει μεταξύ διαφορετικών ερωτημάτων και άρχισε να αλλάζει τους παράγοντες κατάταξης για διαφορετικά ερωτήματα στον τύπο υπολογισμού για τα αποτελέσματα αναζήτησης).

4 Απριλίου 2009

Ένας νέος αλγόριθμος που ονομάζεται "Arzamas" ή "Anadyr" δημοσιεύτηκε στη μηχανή αναζήτησης Yandex τον Απρίλιο του 2009.

Αλγόριθμος Arzamas

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

Θα πρέπει να σημειωθεί ότι σε διαφορετικές περιοχές οι πληροφορίες που παρέχονται είναι επίσης διαφορετικές, παρά το ίδιο ερώτημα που έχει εισαχθεί από τον χρήστη. Επίσης σε αυτόν τον αλγόριθμο αναζήτησης η φόρμουλα έχει βελτιωθεί σημαντικά, γεγονός που καθιστά πιο βολική την εργασία με ερωτήματα πολλαπλών λέξεων. Εισήχθησαν πιο αυστηρά φίλτρα για σελίδες με banner popunder (το banner Pop-Under εμφανίζεται σε όλες τις σελίδες του ιστότοπου και δεν σχετίζεται με το θέμα του ιστότοπου), clickander (διαφήμιση κλικ κάτω που εμφανίζεται στη σελίδα όταν ο επισκέπτης κάνει πρώτο κλικ) και bodyclic (Bodyclic - υπηρεσία διαφήμισης teaser).

5 Νοεμβρίου 2009

Τον Νοέμβριο του 2009, κυκλοφόρησε ένας νέος αλγόριθμος, ο οποίος ονομάζεται "Snezhinsk".

Αλγόριθμος Snezhinsk

Αυτός ο αλγόριθμος εισάγει πρόσθετες λειτουργίες και παραμέτρους κατάταξης που σας επιτρέπουν να εφαρμόσετε πολλές χιλιάδες παραμέτρους αναζήτησης για ένα μόνο έγγραφο. Επίσης σε αυτόν τον αλγόριθμο, εισήχθησαν νέες τοπικές παράμετροι (φίλτρα για ιστότοπους που προσπαθούν σκόπιμα να επηρεάσουν τα αποτελέσματα αναζήτησης, απλούστερος ιστότοπος κατά των σκατά) και βελτιώθηκε σημαντικά η αναζήτηση πρωτότυπου περιεχομένου στο Διαδίκτυο. Αυτός ο αλγόριθμος περιελάμβανε επίσης το σύστημα αυτομάθησης MatrixNet.

6 Δεκεμβρίου 2009

Τον Δεκέμβριο του 2009, εμφανίστηκε ένας νέος αλγόριθμος που ονομάζεται "Konakovo".

Αυτός ο αλγόριθμος ήταν απλώς μια βελτιωμένη έκδοση του αλγορίθμου Snezhinsk και βελτιώθηκε μόνο η τοπική κατάταξη. Τον Σεπτέμβριο του 2010, κυκλοφόρησε ένας νέος αλγόριθμος "Obninsk". Σε αυτόν τον αλγόριθμο, η κατάταξη για εδαφικά ανεξάρτητα ερωτήματα βελτιώθηκε και εισήχθη ένας περιορισμός στην επίδραση των τεχνητών συνδέσμων στην κατάταξη. Επίσης, χάρη σε αυτόν τον αλγόριθμο, η διαδικασία προσδιορισμού του κειμένου του συγγραφέα έχει βελτιωθεί σημαντικά και το λεξικό μεταγραφής έχει επεκταθεί σημαντικά.

7 2010

Τον Δεκέμβριο του 2010, κυκλοφόρησε ένας νέος αλγόριθμος που ονομάζεται "Krasnodar".

Για τη δημιουργία αυτού του αλγόριθμου, αναπτύχθηκε ειδικά μια νέα τεχνολογία που ονομάζεται Spectrum. Χάρη σε αυτόν τον αλγόριθμο, η μηχανή αναζήτησης Yandex άρχισε να ταξινομεί ερωτήματα και να επιλέγει αντικείμενα από αυτά, εκχωρώντας στα ερωτήματα μια συγκεκριμένη κατηγορία (προϊόντα, υπηρεσίες κ.λπ.).

8 2014

Άλλος ένας δολοφόνος πυροβολισμός από το Yandex - Οι αλγόριθμοι κατάταξης Yandex δεν θα λαμβάνουν πλέον υπόψη τους συνδέσμους κατά την κατάταξη. Σύμφωνα με τις τελευταίες ανακοινώσεις, η κατάταξη χωρίς σύνδεση θα ξεκινήσει στις αρχές του 2014. Το Yandex θα αφαιρέσει όλους τους παράγοντες σύνδεσης από τους παράγοντες κατάταξης. Αυτή η καινοτομία θα επηρεάσει μόνο εμπορικά αιτήματα και θα δοκιμαστεί πρώτα στη Μόσχα και στην περιοχή της Μόσχας. Συγγραφείς καινοτομιών, δημιουργοί του AGS Yandex.

Εκτός από τα γραφικά και τα θεωρητικά συνόλων, συχνά χρησιμοποιούν αλγεβρική αναπαράστασηγράφημα σε μορφή μήτρας.

Σκεφτείτε το δίγραμμα σολπου περιέχει nκορυφές και Μπαϊδάκια Πίνακας γειτνίασηςδίφθογγος σολονομάζεται μήτρα ΕΝΑΜέγεθος n n

Μερικές φορές καλείται ο πίνακας γειτνίασης μήτρα σχέσεων, ή μήτρα άμεσων συνδέσεων.

Πίνακας επίπτωσης(ή μήτρα συμβάντων) διγράφημα σολονομάζεται μήτρα σιΜέγεθος n Μ, στο οποίο

Για να εισαγάγετε τον πίνακα γειτνίασης, πρέπει να αριθμήσετε τις κορυφές και για τον πίνακα πρόσπτωσης, τις άκρες του γραφήματος.

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

Ας εξετάσουμε τώρα μερικές μεθόδους για την επίλυση πρακτικών προβλημάτων χρησιμοποιώντας τον μαθηματικό φορμαλισμό που εισαγάγαμε.

Κατάταξη των στοιχείων του συστήματος

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

Η εύρεση μονοπατιών χρησιμοποιώντας ένα σχέδιο με σύνθετη δομή γραφήματος (στην πράξη, πρέπει να αναλύσετε γραφήματα με περισσότερες από 100 κορυφές) είναι δύσκολη και σχετίζεται με την πιθανότητα σφαλμάτων. Ας εξετάσουμε μια από τις αλγεβρικές μεθόδους που είναι βολική για χρήση σε υπολογιστή. Αυτή η μέθοδος επιτρέπει, με βάση τη μήτρα των άμεσων συνδέσεων , χτίζω πλήρης πίνακας διαδρομής
, Οπου - αριθμός διαδρομών από την κορυφή Εγώστην κορυφή ι(= 0), ή περιοριστούμε στην εύρεση ενός από τα στοιχεία του.

Αριθμοί ή οι κυριολεκτικές εκφράσεις τους προσδιορίζονται χρησιμοποιώντας ορίζουσες ειδικού είδους - οιονεί ανήλικοι(ανυπόγραφοκαθοριστικές). Η φόρμουλα ισχύει

.

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

Ο υπολογισμός ενός οιονεί δευτερεύοντος μειώνεται στην αποσύνθεσή του σε οιονεί ελάσσονες μικρότερης τάξης χρησιμοποιώντας τον τύπο

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

Παράδειγμα.

Αφήστε τη μήτρα των άμεσων συνδέσεων να έχει τη μορφή

Είναι απαραίτητο να βρείτε όλα τα μονοπάτια που οδηγούν από την κορυφή 1 έως την 5 και να μετρήσετε τον αριθμό τους.

Για το υπό εξέταση παράδειγμα λαμβάνουμε

Αρχικά στο matrix Η στήλη 1, που αντιστοιχεί στον αριθμό της κορυφής από την οποία ξεκινά η διαδρομή, και η γραμμή 5, που αντιστοιχεί στον αριθμό της κορυφής στην οποία τελειώνει η διαδρομή, διαγράφονται. Αυτό αντιστοιχεί στην αφαίρεση από το γράφημα όλων των άκρων που οδηγούν στην κορυφή 1 και στην αφαίρεση της κορυφής 5. Είναι πιο βολικό να αφήσετε τη θέση και την αρίθμηση των υπόλοιπων σειρών και στηλών αμετάβλητα. Στη συνέχεια, είναι απαραίτητο να επεκταθεί το οιονεί δευτερεύον που προκύπτει σε μη μηδενικά στοιχεία της 1ης σειράς

Η επέκταση για τον πρώτο όρο πραγματοποιείται στη δεύτερη γραμμή, η δεύτερη - στην τρίτη, η τρίτη - στην τέταρτη, δηλ. ο αριθμός της σειράς στην οποία πραγματοποιείται η επέκταση είναι ίσος με τον αριθμό της στήλης στην οποία βρισκόταν ο τελευταίος όρος της επέκτασης.

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

Εάν εκτελέσουμε ενέργειες στην παράσταση που προκύπτει σύμφωνα με τους κανόνες της άλγεβρας Boole, λαμβάνουμε την τιμή πλήρης πίνακας συνδέσεων, που χαρακτηρίζει συνδεσιμότητα γραφήματος. Τιμές στοιχείων του πλήρους πίνακα σύνδεσης ορίζονται ως εξής:

= 1, εάν η κορυφή i συνδέεται με την κορυφή j κατά τουλάχιστον ένα μονοπάτι,

=0 διαφορετικά.

Συνήθως πιστεύεται ότι
.

Η συνδεσιμότητα είναι το πιο σημαντικό χαρακτηριστικό του δομικού διαγράμματος ενός συστήματος. Όσο καλύτερη είναι η πληρότητα της πλήρους μήτρας των συνδέσεων, τόσο καλύτερη είναι η δομή. Η παρουσία μεγάλου αριθμού μηδενικών υποδηλώνει σοβαρά ελαττώματα στη δομή του συστήματος.

Ένα άλλο σημαντικό χαρακτηριστικό της δομής είναι η κατανομή της σημασίας των στοιχείων του συστήματος. Ποσοτικό χαρακτηριστικό σημαντικότητας - κατάταξη στοιχείων- διατυπώθηκε για πρώτη φορά ρητά στην ανάλυση της δομής των σχέσεων κυριαρχίας (ανωτερότητα, υπεροχή) σε ομάδες ατόμων (άνθρωποι, ζώα).

Χρησιμοποιώντας τον πλήρη πίνακα διαδρομής
, οι τιμές κατάταξης των στοιχείων καθορίζονται από τον τύπο

.

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

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

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

Υπάρχουν και άλλες μέθοδοι για τον προσδιορισμό των βαθμών. Η επιλογή μιας κατάλληλης τεχνικής καθορίζεται από τις ιδιαιτερότητες της εργασίας.

Πρέπει να σημειωθεί ότι υπάρχουν δομές, η κατάταξη των στοιχείων των οποίων μπορεί να χάσει το πρακτικό νόημα. Αυτές είναι, πρώτα απ' όλα, ιεραρχικές δομές. Η σημασία ενός στοιχείου σε αυτά καθορίζεται από το επίπεδο της ιεραρχίας.

Ο συγγραφέας αφηγείται περίπου 30 διασκεδαστικές (και διδακτικές) ιστορίες από τον χώρο των μαθηματικών. Μια από τις ιστορίες μιλά για τις αρχές του PageRank, ενός αλγόριθμου κατάταξης συνδέσμων που χρησιμοποιήθηκε για πρώτη φορά από την Google. Το θέμα είναι σχετικό και αρκετά κατανοητό. Πάμε λοιπόν στον Steven Strogatz...

Σε εκείνες τις μακρινές εποχές, όταν το Google δεν υπήρχε ακόμη, η αναζήτηση στο Διαδίκτυο ήταν μια απελπιστική εργασία. Οι ιστότοποι που προσφέρονται από παλαιότερες μηχανές αναζήτησης συχνά δεν ταιριάζουν με το ερώτημα και αυτοί που περιείχαν τις απαραίτητες πληροφορίες είτε ήταν θαμμένοι βαθιά στη λίστα αποτελεσμάτων είτε απουσίαζαν εντελώς. Οι αλγόριθμοι που βασίστηκαν στην ανάλυση συνδέσμων έλυσαν το πρόβλημα φτάνοντας στην καρδιά ενός παραδόξου παρόμοιου με το Zen koans: οι αναζητήσεις στο Διαδίκτυο υποτίθεται ότι έδειχναν τις καλύτερες σελίδες. Τι κάνει μια καλύτερη σελίδα; Όταν άλλες εξίσου καλές σελίδες συνδέονται σε αυτό.

Κατεβάστε τη σημείωση στο ή

Αυτό ακούγεται σαν φαύλος κύκλος. Αυτό είναι αλήθεια. Γι' αυτό όλα είναι τόσο περίπλοκα. Λαμβάνοντας αυτή την ιδέα και ωφελώντας την, ο αλγόριθμος ανάλυσης συνδέσμων παρέχει μια λύση jiu-jitsu σε αναζητήσεις στο διαδίκτυο. Αυτή η προσέγγιση βασίζεται σε ιδέες που λαμβάνονται από τη γραμμική άλγεβρα, τη μελέτη διανυσμάτων και πινάκων. Είτε θέλετε να αναγνωρίσετε μοτίβα σε τεράστιες ποσότητες δεδομένων είτε να εκτελέσετε γιγάντιους υπολογισμούς που περιλαμβάνουν εκατομμύρια μεταβλητές, η γραμμική άλγεβρα σάς παρέχει όλα τα εργαλεία που χρειάζεστε. Με τη βοήθειά του, δημιουργήθηκε η βάση για τον αλγόριθμο PageRank, ο οποίος αποτελεί τη βάση της Google. Βοήθησε επίσης τους επιστήμονες να ταξινομήσουν ανθρώπινα πρόσωπα, να αναλύσουν την ψηφοφορία στο Ανώτατο Δικαστήριο και να κερδίσουν το βραβείο Netflix (που δίνεται στην ομάδα που μπορεί να βελτιώσει το σύστημα του Netflix για την υποβολή προτάσεων για τις καλύτερες ταινίες κατά περισσότερο από 10 τοις εκατό).

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

Ρύζι. 1. Μικρό δίκτυο τριών τοποθεσιών

Τα βέλη υποδεικνύουν ότι η σελίδα X περιέχει έναν σύνδεσμο προς τη σελίδα Y, αλλά το Y δεν ανταποκρίνεται. Αντίθετα, το Υ αναφέρεται στο Ζ. Εν τω μεταξύ, το Χ και το Ζ αναφέρονται μεταξύ τους.

Ποιες σελίδες είναι οι πιο σημαντικές σε αυτόν τον μικρό ιστό; Ίσως πιστεύετε ότι είναι αδύνατο να προσδιοριστεί λόγω έλλειψης πληροφοριών σχετικά με το περιεχόμενό τους. Αλλά αυτός ο τρόπος σκέψης είναι ξεπερασμένος. Οι ανησυχίες σχετικά με το περιεχόμενο είχαν ως αποτέλεσμα έναν άβολο τρόπο κατάταξης σελίδων. Οι υπολογιστές έχουν ελάχιστη κατανόηση του περιεχομένου και οι άνθρωποι δεν μπορούν να αντιμετωπίσουν τις χιλιάδες νέες σελίδες που εμφανίζονται στο Διαδίκτυο καθημερινά.

Η προσέγγιση, που εφευρέθηκε από τους Larry Page και Sergey Brin, μεταπτυχιακούς φοιτητές στο πανεπιστήμιο και ιδρυτές της Google, ήταν να επιτραπεί στις σελίδες να ταξινομηθούν με συγκεκριμένη σειρά ψηφίζοντας συνδέσμους. Στο παραπάνω παράδειγμα, οι σελίδες X και Y συνδέονται με το Z, καθιστώντας το Z τη μοναδική σελίδα με δύο εισερχόμενους συνδέσμους. Κατά συνέπεια, θα είναι η πιο δημοφιλής σελίδα σε αυτό το περιβάλλον. Ωστόσο, εάν οι σύνδεσμοι προέρχονται από σελίδες αμφιβόλου ποιότητας, θα λειτουργήσουν εναντίον τους. Η δημοτικότητα από μόνη της δεν σημαίνει τίποτα. Το κύριο πράγμα είναι να έχετε συνδέσμους από καλές σελίδες.

Και εδώ βρισκόμαστε ξανά σε έναν φαύλο κύκλο. Μια σελίδα θεωρείται καλή εάν έχει καλές σελίδες που συνδέονται με αυτήν, αλλά ποιος αποφασίζει ποιες είναι καλές αρχικά; Αυτό αποφασίζεται από το δίκτυο. Έτσι πάει.

Ο αλγόριθμος της Google εκχωρεί σε κάθε σελίδα έναν κλασματικό αριθμό μεταξύ 0 και 1. Αυτή η αριθμητική τιμή ονομάζεται PageRank και μετρά τη "σημασία" μιας σελίδας σε σχέση με άλλες, υπολογίζοντας το σχετικό χρονικό διάστημα που θα περνούσε ένας υποθετικός χρήστης για να την επισκεφτεί. Αν και ένας χρήστης μπορεί να επιλέξει από περισσότερους από έναν εξερχόμενους συνδέσμους, επιλέγει έναν τυχαία με ίση πιθανότητα. Με αυτήν την προσέγγιση, οι σελίδες θεωρούνται πιο έγκυρες εάν επισκέπτονται συχνότερα.

Και επειδή οι δείκτες PageRank ορίζονται ως αναλογίες, το άθροισμά τους σε ολόκληρο το δίκτυο πρέπει να είναι 1. Αυτός ο νόμος διατήρησης προτείνει έναν άλλο, ίσως πιο απτό, τρόπο οπτικοποίησης της Κατάταξης σελίδας. Σκεφτείτε το ως μια υγρή ουσία που ρέει μέσω του δικτύου, η ποσότητα της οποίας μειώνεται σε κακές σελίδες και αυξάνεται σε καλές. Χρησιμοποιώντας έναν αλγόριθμο, προσπαθούμε να προσδιορίσουμε πώς αυτό το υγρό κατανέμεται στο Διαδίκτυο με την πάροδο του χρόνου.

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

Αρχικά, ο αλγόριθμος ορίζει ίσα μερίδια, γεγονός που επιτρέπει σε κάθε σελίδα να λάβει το ίδιο ποσό PageRank. Στο παράδειγμά μας υπάρχουν τρεις σελίδες και καθεμία από αυτές αρχίζει να κινείται σύμφωνα με τον αλγόριθμο με βαθμολογία 1/3.

Ρύζι. 2. Αρχικές τιμές PageRank

Στη συνέχεια, η βαθμολογία ενημερώνεται για να δείξει την πραγματική αξία κάθε σελίδας. Ο κανόνας είναι ότι κάθε σελίδα παίρνει το PageRank της από τον τελευταίο κύκλο και το κατανέμει ομοιόμορφα σε όλες τις σελίδες στις οποίες συνδέεται. Επομένως, η ενημερωμένη τιμή της σελίδας X μετά τον πρώτο γύρο εξακολουθεί να είναι το 1/3, καθώς αυτό είναι το ποσό PageRank που λαμβάνει από το Z, τη μοναδική σελίδα που συνδέεται με αυτήν. Αυτό μειώνει τη βαθμολογία της σελίδας Y στο 1/6, καθώς λαμβάνει μόνο το ήμισυ του PageRank του X μετά τον προηγούμενο γύρο. Το άλλο μισό πηγαίνει στη Σελίδα Z, καθιστώντας το νικητή σε αυτό το σημείο καθώς προσθέτει άλλο 1/6 της Σελίδας X στον εαυτό της, καθώς και το 1/3 του Y, για ένα σύνολο 1/2. Έτσι, μετά τον πρώτο κύκλο έχουμε τις ακόλουθες τιμές PageRank:

Ρύζι. 3. Τιμές PageRank μετά από μία ενημέρωση

Στους επόμενους κύκλους, ο κανόνας ενημέρωσης παραμένει ο ίδιος. Αν συμβολίσουμε με x, y, z το τρέχον πλήθος των σελίδων X, Y και Z, τότε ως αποτέλεσμα της ενημέρωσης παίρνουμε το ακόλουθο πλήθος:

z’ = ½ x + y,

όπου οι πινελιές υποδεικνύουν ότι έγινε ενημέρωση. Είναι βολικό να εκτελείτε τέτοιους επαναλαμβανόμενους υπολογισμούς σε ένα υπολογιστικό φύλλο (ή χειροκίνητα εάν το δίκτυο είναι μικρό, όπως στην περίπτωσή μας).

Μετά από δέκα επαναλήψεις, θα διαπιστώσουμε ότι οι αριθμοί ουσιαστικά δεν αλλάζουν από ενημέρωση σε ενημέρωση. Σε αυτό το σημείο, το μερίδιο του X θα είναι 40,6% του συνολικού PageRank, το μερίδιο του Y θα είναι 19,8% και το Z θα είναι 39,6%. Αυτές οι τιμές είναι ύποπτα κοντά στους αριθμούς 40, 20 και 40%, γεγονός που υποδηλώνει ότι ο αλγόριθμος πρέπει να συγκλίνει σε αυτούς. Αυτό είναι αλήθεια. Ο αλγόριθμος της Google ορίζει αυτές τις οριακές τιμές για το δίκτυο ως PageRank.

Ρύζι. 4. Όρια κατάταξης σελίδας

Το συμπέρασμα για αυτό το μικρό δίκτυο είναι ότι οι σελίδες X και Z είναι εξίσου σημαντικές, παρόλο που το Z έχει διπλάσιο αριθμό εισερχόμενων συνδέσεων. Αυτό είναι κατανοητό: Η Σελίδα X είναι ίση με το Z σε σημασία, αφού λαμβάνει την πλήρη έγκριση από αυτήν, αλλά της δίνει μόνο το ήμισυ της έγκρισής της ως αντάλλαγμα. Το άλλο μισό πηγαίνει στο Y. Αυτό εξηγεί επίσης γιατί ο Y παίρνει μόνο το ήμισυ των μετοχών του X και του Z.

Είναι ενδιαφέρον ότι αυτές οι τιμές μπορούν να ληφθούν χωρίς να καταφύγουμε σε πολλαπλές επαναλήψεις. Απλά πρέπει να σκεφτείτε τις συνθήκες που ορίζουν μια στατική κατάσταση. Εάν δεν αλλάξει τίποτα μετά την επόμενη ενημέρωση, τότε x’ = x, y’ = y και z’ = z. Επομένως, αντικαθιστώντας τις αρχικές μεταβλητές στις εξισώσεις ενημέρωσης με τα ισοδύναμά τους χωρίς πρώτους, λαμβάνουμε ένα σύστημα εξισώσεων

κατά την επίλυση x = 2y = z. Δεδομένου ότι το άθροισμα των τιμών των x, y και z πρέπει να ισούται με 1, προκύπτει ότι x = 2/5, y = 1/5 και z = 2/5, που αντιστοιχεί στις τιμές που βρέθηκαν προηγουμένως.

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

Ωστόσο, η πιο σημαντική νίκη της γραμμικής άλγεβρας, όσον αφορά τον ρόλο της στην καθημερινή ζωή, ήταν σίγουρα η λύση στο παράδοξο του Ζεν Βουδισμού για την κατάταξη σελίδων. "Μια σελίδα είναι τόσο καλή όσο οι καλές σελίδες που συνδέονται με αυτήν." Μεταφρασμένο σε μαθηματικά σύμβολα, αυτό το κριτήριο γίνεται ο αλγόριθμος PageRank.

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

Σύμφωνα με την Google, ο όρος PageRang προέρχεται από το όνομα ενός εκ των ιδρυτών της Google, του Larry Page, και όχι από την αγγλική λέξη σελίδα (σελίδα).

Για λόγους απλότητας, θα παρουσιάσω μόνο τη βασική έκδοση του αλγορίθμου PageRank. Για τον χειρισμό δικτύων με κάποιες άλλες δομικές ιδιότητες, πρέπει να τροποποιηθεί. Ας υποθέσουμε ότι υπάρχουν σελίδες στο δίκτυο που συνδέονται με άλλες, αλλά αυτές, με τη σειρά τους, δεν συνδέονται με αυτές. Κατά τη διαδικασία ενημέρωσης, αυτές οι σελίδες θα χάσουν το PageRank τους. Το δίνουν σε άλλους και δεν αναπληρώνεται πια. Έτσι, θα καταλήξουν με τιμές PageRank ίσες με μηδέν και από αυτή την άποψη θα γίνουν δυσδιάκριτες.

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

Για να αποφύγουν τέτοια αποτελέσματα, οι Brin και Page τροποποίησαν τον αλγόριθμό τους ως εξής. Μετά από κάθε βήμα στη διαδικασία ενημέρωσης δεδομένων, όλες οι τρέχουσες τιμές PageRank μειώνονται κατά έναν σταθερό παράγοντα, έτσι ώστε το άθροισμά τους να είναι μικρότερο από 1. Το υπόλοιπο PageRank κατανέμεται στη συνέχεια ομοιόμορφα μεταξύ όλων των κόμβων του δικτύου, σαν να «πέφτει από ο ουρανός." Έτσι, ο αλγόριθμος τελειώνει με μια ενέργεια εξισορρόπησης που κατανέμει τις τιμές PageRank μεταξύ των φτωχότερων κόμβων.

Τα μαθηματικά του PageRank και η διαδραστική έρευνα συζητούνται πιο διεξοδικά στους E. Aghapour, T. P. Chartier, A. N. Langville και K. E. Pedings, Google PageRank: The mathematics of Google (