Please use this identifier to cite or link to this item: http://hdl.handle.net/10889/13170
Title: Πρόβλεψη κοινοτήτων σε γραφήματα κοινωνικών δικτύων χρήσει τεχνικών συνδυαστικής μηχανικής μάθησης και βάσει του αλγόριθμου Blondel
Other Titles: Community detection in social media graphs using ensemble machine learning techniques and based on the Blondel algorithm.
Authors: Ρίζος, Ιωάννης Ορέστης
Keywords: Ανίχνευση κοινοτήτων
Μηχανική μάθηση
Πρόβλεψη κοινοτήτων
Αλγόριθμος Louvain
Συνδυαστική μάθηση
Συστάδες
Λογιστική παλινδρόμηση
Keywords (translated): Community detection
Machine learning
Community prediction
Louvain algorithm
Ensemble learning
Clustering
Logistic regression
Abstract: Η οργάνωση των κόμβων σε σύνολα από συστάδες, είναι ένα από τα πιο πολύτιμα χαρακτηριστικά μελέτης της ανάλυσης γραφημάτων και της κατανόησης πολυσύνθετων συστημάτων, εμφανίζοντας χρησιμότητα σε ένα ευρύ φάσμα ερευνητικών πεδίων. Με την εκρηκτική αύξηση της χρήση τον μέσων κοινωνικής δικτύωσης, η ανίχνευση της κοινοτικής δομής και η λύση του προβλήματος αυτού με αποδοτικό τρόπο ποτέ δεν ήταν πιο επίκαιρη αλλά ταυτόχρονα και πιο απαιτητική, εξαιτίας του τεράστιου μεγέθους των δικτύων αυτών. Η χρήση κλασσικών μεθόδων και αλγορίθμων ανίχνευσης κοινοτήτων καταλήγει πολύ συχνά να είναι ανέφικτη λόγω της έλλειψης κλιμάκωσης που αυτοί παρουσιάζουν. Σύγχρονα βήματα στον τομέα των τεχνικών πρόβλεψης συνδέσεων, προσεγγίζουν το πρόβλημα εξαγωγής κοινοτικής δομής, αξιοποιώντας εργαλεία κατανεμημένης μηχανικής μάθησης. Τα αποτελέσματα των ερευνών αυτών, έχουν δείξει πως η εξαγωγή της κοινοτικής πληροφορίας με χρήση τεχνικών πρόβλεψης συνδέσεων είναι μια εφαρμόσιμη εναλλακτική μέθοδος προσέγγισής αυτού του NP-hard προβλήματος, εμφανίζοντας ικανοποιητική ακρίβεια ταξινόμησης, διατηρώντας παράλληλα την αποδοτικότητα των κατανεμημένων μοντέλων. Ένα ακόμα πεδίο με αυξανόμενο ερευνητικό ενδιαφέρον είναι η χρήση τεχνικών συνδυαστικής μάθησης αποσκοπώντας την αύξηση της απόδοσης μοντέλων επιβλεπομένης μάθησης. Ο βασικός στόχος της παρούσας διπλωματικής είναι να προταθεί μια βελτιστοποιημένη μεθοδολογία ανίχνευσης κοινοτήτων, χρησιμοποιώντας την υπάρχουσα ως βάση, και εξελίσσοντας την, εισάγοντας τις τεχνικές συνδυαστικής μηχανικής μάθησης. Το κύριο σημείο συμφόρησης που επιχειρείται να ξεπεραστεί είναι αυτό της υπερβολικής τοπολογικής ανομοιογένειας που παρουσιάζουν τα πολύ μεγάλα κοινωνικά δίκτυα, και που ένα μονάχα μικρό αντιπροσωπευτικό υπογράφημα ως σύνολο εκπαίδευσης δεν μπορεί να συλλάβει. Προτείνουμε λοιπόν πως η χρήση ensemble μοντέλων μάθησης, σε συνδυασμό με την αντικατάσταση του “αντιπροσωπευτικού” υπογραφήματος με μια καλύτερη εναλλακτική υπό την μορφή πολλαπλών τυχαίων υπογραφημάτων, θα επιφέρουν μεγαλύτερη ακρίβεια στην κοινοτική δομή που εξάγεται.
Abstract (translated): The organization of vertices in sets of clusters is one of the most valuable features to the science of graph analysis and understanding of complex systems presenting great importance in wide variety of research fields. With the explosive uptick in social media usage around the world, detecting their community structure and solving the problem in an efficient manner has never been more prevalent, but also challenging due to the sheer size these types of networks represent. The standard community detection methods and algorithms are often shown to be infeasible as a result of their unscalable nature. Recent advances in link prediction techniques has approached the problem of extracting the community structure of a social network through the use of distributed supervised machine learning solutions. The results of these studies has shown that extracting community structure though link prediction is a feasible alternative in tackling this NP-hard problem, displaying fairly accurate classification metrics, while maintaining the efficiency of the distributed models. Another field of peaking interest lately is the use of ensemble learning techniques in order to increase the performance of supervised machine learning models. The main goal of this thesis is to propose an optimized methodology of community prediction, using the existing as a base, evolving it to take advantage of ensemble machine learning techniques. The main performance bottleneck we are tasked to overcome is that of the extreme topological heterogeneity large social media networks often display, that a single small representative subgraph used as a training set simply cannot capture. We are proposing that the use of ensemble learning combined with the replacement of the representative subgraph by a better alternative in the form of multiple random subgraphs, will yield the performance improvement to the accuracy of the community structure extracted.
Appears in Collections:Τμήμα Μηχανικών Η/Υ και Πληροφορικής (ΔΕ)

Files in This Item:
File Description SizeFormat 
Thesis.pdf5.88 MBAdobe PDFView/Open


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