Ανάλυση, μοντελοποίηση και προσομοίωση αναζήτησης σε σύνθετα δυναμικά δίκτυα

Abstract

Complex networks are present everywhere in the real world, coming from different fields (science, nature, technology, society), in various scales and with a variety of forms. These systems arise and evolve by following simple rules defined through the interactions between the participating entities. They are considered complex because of the complicated mechanics of their creation and evolution, because of the dynamic processes that take place within them and because of the huge amount of information required to identify them. Tools from network science are used to describe, reproduce and quantify them and also, to help us to understand and predict their behavior as well as the behavior of the dynamic processes that occur within them.Search is one of the fundamental issues in complex networks with practical application in various contexts, such as finding a target or locating a person in a social network or discovering a desired resource. Search is a dynamic process that unfolds by transmitting messages from node to node. When there is global knowledge of the network, search is focused on finding the most appropriate route based on some criterion (eg. transition costs). In the absence of information about the network structure, search in these systems is a blind procedure, possibly using only local information. The aim of this dissertation is to design and develop models and techniques that will contribute in two directions: a) towards the study of the search process both analytically and experimentally, and b) towards investigating their applicability in complex networks. We focus on static or dynamic unstructured networks where connections between nodes are governed by random rules, and on search mechanisms based on flooding. We start by studying and analyzing the behavior of flooding with respect to unnecessarily produced traffic (duplicate messages) and provide simple bounds and approximate models to assess the associated overheads and network coverage. Our primary objective is the elimination of overheads that emanate from the overlay network topology itself and the multiplicity of paths among nodes. We then propose novel probabilistic search algorithms that exploit network features and metrics, such as the nodes degrees. The decision of a node to propagate a message (or not) is based on both the popularity of resources and an estimation of network coverage. Based on these parameters we adjust the forwarding probability at the time a node receives the query message so as to reduce the duplicate message overhead while maintaining a high probability of query success. To study the search problem experimentally, we consider a comprehensive framework which includes the network topology, the resources and the searching strategies. We design and develop a novel, general-purpose simulator, called Armonia. It provides implementations for a wide suite of models and algorithms found in the literature related to network topology generation, search strategies and resources allocation and placement policies. Finally, we use our simulation framework to evaluate our proposed algorithms. We apply our strategies in static and dynamic networks using well-known network models and data sets coming from real networks. The observed results confirm the effectiveness of our mechanisms and their superiority with respect to the other known strategies.

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