Σύγκριση Σύγχρονων Μεθόδων Εξεύρεσης Κοινοτήτων και Πρακτικές Εφαρμογές

Abstract

Η Ανίχνευση Κοινοτήτων είναι μία από τις πιο δημοφιλείς μεθόδους για την ανάλυση Μεγάλων ∆εδομένων που προκύπτουν από τοπολογίες Σύνθετων ∆ικτύων. Τα περισσότερα πραγματικά δίκτυα εμφανίζουν κοινοτική δομή, δηλαδή οι κόμβοι είναι οργανωμένοι σε ομάδες και μοιράζονται τις περισσότερες φορές μια κοινή ιδιότητα. ́Οσο το μέγεθος και η πολυπλοκότητα των δικτύων αυξάνεται, το πρόβλημα της Ανίχνευσης Κοινοτήτων σε γράφους καθίσταται ένα δύσκολο υπολογιστικά πρόβλημα, δημιουργώντας την ανάγκη για ανάπτυξη μεθόδων που θα δίνουν ικανοποιητικά αποτελέσματα σε μικρό χρόνο. Στην παρούσα διπλωματική εργασία, αρχικά, ερευνήθηκαν συγκεκριμένες μέθοδοι Ανίχνευσης Κοινοτήτων σε μεγάλους γράφους. Στη συνέχεια, και με βάση την υπάρχουσα βιβλιογραφία, επιλέχθηκαν δύο αλγόριθμοι, από δύο διαφορετικές κατηγορίες μεθόδων. Σε πρώτο στάδιο μελετήθηκε ο Hyperbolic Girvan-Newman, ο οποίος αποτελεί μια παραλλαγή του κλασικού Girvan-Newman αλγορίθμου. Η διαφορά τους έγκειται, στο ότι ο HGN κάνει πρώτα χρήση δικτύων, ενσωματωμένων στον Υπερβολικό χώρο. Σε δεύτερο στάδιο υλοποιήθηκε ο αλγόριθμος Walktrap, ο οποίος βασίζεται σε Τυχαίους Περιπάτους. ́Επειτα μελετήθηκε τόσο η απόδοση του HGN όσο και του Walktrap σε δεδομένα από Κοινωνικά ∆ίκτυα μικρής-κλίμακας και επιχειρήθηκε μία σύγκριση των αποτελεσμάτων μεταξύ αυτών των δύο μεθόδων. Τα αποτελέσματα αυτά παρουσιάζονται αναλυτικά τόσο με πίνακες όσο και με διαγράμματα, στο αντίστοιχο κεφάλαιο της ∆ιπλωματικής Εργασίας.