Αλγόριθμοι Ανάλυσης Κεντρικότητας Σε Κοινωνικά Δίκτυα

Abstract

Ο σκοπός της παρούσας διπλωματικής εργασίας είναι η ανάπτυξη μίας μεθοδολογίας για την ανάλυση και αποδοτική προσέγγιση/υπολογισμό μετρικών κεντρικότητας βασισμένων σε μονοπάτια, δηλαδή κεντρικότητες οι οποίες απαιτούν γνώση της πραγματικής δρομολόγησης μονοπατιών για τον υπολογισμό τους. Τέτοιες μετρικές είναι πολύ σημαντικές για την ανάλυση της δρομολόγησης και για μηχανισμούς και εφαρμογές δικτύων που βασίζονται στη δρομολόγηση.Παρ’ όλα αυτά, η δρομολόγηση που βασίζεται σε συντομότερα μονοπάτια σε αριθμό βημάτων και η εκτίμηση των μετρικών κεντρικότητας στα σύγχρονα σύνθετα δίκτυα (τα οποία αποτελούνται έως και από εκατομμύρια κόμβους και ακμές) είναι μία, μάλλον αρκετά δαπανηρή, σε σχέση με τον υπολογιστικό της χρόνο, εργασία. Για τον λόγο αυτό, χρησιμοποιήθηκε η ενσωμάτωση δικτύων στον υπερβολικό χώρο, ενώ υιοθετήθηκε η άπληστη δρομολόγηση πάνω σε υπερβολικές συντεταγμένες. Η άπληστη δρομολόγηση στον υπερβολικό χώρο έχει διπλό πλεονέκτημα: (i) Απαιτεί λιγότερη υπολογιστική προσπάθεια από την δρομολόγηση συντομότερων μονοπατιών (σε σχέση με την απόσταση-βημάτων), ενώ την ίδια στιγμή, (ii) καταλήγει σε άπληστα μονοπάτια με μήκη πολύ κοντά σε αυτά των συντομότερων μονοπατιών, για τα σύνθετα δίκτυα που μας ενδιαφέρουν, τα οποία φέρουν την ιδιότητα της ελεύθερης-κλίμακας (scale-free). Κάνοντας χρήση αυτών των δύο στοιχείων, προτείνεται η Υπερβολική Κεντρικότητα Φόρτου Κίνησης (ΥΚΦΚ) σαν μία εναλλακτική μετρική της Κεντρικότητας Φόρτου Κίνησης (ΚΦΚ), η οποία χρησιμοποιείται για την κατάταξη των κόμβων σε σχέση με τη σημασία τους στη διαδικασία δρομολόγησης. Μέσω ανάλυσης και προσομοιώσεων, επιδείχθηκε ότι η ΥΚΦΚ απαιτεί σημαντικά λιγότερο υπολογιστικό χρόνο από την ΚΦΚ, ενώ παρ’ όλο που είναι περισσότερο ενδεδειγμένη για καθεστώς άπληστης δρομολόγησης στον υπερβολικό χώρο, επιτυγχάνει μία κοντινή προσέγγιση της ΚΦΚ για δίκτυα με ιδιότητες ελεύθερης-κλίμακας όταν υιοθετείται η δρομολόγηση συντομότερων μονοπατιών.Επιπλέον, η ΥΚΦΚ μελετήθηκε κάτω από έναν τύπο ενσωμάτωσης του γράφου του δικτύου στον υπερβολικό χώρο συντεταγμένων (που αποκαλείται «Άπληστη Ενσωμάτωση») ο οποίος εξασφαλίζει 100% επιτυχία της άπληστης δρομολόγησης. Αυτός ο τύπος ενσωμάτωσης βρίσκει πρώτα μία ενσωμάτωση ενός συνδετικού δένδρου του γράφου του δικτύου, η οποία είναι επίσης μία άπληστη ενσωμάτωση ολόκληρου του γράφου. Παρ’ όλα αυτά, η επιλογή των δενδρικών ακμών του δένδρου έχει σημαντική επίδραση στις μετρικές κεντρικότητας όλων των κόμβων στο δίκτυο. Αυτή η επίδραση παρουσιάστηκε μέσω μαθηματικών σχέσεων, απτών παραδειγμάτων και στατιστικών ιδιοτήτων. Κάνοντας χρήση αυτής της επίδρασης, προτάθηκε ένα πλαίσιο σχεδιασμού και προσαρμογής της δρομολόγησης πακέτων με αξιολόγηση της σημασίας των κόμβων, χρήσιμο για λειτουργίες μεταφοράς της συμφόρησης κατά τη δρομολόγηση.