Χρήση γενετικών αλγορίθμων για τον εντοπισμό κοινοτήτων και ομάδων χρηστών στα μέσα κοινωνικής δικτύωσης

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++ που θα διερευνήσει πραγματικά δεδομένα Κοινωνικού Δικτύου, ώστε να φανεί στην πράξη η δυναμική των Αλγορίθμων αυτών.