Χρήση γενετικών αλγορίθμων για τον εντοπισμό κοινοτήτων και ομάδων χρηστών στα μέσα κοινωνικής δικτύωσης
| dc.contributor.advisor | Λιαγκούρας, Κωνσταντίνος | |
| dc.contributor.author | Πηλιούνης, Σπυρίδων | |
| dc.date.accessioned | 2025-06-17T12:11:27Z | |
| dc.date.available | 2025-06-17T12:11:27Z | |
| dc.date.issued | 2025-06 | |
| dc.identifier.uri | https://dione.lib.unipi.gr/xmlui/handle/unipi/17851 | |
| dc.description.abstract | Η αναγνώριση κοινοτήτων και ομάδων χρηστών μέσα στα κοινωνικά δίκτυα, - Communities & User-Groups Identification in Social Networks [25], είναι ένα ουσιαστικό ζητούμενο σήμερα στην επιστήμη των μεγάλων δεδομένων, με εφαρμογές που εκτείνονται από το μάρκετινγκ και τα συστήματα παροχής συμβουλών και εκτιμήσεων για διαφόρων ειδών θεματολογικές κατηγορίες έως την κυβερνοασφάλεια και την επιδημιολογία. Μια κοινότητα σε ένα κοινωνικό δίκτυο ορίζεται συνήθως ως ένα υποσύνολο κόμβων που παρουσιάζουν πυκνότερες συνδέσεις μέσα στην ομάδα σε σύγκριση με το υπόλοιπο δίκτυο. Λόγω της μεγάλης έκτασης αλλά και της πολυπλοκότητας των σύγχρονων κοινωνικών δικτύων, υπάρχει ανάγκη για αποτελεσματικές και κλιμακούμενες από πλευράς απόδοσης μεθόδους για αυτή την εργασία επισήμανσης τέτοιων ομάδων. Παραδοσιακοί αλγόριθμοι συσταδοποίησης (clustering) βασισμένοι σε γράφους όπως η ιεραρχική συσταδοποίηση, η φασματική (spectral) συσταδοποίηση και η σπονδυλωτή συσταδοποίηση (modularity), έχουν διερευνηθεί αρκετά αλλά συχνά αντιμετωπίζουν προβλήματα όταν επιχειρείται η ανάλυση μεγάλης κλίμακας, δυναμικών και επικαλυπτόμενων κοινοτήτων. Οι Εξελικτικοί Αλγόριθμοί και ειδικότερα οι Γενετικοί Αλγόριθμοι (GA), έχουν αναδυθεί πλέον ως μια ισχυρή εναλλακτική προσέγγιση για την επίλυση του προβλήματος της ανίχνευσης κοινοτήτων και ομάδων. Οι Γενετικοί Αλγόριθμοι, ως έννοια στην θεωρητική πληροφορική παρουσιάζονται για πρώτη φορά από τον John Holland (1975) [22] ως μια ευριστική μέθοδος βελτιστοποίησης εμπνευσμένη από τη φυσική επιλογή και έχει χρησιμοποιηθεί σε ευρεία κλίμακα για την επίλυση πολύπλοκων συνδυαστικών προβλημάτων βελτιστοποίησης. Η ευελιξία των GA τους επιτρέπει να εξερευνούν τεράστιους χώρους από πιθανές λύσεις για την ταυτοποίηση ενός ζητούμενου τύπου ή μοτίβου κοινότητας ή ομάδας μέσα σε ένα Κ.Δ., ενώ σταδιακά αυτό-εξελίσσονται αποτελεσματικά ώστε να εντοπίζουν συνεχώς και καλύτερα τέτοια μοτίβα κοινοτήτων. Κωδικοποιούν πιθανές δομές κοινοτήτων σαν να είναι άτομα μέσα σε έναν πληθυσμό, εφαρμόζοντας τεχνικές διασταύρωσης και μετάλλαξης για τη δημιουργία νέων λύσεων. Χρησιμοποιούν στη συνέχεια συναρτήσεις fitness (στατιστική ταιριάσματος) για την αξιολόγηση της λύσης βάση (αναλογικά) του βαθμού της σπονδυλωτής συσταδοποίησης (modularity [23]), ή (αντιστρόφως ανάλογα) της αγωγιμότητας (conductance [24]) που είναι βασικές μετρικές, μαζί και με κάποιες άλλες, του πόσο πολύ ένα group που επιχειρείται να πιστοποιηθεί απέχει από το υπόλοιπο υπό μελέτη SN αναφορικά με κάποια χαρακτηριστικά του. Σε αντίθεση με τους παραδοσιακούς αιτιοκρατικής φύσης αλγόριθμους, οι GA εισάγουν στοχαστική (στατιστικού τύπου) εξερεύνηση του SN. Το χαρακτηριστικό αυτό τα καθιστά περισσότερο κατάλληλα για την ανίχνευση επικαλυπτόμενων πολλαπλών υπό-ομάδων χρηστών, καθώς και κοινοτήτων που έχουν δυναμικά μοτίβα εξέλιξης. Οι πρώιμες υλοποιήσεις GΑ έγιναν με υπολογιστικό προσανατολισμό την βελτιστοποίηση (maximization) του modularity σε στατικά δίκτυα, ενώ οι μεταγενέστερες εξελίξεις έχουν ενσωματώσει και μεθόδους βελτιστοποίησης πολλών στόχων, υβριδικές ευριστικές μεθόδους και μεθόδους δυναμικής προσαρμογής για την αντιμετώπιση της εξελικτικής φύσης των πραγματικών δικτύων. Επιπλέον, πρόσφατες μελέτες έχουν διερευνήσει, και η έρευνα είναι ανοιχτή, την διασύνδεση των GA με τεχνικές Μηχανικής Μάθησης (ML) για τη βελτίωση της ακρίβειας και της υπολογιστικής αποδοτικότητας των μεθόδων. Ωστόσο, προκλήσεις όπως η δυναμική ρύθμιση των παραμέτρων των αλγορίθμων καθώς και ο έλεγχος της σύγκλισης (δηλαδή εάν κάπου πάει να καταλήξει το μοντέλο που ‘τρέχει), μαζί βεβαίως και το υπολογιστικό κόστος του μοντέλου που ‘τρέχει’, παραμένουν ενεργές περιοχές έρευνας. Η χρήση των GA στην ανίχνευση κοινοτήτων παρέχει πολλά πλεονεκτήματα σε σύγκριση με τις παραδοσιακές μεθόδους. 1. Οι GA επιτρέπουν μια ολιστικού τύπου αναζήτηση σε ένα περιβάλλον δεδομένων με αρκετή πολυπλοκότητα, ώστε να προκύπτει καλό fitness (το πόσο αποτελεσματική δηλαδή μια υποψήφια λύση είναι, με βάση την αξιολόγηση των παραμέτρων modularity και conductance που προαναφέραμε), αποφεύγοντας παραπλανητικά τοπικά βέλτιστα, που συνήθως συμβαίνουν με τη χρήση παραδοσιακών μεθόδων συσταδοποίησης. 2. Οι GA αλγόριθμοι είναι εγγενώς παραλληλοποιήσιμοι. Αυτό σε επίπεδο κώδικα σημαίνει ότι με κατανεμημένες υπολογιστικές διαδικασίες, many-threads, many-cores, many-machines, μπορούν να χειριστούν αποτελεσματικά και γρήγορα δίκτυα μεγάλης κλίμακας. 3. Oι GA προσφέρουν ευελιξία στην ενσωμάτωση ευριστικών παραμέτρων, συνθηκών και περιορισμών, κατάλληλο για τον κάθε υπό έρευνα τομέα Κοινωνικών Δικτύων, πράγμα που τους καθιστά προσαρμόσιμους για εξειδικευμένες αναζητήσεις όπως η ανίχνευση απάτης μέσα σε τεράστιου όγκου οικονομικά και λογιστικά δεδομένα, η ανάλυση πολιτικών προτιμήσεων/τάσεων, αλλά και οι μοντελοποιήσεις επιδημιολογικού τύπου. Επιπλέον, τα υβριδικά μοντέλα που συνδυάζουν GA με άλλες στρατηγικές βελτιστοποίησης έχουν κερδίσει έδαφος τα τελευταία χρόνια. Για παράδειγμα, μέσω της χρήσης memetic αλγόριθμων, ενσωματώνονται στους GA μηχανισμοί τοπικής αναζήτησης που βελτιώνουν δραματικά την διακριτοποίηση ομάδων και κοινοτήτων μετά την δημιουργία κάποιων αρχικών λύσεων. Άλλες υβριδικές προσεγγίσεις ενσωματώνουν μεθόδους «νοημοσύνης σμήνους», όπως η Βελτιστοποίηση Σμήνους Σωματιδίων (PSO) και η Βελτιστοποίηση Αποικίας Μυρμηγκιών (ACO). Αυτές οι υβριδικές μέθοδοι έχουν επιδείξει βελτιωμένη ακρίβεια και υπολογιστική αποδοτικότητα σε σύνολα δεδομένων μεγάλης κλίμακας. Πέρα από τα στατικά δίκτυα (εκείνα όπου τα nodes και τα edges τους παραμένουν σχετικά αναλλοίωτα στον χρόνο μέσα στον γράφο που τα απεικονίζει και τα ‘φιλοξενεί’, π.χ. Facebook), τα δυναμικά και εξελικτικά κοινωνικά δίκτυα (εκείνα όπου τα nodes & edges αλλάζουν συνεχώς, π.χ. tweeter) παρουσιάζουν πρόσθετες προκλήσεις, απαιτώντας προσαρμοστικές προσεγγίσεις βασισμένες σε GA. Οι δομές κοινοτήτων στα κοινωνικά δίκτυα δεν είναι στατικές και εξελίσσονται λόγω των συνεχών αλληλεπιδράσεων των χρηστών, των αναδυόμενων τάσεων και των εξωτερικών επιρροών. Οι Προσαρμοστικοί Γενετικοί Αλγόριθμοι (AGA [26]) έχουν αναπτυχθεί για την αντιμετώπιση αυτού του ζητήματος, στη βάση ειδικών λογισμικών, που υλοποιούν μηχανισμούς χρονοεξαρτώμενης αξιολόγησης του fitness [27] [28] [29], μηχανισμούς σταδιακά αυξανόμενης μάθησης και μηχανισμούς αυτόματης προσαρμογής του ρυθμού μάθησης μετά από κάθε μετάλλαξη του GA. Αυτές οι μέθοδοι είναι ιδιαίτερα εφαρμόσιμες σε τομείς όπου η παρακολούθηση κοινοτήτων σε πραγματικό χρόνο είναι απαραίτητη, όπως στον συντονισμό κρίσεων, στην ανάλυση κοινωνικών μέσων σε πραγματικό χρόνο και στην ανίχνευση απειλών κυβερνοασφάλειας. Σε αυτή την εργασία θα παρουσιάσουμε μια κατά το δυνατόν πλήρως αντιπροσωπευτική βιβλιογραφική εικόνα των εφαρμογών των Γενετικών Αλγορίθμων στην ανίχνευση κοινοτήτων και ομάδων στα Κοινωνικά Δίκτυα, με αναφορά στην εξέλιξη και στην τρέχουσα έρευνα σε αυτόν τον τομέα, εστιάζοντας στις διαφορετικές προσεγγίσεις υλοποίησής τους. Θα βασιστούμε στην ιστορία χρήσης των GA για ανίχνευση κοινοτήτων στα SNs έως σήμερα και θα αναπτύξουμε, τεκμηριώσουμε και αναλύσουμε συγκριτικά τις τεχνικές που χρησιμοποιούνται, αλλά και τις τάσεις που ήδη υλοποιούνται για εξέλιξη των μεθόδων χρήσης των GA. Καθώς και τα όποια κενά και αδυναμίες των σχετικών μεθόδων. Βασικό τμήμα της εργασίας αυτής αποτελεί η παρουσίαση της διεμπλοκής, της υπολογιστικής φιλοσοφίας και της μαθηματικής και προγραμματιστικής υλοποίησης των, • GA, αλγορίθμων Εξελικτικού Τύπου (Evolutionary Algorithms), με εκείνες των • CA - Κυψελοειδών Αυτόματων, (που συνιστούν διαφορετική μορφή Εξελικτικών Αλγορίθμων, όχι όμως με την στενή έννοια του όρου, αλλά με δραστικότερα χαρακτηριστικά σε τοπικές ανιχνεύσεις), επάνω στην χρήση των μοντέλων τους για την διερεύνηση των Κοινωνικών Δικτύων. Επίσης, μέσα στον απέραντο χώρο των Κοινωνικών Δικτύων έχει δειχθεί ότι υπάρχουν και ομάδες ή κοινότητες που έχουν «φαντασμική» παρουσία, υπό την έννοια ότι τα edges που συνδέουν τους συσχετιζόμενους κόμβους είναι πολύ μεγάλα space-vectors, ενώ οι κόμβοι – nodes έχουν εξαιρετικά μεγάλη διασπορά. Διερευνούμε λοιπόν, αλλά σε μικρό βιβλιογραφικό εύρος και αυτή την περίπτωση. Στόχος της εργασίας μας εδώ μας είναι να παρέχουμε στους ερευνητές μια δομημένη επισκόπηση του τρόπου με τον οποίο οι Γενετικοί Αλγόριθμοι και οι επεκταμένες υλοποιήσεις τους έχουν συνεισφέρει στην πρόοδο της ανάλυσης των Κοινωνικών Δικτύων [53], ενώ ταυτόχρονα να υποδείξουμε τα κενά και τις προκλήσεις για περαιτέρω έρευνα και ανάπτυξη. Θα επιχειρήσουμε τέλος μια υπολογιστική υλοποίηση ενός τέτοιου αλγορίθμου μέσω της κατασκευής μιας εφαρμογής σε C++ που θα διερευνήσει πραγματικά δεδομένα Κοινωνικού Δικτύου, ώστε να φανεί στην πράξη η δυναμική των Αλγορίθμων αυτών. | el |
| dc.format.extent | 145 | el |
| dc.language.iso | el | el |
| dc.publisher | Πανεπιστήμιο Πειραιώς | el |
| dc.rights | Αναφορά Δημιουργού-Μη Εμπορική Χρήση-Όχι Παράγωγα Έργα 3.0 Ελλάδα | * |
| dc.rights.uri | http://creativecommons.org/licenses/by-nc-nd/3.0/gr/ | * |
| dc.title | Χρήση γενετικών αλγορίθμων για τον εντοπισμό κοινοτήτων και ομάδων χρηστών στα μέσα κοινωνικής δικτύωσης | el |
| dc.title.alternative | Use of genetic algorithms to identify communities and user groups in social networks | el |
| dc.type | Bachelor Dissertation | el |
| dc.contributor.department | Σχολή Τεχνολογιών Πληροφορικής και Επικοινωνιών. Τμήμα Πληροφορικής | el |
| dc.description.abstractEN | The identification of communities and user groups within social networks – Communities & User-Groups Identification in Social Networks [25] – is a crucial challenge today in big data science, with applications ranging from marketing and recommendation systems for various thematic categories to cybersecurity and epidemiology. A community in a social network is typically defined as a subset of nodes with denser connections within the group compared to the rest of the network. Due to the vast scale and complexity of modern social networks, there is a need for efficient and scalable methods to detect such groups. Traditional graph-based clustering algorithms such as hierarchical clustering, spectral clustering, and modularity-based clustering have been extensively explored but often face issues when analyzing large-scale, dynamic, and overlapping communities. Evolutionary Algorithms, and more specifically Genetic Algorithms (GAs), have emerged as a powerful alternative approach to solve the problem of community and group detection. Genetic Algorithms, introduced by John Holland (1975) [22], are a heuristic optimization method inspired by natural selection, widely used to solve complex combinatorial optimization problems. The flexibility of GAs allows them to explore vast spaces of possible solutions for identifying desired types or patterns of communities or groups within a social network (SN), while gradually evolving to more effectively detect such patterns. They encode potential community structures as individuals in a population, applying crossover and mutation techniques to create new solutions. Then they evaluate these solutions using fitness functions based on metrics like modularity [23] (positively correlated) and conductance [24] (negatively correlated), among others, which assess how distinct a proposed group is from the rest of the network in terms of specific features. Unlike deterministic traditional algorithms, GAs introduce stochastic (statistical) exploration of the SN, making them more suitable for detecting overlapping and dynamically evolving sub-groups and communities. Early GA implementations focused on maximizing modularity in static networks, while more recent developments have incorporated multi-objective optimization, hybrid heuristic methods, and dynamic adaptation techniques to better address the evolving nature of real-world networks. Recent research also explores the integration of GAs with Machine Learning (ML) techniques to improve the accuracy and computational efficiency of detection methods. However, challenges remain, including dynamic parameter tuning, convergence control (i.e., whether the running model is reaching a conclusion), and the computational cost of the running model. Advantages of using GAs for community detection compared to traditional methods include: Holistic search capability: GAs can effectively explore complex data environments to find high-fitness solutions (i.e., effective candidate community structures based on modularity and conductance), avoiding misleading local optima commonly encountered with traditional clustering methods. Inherent parallelism: GAs are naturally parallelizable. In code terms, this means that using distributed computation (many-threads, many-cores, many-machines), they can efficiently handle large-scale networks. Flexibility and adaptability: GAs allow integration of heuristic parameters, conditions, and constraints tailored to specific domains of social network research. This adaptability makes them suitable for specialized tasks such as fraud detection in massive financial/accounting datasets, political preference/trend analysis, and epidemiological modeling. Hybrid models combining GAs with other optimization strategies have gained traction in recent years. For instance, memetic algorithms incorporate local search mechanisms into GAs, significantly improving the refinement of community structures after generating initial solutions. Other hybrid approaches combine swarm intelligence methods such as Particle Swarm Optimization (PSO) and Ant Colony Optimization (ACO), showing enhanced accuracy and computational performance in large-scale datasets. Beyond static networks (where nodes and edges remain relatively stable over time, e.g., Facebook), dynamic and evolutionary social networks (e.g., Twitter) pose additional challenges, requiring adaptive GA-based approaches. Community structures in social networks evolve due to ongoing user interactions, emerging trends, and external influences. Adaptive Genetic Algorithms (AGAs) [26] have been developed to address this, incorporating time-dependent fitness evaluation mechanisms [27][28][29], gradually increasing learning mechanisms, and automated learning rate adjustments after each mutation. These methods are particularly applicable in real-time community tracking scenarios, such as crisis coordination, live social media analysis, and cyber threat detection. This study aims to present a comprehensive literature review of GA applications in detecting communities and groups within Social Networks, referencing the evolution and current research in this field, and focusing on different implementation approaches. It will rely on the history of GA use in SNs to date, and will document and comparatively analyze the techniques employed, as well as current trends and developments. It will also highlight the gaps and limitations in these methods. A key part of this work involves examining the interplay, computational philosophy, and mathematical/programmatic implementation of: GA (Genetic Algorithms), a type of Evolutionary Algorithm, and CA (Cellular Automata), which, while not strictly GAs, represent a different evolutionary model with stronger capabilities in localized detection, in the context of their application to social network analysis. Moreover, within the vast space of social networks, it has been shown that there exist "phantom" communities – groups whose associated edges are very large space-vectors, and whose nodes exhibit significant dispersion. We explore this special case briefly through a limited literature scope. Our goal is to offer researchers a structured overview of how Genetic Algorithms and their extended implementations have contributed to the advancement of Social Network analysis [53], while also pointing out current gaps and challenges for future research and development. Finally, we aim to implement such an algorithm computationally through the development of a C++ application that will analyze real social network data, in order to demonstrate the practical potential of these algorithms. | el |
| dc.subject.keyword | Γενιτικοί | el |
| dc.subject.keyword | Αλγόριθμοι | el |
| dc.subject.keyword | Κοινότητες | el |
| dc.subject.keyword | Ομάδες χρηστών | el |
| dc.subject.keyword | Μέσα κοινωνικής δικτύωσης | el |
| dc.subject.keyword | CA | el |
| dc.subject.keyword | GA | el |
| dc.subject.keyword | Phantom communities | el |
| dc.subject.keyword | Κυψελωτά αυτόματα | el |
| dc.subject.keyword | Phantom groups | |
| dc.date.defense | 2025-06-12 |
Αρχεία σε αυτό το τεκμήριο
Αυτό το τεκμήριο εμφανίζεται στις ακόλουθες συλλογές
Εκτός από όπου διευκρινίζεται διαφορετικά, το τεκμήριο διανέμεται με την ακόλουθη άδεια:
Αναφορά Δημιουργού-Μη Εμπορική Χρήση-Όχι Παράγωγα Έργα 3.0 Ελλάδα
Αναφορά Δημιουργού-Μη Εμπορική Χρήση-Όχι Παράγωγα Έργα 3.0 Ελλάδα