Ανάλυση Μεγάλων Δεδομένων Διαδικτύου-των-αντικειμένων Με Αλγόριθμους Ανίχνευσης Κοινοτήτων Σε Δίκτυα Υπερβολικών Χώρων

Abstract

Ο σκοπός της παρούσας Διπλωμάτικης Εργασίας είναι η ανάπτυξη μιας αποδοτικής μεθοδολογίας Ανίχνευσης Κοινοτήτων για την ανάλυση Μεγάλων Δεδομένων που προκύπτουν από τοπολογίες Διαδικτύου-των-Αντικειμένων. Για τον σκοπό αυτό γίνεται χρήση δικτύων ενσωματωμένων στον Υπερβολικό Χώρο. Ο χώρος αυτός λόγω των ιδιοτήτων του, επιλέγεται ως ένας «φυσικός» χώρος για την αναπαράσταση Σύνθετων Δικτύων. Για την ανάπτυξη της μεθοδολογίας γίνεται τροποποίηση του αλγόριθμου Ανίχνευσης Κοινοτήτων των Newman-Girvan. Στον αλγόριθμο των Newman-Girvan γίνεται χρήση της έννοιας της Κεντρικότητας Ενδιαμεσικότητας Ακμών. Στο πλαίσιο της παρούσας εργασίας προτείνεται μια προσέγγιση υπολογισμού της μετρικής αυτής με χρήση υπερβολικής γεωμετρίας. Συγκεκριμένα, προτείνεται ένας προσεγγιστικός αλγόριθμος ο οποίος υπολογίζει τις Κεντρικότητες των Ακμών βασισμένος στις αποστάσεις των κόμβων μετά από ενσωμάτωσή των αντίστοιχων δικτύων στον Υπερβολικό Χώρο. Η νέα αυτή μετρική ονομάζεται Υπερβολική Κεντρικότητα Ενδιαμεσικότητας Ακμής (Υ.Κ.Ε.Α.). Επειδή ο υπολογισμός της Κεντρικότητας Ενδιαμεσικότητας (είτε κορυφής, είτε ακμής) βασίζεται στον υπολογισμό συντομότερων μονοπατιών επιλέγεται για την ενσωμάτωση του δικτύου η Ενσωμάτωση Rigel. Η ενσωμάτωση αυτή τοποθετεί τους κόμβους με τέτοιο τρόπο στον Υπερβολικό Χώρο ώστε η απόσταση δυο κόμβων να προσεγγίζει την απόσταση τους στο δίκτυο. Στη συνέχεια, η μετρική αυτή χρησιμοποιείται στον προτεινόμενο αλγόριθμο Ανίχνευσης Κοινοτήτων Hyperbolic Newman-Girvan (HNG).Η απόδοση του αλγόριθμου HNG μελετήθηκε τόσο για Γράφους Εγγύτητας, δίκτυα δηλαδή που προκύπτουν από την ένωση σημείων παρατηρήσεων όσο και για Κοινωνικά Δίκτυα τύπου μικρής-κλίμακας, αλλά και για διάφορα μοντέλα κατασκευής Σύνθετων Δικτύων. Ο αλγόριθμος ολοκληρώθηκε σε μικρότερο χρονικό διάστημα από τον αλγόριθμο των Newman-Girvan στην περίπτωση των Γράφων Εγγύτητας που εξετάστηκαν, καθώς επίσης έδωσε ικανοποιητικά αποτελέσματα Αρθρωτότητας για τα υπόλοιπα δίκτυα. Τα αποτελέσματα αυτά παρουσιάζονται αναλυτικά τόσο με πίνακες όσο και με διαγράμματα στο αντίστοιχο κεφάλαιο της Εργασίας (Κεφάλαιο 8).