Ανάλυση, μοντελοποίηση και προσομοίωση αναζήτησης σε σύνθετα δυναμικά δίκτυα
Authors: Μαργαρίτη Σπυριδούλα 
Published: September 2021

Στον πραγματικό κόσμο συναντάμε πληθώρα σύνθετων συστημάτων, που προέρχονται από διαφορετικούς τομείς (της επιστήμης, της φύσης, της τεχνολογίας, αλλά και της κοινωνίας), σε διάφορες κλίμακες και με ποικίλους σχηματισμούς. Τα συστήματα αυτά αναφύονται και εξελίσσονται ακολουθώντας απλούς κανόνες που καθορίζονται από τις αλληλεπιδράσεις μεταξύ των οντοτήτων που τα απαρτίζουν. Οι εγγενείς διαδικασίες σχηματισμού ή/και μεταβολής τους, οι δυναμικές λειτουργίες που εκτυλίσσονται σε αυτά και ο τεράστιος όγκος πληροφορίας που απαιτείται για τον προσδιορισμό τους, τα καθιστούν ιδιαίτερα πολύπλοκα. Για την περιγραφή τους, την αναπαραγωγή τους και την ποσοτικοποίησή τους χρησιμοποιούμε εργαλεία από την επιστήμη των δικτύων, τα οποία μας επιτρέπουν να κατανοήσουμε και να προβλέψουμε την συμπεριφορά τους αλλά και τη συμπεριφορά των δυναμικών διαδικασιών που εξελίσσονται σε αυτά, όπως η αναζήτηση. Η αναζήτηση είναι ένα από τα σημαντικότερα ζητήματα στα σύνθετα δίκτυα με πρακτική εφαρμογή σε διάφορα πλαίσια, όπως, για παράδειγμα, την εύρεση ενός στόχου ή την αναζήτηση ενός προσώπου σε ένα κοινωνικό δίκτυο ή τον εντοπισμό ενός πόρου σε ένα δίκτυο ομότιμων (peer-to-peer) ή την ανάκτηση των δεδομένων που αποθηκεύονται σε μεγάλες ποσότητες στους κόμβους των δικτύων ή την εύρεση ενός δρομολογητή σε ένα δίκτυο επικοινωνίας. Η αναζήτηση είναι μια δυναμική διαδικασία που εξελίσσεται σε ένα δίκτυο μεταδίδοντας μηνύματα από κόμβο σε κόμβο. Όταν υπάρχει συνολική γνώση του δικτύου, η αναζήτηση στρέφεται στην εύρεση της καταλληλότερης διαδρομής με βάση κάποιο κριτήριο (π.χ. κόστος μετάβασης σε hops). Αντίθετα, η παντελής έλλειψη πληροφορίας σχετικά με τη δομή του δικτύου, έχει ως αποτέλεσμα η διαδικασία αναζήτησης να διεξάγεται τυφλά ή να βασίζεται μόνο σε τοπική πληροφορία. Στόχος αυτής της διατριβής είναι η σχεδίαση και ανάπτυξη μοντέλων και τεχνικών που θα συμβάλουν σε δύο κατευθύνσεις: α) να διερευνήσουμε τη διαδικασία της αναζήτησης αναλυτικά και πειραματικά και β) να εξετάσουμε την εφαρμοσιμότητά τους σε σύνθετα δίκτυα. Εστιάζουμε σε αδόμητα δίκτυα, όπου οι συνδέσεις μεταξύ των κόμβων είναι αποτέλεσμα κανόνων τυχαιότητας, στατικά ή δυναμικά και οι τεχνικές αναζήτησης βασίζονται στην πλημμύρα. Αρχικά, εξετάζουμε και αναλύουμε τη συμπεριφορά της αναζήτησης και παρέχουμε γενικά όρια και προσεγγιστικά μοντέλα για την εκτίμηση της μη αναγκαίας παραγόμενης κίνησης (διπλότυπα μηνύματα) και την κάλυψη του δικτύου. Θέτοντας ως πρωταρχικό στόχο την εξάλειψη της πλεονάζουσας πληροφορίας που οφείλονται στην τοπολογία του δικτύου και στην ύπαρξη πολλαπλών μονοπατιών μεταξύ των κόμβων, προτείνουμε δύο πιθανοτικές στρατηγικές αναζήτησης που αξιοποιούν χαρακτηριστικά και μετρικές του δικτύου, όπως για παράδειγμα, το πλήθος των συνδέσεων του κάθε κόμβου (βαθμός) ή τον αριθμητικό μέσο των βαθμών. Η απόφαση ενός κόμβου για να μεταδώσει ένα μήνυμα-ερώτηση που έλαβε, βασίζεται στη δημοτικότητα των αντικειμένων και σε μια εκτίμηση για την κάλυψη του δικτύου. Ο κάθε κόμβος, πριν μεταδώσει, προσαρμόζει την πιθανότητα προώθησης, έτσι ώστε να μειώνονται τα διπλότυπα μηνύματα ενώ η πιθανότητα επιτυχίας παραμένει υψηλή. Για να μελετήσουμε την αναζήτηση θέτουμε ένα πλαίσιο που περιλαμβάνει: την τοπολογία του δικτύου, τα προς αναζήτηση στοιχεία και τον μηχανισμό αναζήτησης. Σχεδιάζουμε και αναπτύσσουμε ένα πρωτότυπο, γενικού σκοπού προσομοιωτή, που τον ονομάσαμε Armonia. Παρέχει υλοποιημένα σύνολα, που έχουν προταθεί κατά καιρούς στη βιβλιογραφία, για διάφορα στατικά και δυναμικά μοντέλα δικτύων, διαφορετικές τεχνικές αναζήτησης και στρατηγικές εκχώρησης αντιγράφων. Τέλος, χρησιμοποιούμε το πλαίσιο προσομοίωσης Armonia για την αξιολόγηση των προτεινόμενων τεχνικών. Εφαρμόζουμε τις στρατηγικές μας σε στατικά και δυναμικά δίκτυα που παράγουμε χρησιμοποιώντας είτε τυπικά μοντέλα δικτύων είτε διαθέσιμα σύνολα δεδομένων από πραγματικά δίκτυα. Συγκριτικά πειραματικά αποτελέσματα των προτεινόμενων τεχνικών μας με άλλες παρόμοιες στρατηγικές επιβεβαιώνουν την αποτελεσματικότητά τους.