Εμπειρική μελέτη ανίχνευσης κοινοτήτων σε γραφήματα διαφορετικού τύπου αλληλεπιδράσεων
Loading...
Date
2026-07-02
Authors
Σακκά, Χρυσάνθη-Νεφέλη
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
H σύγχρονη επιστήμη των δικτύων έχει φέρει σημαντικές προόδους, για την κατανόηση των πολύπλοκων συστημάτων. Ένα από τα πιο σημαντικά προβλήματα των γραφημάτων μοντελοποίησης πραγματικών συστημάτων έγκειται στην αναγνώριση δομών κοινοτήτων – community detection. Για την αποδοτική επεξεργασία δεδομένων μεγάλης κλίμακας, έχουν αναπτυχθεί συγκεκριμένες μεθοδολογίες, για την πρόβλεψη της υποκείμενης κοινοτικής ιεραρχίας σε γραφήματα κοινωνικών δικτύων χρήσει αλγορίθμων ανίχνευσης κοινοτήτων (community detection). Ένα από τα πιο σημαντικά χαρακτηριστικά των γραφημάτων που αναπαριστούν πραγματικά συστήματα είναι η δομή των κοινοτήτων ή η συσταδοποίηση (clustering), δηλαδή η οργάνωση των κορυφών σε συστάδες, με πολλές ακμές που ενώνουν κορυφές της ίδιας συστάδας και σχετικά λίγες ακμές που ενώνουν κορυφές διαφορετικών συστάδων. Ως αποτέλεσμα, οι τεχνικές ανάλυσης δικτύων έχουν ευρέως υιοθετηθεί λόγω της ενσωματωμένης αποδοτικότητάς τους στον χειρισμό ιεραρχικών δεδομένων και οι εφαρμογές της θεωρίας γραφημάτων έχουν τραβήξει σημαντικό επιστημονικό νδιαφέρον. Η ανίχνευση κοινοτήτων χρήζει μεγάλης σημασίας στην κοινωνιολογία, τη βιολογία και την επιστήμη των υπολογιστών, καθώς και σε εφαρμογές όπως το μάρκετινγκ και η ανάλυση ιεραρχικών δομών. Στην βιβλιογραφία έχουν προταθεί ποικίλες οικογένειες μεθόδων από κλασικές ευρετικές βελτιστοποίησης modularity και διαιρετικές μεθόδους, έως κατανεμημένη πρόβλεψη κοινοτήτων, εξελικτικούς αλγορίθμους, βελτιώσεις matrix-based προσεγγίσεων και σύγχρονες κατευθύνσεις βαθιάς μάθησης. Οι τελευταίες κατευθύνσεις αναδεικνύουν κίνητρα κλιμάκωσης και εμπλουτισμού της εισόδου, αλλά δεν αποτελούν αντικείμενο υλοποίησης της παρούσας εργασίας. Η διπλωματική επικεντρώνεται σε εμπειρική, αναπαραγώγιμη (reproducible) σύγκριση τριών κλασικών αλγορίθμων — Louvain, Leiden και Girvan–Newman — σε έξι μη κατευθυνόμενα γραφήματα: τρία από το Stanford SNAP (citation, email, web) και τρία χημικά/βιολογικά από το BioSNAP (drug–gene, drug–drug, protein). Οι Louvain και Leiden εφαρμόζονται στο πλήρες γράφημα· ο Girvan–Newman σε BFS υπογράφημα (subgraph),όπου το πλήρες δίκτυο είναι υπολογιστικά μη πρακτικό. Η αξιολόγηση βασίζεται σε δομική συνοχή (structural cohesion: modularity Q, αριθμός κοινοτήτων, κατανομή μεγεθών, χρόνος εκτέλεσης) και όχι σε σημασιολογικό περιεχόμενο κόμβων, δεδομένου ότι τα datasets είναι λίστες ακμών. Τα αποτελέσματα αναδεικνύουν συμπεριφορά ανά domain (domain-specific): τα κοινωνικά/επιστημονικά SNAP δίκτυα εμφανίζουν πολλές medium-sized communities, ενώ τα BioSNAP — ιδίως το dense ChCh-Miner — συμπεριφέρονται διαφορετικά. Ο Leiden δίνει συνήθως ελαφρώς υψηλότερη Q και σημαντικά μικρότερο χρόνο από τον Louvain,επιβεβαιώνοντας τη βιβλιογραφία σε διαφορετικό σύνολο domains. Ο Girvan–Newmanλειτουργεί ως ιστορικό/divisive σημείο αναφοράς, όχι ως ισοδύναμος ανταγωνιστής σε πλήρη κλίμακα. Η κύρια συνεισφορά είναι η ανάλυση ανά domain (domain-specific) και η ένταξη χημικών γραφημάτων (BioSNAP) στο ίδιο πειραματικό πλαίσιο με κλασικά SNAPbenchmarks (§1.2.1).Η υλοποίηση πραγματοποιήθηκε σε Python (NetworkX, leidenalg) και δημοσιεύεταιαναπαραγώγιμα. Μελλοντική επέκταση: κατευθυνόμενα ή weighted γραφήματα (edgeweights, §2.0), κατανεμημένα και νεφοϋπολογιστικά.Θα προσπαθήσουμε να παρουσιάσουμε εκτενώς το θέμα, ξεκινώντας από το βασικόθεωρητικό υπόβαθρο, τον ορισμό των κύριων στοιχείων του προβλήματος, μέχρι τηνπαρουσίαση των περισσότερων μεθόδων που έχουν αναπτυχθεί, με ειδική έμφαση στιςτεχνικές που σχεδιάστηκαν από στατιστικούς φυσικούς, από τη συζήτηση κρίσιμων θεμάτων όπως η σημασία της συσταδοποίησης και πώς οι μέθοδοι πρέπει να ελέγχονται και νασυγκρίνονται μεταξύ τους, μέχρι την περιγραφή εφαρμογών σε πραγματικά δίκτυα.
Description
Keywords
Ανίχνευση κοινοτήτων, Ανάλυση ανά τύπο δικτύου, Κοινωνικά δίκτυα, Βιοϊατρικά/χημικά δίκτυα