Please use this identifier to cite or link to this item: http://artemis.cslab.ece.ntua.gr:8080/jspui/handle/123456789/13572
Title: Ανάλυση Μεγάλων Δεδομένων Διαδικτύου-των-αντικειμένων Με Αλγόριθμους Ανίχνευσης Κοινοτήτων Σε Δίκτυα Υπερβολικών Χώρων
Authors: Κωνσταντινος Τσιτσεκλης
Παπαβασιλείου Συμεών
Keywords: ανίχνευση κοινοτήτων
ομαδοποίηση
μεγάλα δεδομένα
διαδίκτυο-των-αντικειμένων
κεντρικότητα ενδιαμεσικότητας ακμής
υπερβολικός χώρος
υπερβολική γεωμετρία
κοινωνικά δίκτυα
ενσωμάτωση δικτύου
Issue Date: 10-Oct-2017
Abstract: Ο σκοπός της παρούσας Διπλωμάτικης Εργασίας είναι η ανάπτυξη μιας αποδοτικής μεθοδολογίας Ανίχνευσης Κοινοτήτων για την ανάλυση Μεγάλων Δεδομένων που προκύπτουν από τοπολογίες Διαδικτύου-των-Αντικειμένων. Για τον σκοπό αυτό γίνεται χρήση δικτύων ενσωματωμένων στον Υπερβολικό Χώρο. Ο χώρος αυτός λόγω των ιδιοτήτων του, επιλέγεται ως ένας «φυσικός» χώρος για την αναπαράσταση Σύνθετων Δικτύων. Για την ανάπτυξη της μεθοδολογίας γίνεται τροποποίηση του αλγόριθμου Ανίχνευσης Κοινοτήτων των Newman-Girvan. Στον αλγόριθμο των Newman-Girvan γίνεται χρήση της έννοιας της Κεντρικότητας Ενδιαμεσικότητας Ακμών. Στο πλαίσιο της παρούσας εργασίας προτείνεται μια προσέγγιση υπολογισμού της μετρικής αυτής με χρήση υπερβολικής γεωμετρίας. Συγκεκριμένα, προτείνεται ένας προσεγγιστικός αλγόριθμος ο οποίος υπολογίζει τις Κεντρικότητες των Ακμών βασισμένος στις αποστάσεις των κόμβων μετά από ενσωμάτωσή των αντίστοιχων δικτύων στον Υπερβολικό Χώρο. Η νέα αυτή μετρική ονομάζεται Υπερβολική Κεντρικότητα Ενδιαμεσικότητας Ακμής (Υ.Κ.Ε.Α.). Επειδή ο υπολογισμός της Κεντρικότητας Ενδιαμεσικότητας (είτε κορυφής, είτε ακμής) βασίζεται στον υπολογισμό συντομότερων μονοπατιών επιλέγεται για την ενσωμάτωση του δικτύου η Ενσωμάτωση Rigel. Η ενσωμάτωση αυτή τοποθετεί τους κόμβους με τέτοιο τρόπο στον Υπερβολικό Χώρο ώστε η απόσταση δυο κόμβων να προσεγγίζει την απόσταση τους στο δίκτυο. Στη συνέχεια, η μετρική αυτή χρησιμοποιείται στον προτεινόμενο αλγόριθμο Ανίχνευσης Κοινοτήτων Hyperbolic Newman-Girvan (HNG).Η απόδοση του αλγόριθμου HNG μελετήθηκε τόσο για Γράφους Εγγύτητας, δίκτυα δηλαδή που προκύπτουν από την ένωση σημείων παρατηρήσεων όσο και για Κοινωνικά Δίκτυα τύπου μικρής-κλίμακας, αλλά και για διάφορα μοντέλα κατασκευής Σύνθετων Δικτύων. Ο αλγόριθμος ολοκληρώθηκε σε μικρότερο χρονικό διάστημα από τον αλγόριθμο των Newman-Girvan στην περίπτωση των Γράφων Εγγύτητας που εξετάστηκαν, καθώς επίσης έδωσε ικανοποιητικά αποτελέσματα Αρθρωτότητας για τα υπόλοιπα δίκτυα. Τα αποτελέσματα αυτά παρουσιάζονται αναλυτικά τόσο με πίνακες όσο και με διαγράμματα στο αντίστοιχο κεφάλαιο της Εργασίας (Κεφάλαιο 8).
URI: http://artemis-new.cslab.ece.ntua.gr:8080/jspui/handle/123456789/13572
Appears in Collections:Διπλωματικές Εργασίες - Theses

Files in This Item:
File SizeFormat 
DT2017-0230.pdf2.89 MBAdobe PDFView/Open


Items in Artemis are protected by copyright, with all rights reserved, unless otherwise indicated.