Εμπειρική μελέτη ανίχνευσης κοινοτήτων σε γραφήματα διαφορετικού τύπου αλληλεπιδράσεων
| datacite.contributor.RelatedPerson | Σιούτας, Σπύρος | |
| datacite.contributor.RelatedPerson | Τσίχλας, Κωνσταντίνος | |
| datacite.contributor.Supervisor | Μακρής, Χρήστος | |
| dc.contributor.author | Σακκά, Χρυσάνθη-Νεφέλη | |
| dc.contributor.other | Sakka, Chrysanthi-Nefeli | |
| dc.date.accessioned | 2026-07-07T10:00:02Z | |
| dc.date.available | 2026-07-07T10:00:02Z | |
| dc.date.issued | 2026-07-02 | |
| dc.degree | graduateThesis | |
| dc.description.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), κατανεμημένα και νεφοϋπολογιστικά.Θα προσπαθήσουμε να παρουσιάσουμε εκτενώς το θέμα, ξεκινώντας από το βασικόθεωρητικό υπόβαθρο, τον ορισμό των κύριων στοιχείων του προβλήματος, μέχρι τηνπαρουσίαση των περισσότερων μεθόδων που έχουν αναπτυχθεί, με ειδική έμφαση στιςτεχνικές που σχεδιάστηκαν από στατιστικούς φυσικούς, από τη συζήτηση κρίσιμων θεμάτων όπως η σημασία της συσταδοποίησης και πώς οι μέθοδοι πρέπει να ελέγχονται και νασυγκρίνονται μεταξύ τους, μέχρι την περιγραφή εφαρμογών σε πραγματικά δίκτυα. | |
| dc.description.translatedabstract | The modern science of networks has brought significant progress in understandingcomplex systems. One of the most critical issues in modeling real-world systems using graphs lies in community detection. For the efficient processing of large-scale data, specific methodologies have been developed to predict the underlying community hierarchy in social network graphs using community detection algorithms. One of the key features of graphs representing real systems is the structure of communities or clustering, organizing vertices into clusters with many edges connecting vertices within the same cluster and relatively few edges connecting vertices from different clusters. Consequently, network analysis techniques have been widely adopted for their inherent efficiency in handling hierarchical data, and applications of graph theory have attracted significant scientific interest. Community detection is of great importance in sociology, biology, and computer science, fields where systems are often represented as graphs, as well as domains such as marketing and hierarchical structure analysis.The literature spans multiple families of methods — from classical modularity heuristics and divisive approaches to distributed community, evolutionary algorithms, matrix-based enhancements, and recent deep learning directions. The latter highlight scalability and richer input representations but are not implemented in this thesis.This work presents an empirical, reproducible comparison of three classicalalgorithms — Louvain, Leiden, and Girvan–Newman — on six undirected graphs: three from Stanford SNAP (citation, email, web) and three chemical/biological graphs from BioSNAP (drug–gene, drug–drug, protein). Louvain and Leiden run on the full graph; Girvan Newman on a BFS subgraph where full-graph execution is impractical. Evaluation uses structural cohesion (modularity Q, community counts, size distributions, runtime), not semantic node content, as datasets are edge lists only.Results show domain-specific behaviour: SNAP social/scientific networks yield many medium-sized communities, while BioSNAP graphs — especially dense ChCh-Miner —behave differently. Leiden typically achieves slightly higher Q and significantly lower runtime than Louvain, consistent with prior Louvain–Leiden studies on other benchmarks. Girvan– Newman serves as a historical/divisive baseline, not a full-scale peer of the agglomerative methods. The main contribution is domain-specific analysis including BioSNAP chemical graphs alongside SNAP benchmarks in one reproducible Louvain/Leiden/GN study (§1.2.1).Implementation is in Python (NetworkX, leidenalg) with a public repository. Future work includes directed or weighted graphs (edge weights), and extension to distributed or cloudscale. | |
| dc.identifier.uri | https://hdl.handle.net/10889/32353 | |
| dc.language.iso | el | |
| dc.rights | Attribution-NonCommercial-ShareAlike 3.0 Greece | en |
| dc.rights.uri | http://creativecommons.org/licenses/by-nc-sa/3.0/gr/ | |
| dc.subject | Ανίχνευση κοινοτήτων | |
| dc.subject | Ανάλυση ανά τύπο δικτύου | |
| dc.subject | Κοινωνικά δίκτυα | |
| dc.subject | Βιοϊατρικά/χημικά δίκτυα | |
| dc.subject.alternative | Community detection | |
| dc.subject.alternative | Domain-specific analysis | |
| dc.subject.alternative | Social networks | |
| dc.subject.alternative | Biomedical/chemical networks | |
| dc.title | Εμπειρική μελέτη ανίχνευσης κοινοτήτων σε γραφήματα διαφορετικού τύπου αλληλεπιδράσεων | |
| dc.title.alternative | Empirical study of community detection on graphs of different interaction types |