Εύρεση κοινοτήτων σε δίκτυα
Authors: Μπάλτσου Γεωργία 
Published: March 2023

Στις μέρες μας, τα δίκτυα χρησιμοποιούνται για την αναπαράσταση δεδομένων σχεδόν σε κάθε τομέα, όπως η βιολογία, οι μετακινήσεις, η κοινωνιολογία, οι αγοραπωλησίες κ.ά.. Αυτό συμβαίνει διότι τα δίκτυα αποτελούν έναν εύχρηστο τρόπο μελέτης των δεδομένων καθώς και των μεταξύ τους σχέσεων μέσω των μεθόδων που συνιστούν την ανάλυση δικτύων. Πιο συγκεκριμένα, τα δεδομένα αναπαρίστονται από οντότητες που ονομάζονται κόμβοι και τις μεταξύ τους συσχετίσεις που ονομάζονται ακμές.Ειδικότερα, στα δίκτυα συνήθως προκύπτουν ορισμένες ομάδες οντοτήτων (κόμβων) που έχουν ιδιαίτερη σημασία, και σχηματίζουν τις επονομαζόμενες κοινότητες. Οι κοινότητες έχουν ιδιαίτερη σημασία επειδή σχετίζονται με λειτουργικά κομμάτια του δικτύου. Συνεπώς, η εύρεση κοινοτήτων, αποτελεί σημαντικό ερευνητικό πεδίο του ευρύτερου αντικειμένου της ανάλυσης δικτύων. Για το σκοπό αυτό, η παρούσα διατριβή αντιμετωπίζει τρία καίρια προβλήματα που σχετίζονται με την εύρεση κοινοτήτων σε δίκτυα. Το πρώτο μέρος της διατριβής ασχολείται με τον εντοπισμό τοπικών κοινοτήτων όπου η διαδικασία εύρεσης τους ξεκινά από σημαντικές οντότητες με υποδείξεις (hints). Αυτές οι πρόσθετες πληροφορίες σχετικά με τη σημασία ορισμένων οντοτήτων μπορούν να αξιοποιηθούν για τον εντοπισμό καλύτερων και πιο σχετικών κοινοτήτων και μπορεί να δίνονται από έναν ειδικό επί του τομέα ή μπορεί να προκύπτουν από επιπλέον πληροφορίες του δικτύου. Ως εκ τούτου, προτείνεται το πλαίσιο Hint Enhancement Framework (HEF), το οποίο εφαρμόζει μια διαδικασία μερικών βημάτων για να ανακαλύψει την κοινότητα των οντοτήτων με υποδείξεις. Ειδικότερα, το συγκεκριμένο πλαίσιο πραγματοποιεί τροποποίηση υφιστάμενων γραφημάτων, προκειμένου οι κοινότητες που μας ενδιαφέρουν να γίνουν πιο εύκολα αναγνωρίσιμες αλλά και πιο ισχυρές. Πιο συγκεκριμένα, γίνεται είτε αλλαγή των βαρών των ακμών των γράφων, είτε αλλαγή των τιμών των μετρικών που λαμβάνονται υπόψη για την ένταξη ενός κόμβου σε μια κοινότητα ή όχι, έτσι ώστε να ενισχυθούν συγκεκριμένοι κόμβοι ενδιαφέροντος. Η αλλαγή των βαρών γίνεται με κάποια μέθοδο επανυπολογισμού βαρών, για παράδειγμα με βάση τα τρίγωνα στα οποία συμμετέχουν οι προσκείμενες ακμές των κόμβων ενδιαφέροντος. Για την αξιολόγηση του HEF ήταν απαραίτητη και η αναζήτηση κατάλληλων συνόλων δεδομένων προκειμένου να διεξαχθούν πειράματα. Ειδικότερα, χρησιμοποιήθηκαν τόσο συνθετικά όσο και πραγματικά σύνολα δεδομένων για την όσο το δυνατόν αντικειμενικότερη αξιολόγηση. Το τελευταίο κομμάτι του πρώτου μέρους της διπλωματικής εργασίας ασχολείται με το πρόβλημα της εύρεσης κοινοτήτων σε δυναμικά δίκτυα. Ειδικότερα, προτείνεται ένα πλαίσιο εύρεσης της κοινότητας στην οποία ανήκει ένα σύνολο κόμβων ιδιαίτερης σημασίας, που ονομάζονται άγκυρες (anchors), καθώς και η εξέλιξη του με την πάροδο του χρόνου. Ειδικότερα, οι κόμβοι "άγκυρες" αποτελούν επέκταση της ιδέας των “hints” προς εφαρμογή σε χρονικώς μεταβαλλόμενα δίκτυα καθώς θεωρείται πως οι κόμβοι-hints ουσιαστικά ορίζουν την κοινότητα και ως εκ τούτου μπορούν με ένα φυσικό τρόπο να εφαρμοσθούν στην περίπτωση που το δίκτυο αλλάζει. Από την εργασία αυτή προέκυψε ένα πλαίσιο το οποίο μπορεί να εντοπίζει τοπικές κοινότητες συγκεκριμένων κόμβων ενδιαφέροντος σε ροές γραφημάτων.Το δεύτερο μέρος της εργασίας επικεντρώνεται στην ανακάλυψη αιτιότητας μεταξύ οντοτήτων (κόμβων) και κοινοτήτων, γεγονός που προσθέτει αξία στο πρόβλημα εύρεσης κοινοτήτων στα δίκτυα. Πιο συγκεκριμένα, παρουσιάζεται ένα πλαίσιο που προσδιορίζει τις αιτίες της συμμετοχής (ή μη) ενός κόμβου σε μια κοινότητα. Δηλαδή, γιατί ένας κόμβος ανήκει σε μια συγκεκριμένη κοινότητα (ή όχι) και ποιες είναι οι σχέσεις (ακμές) που επηρεάζουν την συμμετοχή (ή μη) αυτού στην κοινότητα; Το συγκεκριμένο ζήτημα είναι η πρώτη φορά που εξετάζεται στο πλαίσιο της εύρεσης κοινοτήτων σε δίκτυα. Από την εργασία αυτή προέκυψε ένα πλαίσιο μερικών βημάτων το οποίο δύναται να εντοπίζει σχέσεις αιτιότητας κόμβου-κοινότητας. Και σε αυτήν την περίπτωση πραγματοποιήθηκε πειραματική αξιολόγηση του προτεινόμενου πλαίσιο με ενθαρρυντικά αποτελέσματα.Το τελευταίο κομμάτι της διατριβής, αποτελεί μια συνολική έρευνα στο κομμάτι της τοπικής εύρεσης κοινοτήτων σε δίκτυα. Πιο συγκεκριμένα, από την ενασχόληση με αλγορίθμους και μεθόδους τοπικής εύρεσης κοινοτήτων τα τελευταία τέσσερα χρόνια, προέκυψε η ανάγκη δημιουργίας μιας εκτενούς εργασίας όπου θα υπάρχουν συγκεντρωμένες οι κυριότερες εργασίες πάνω στο αντικείμενο της τοπικής εύρεσης κοινοτήτων σε δίκτυα, καθώς δεν υπάρχει αντίστοιχη εκτενής εργασία. Ειδικότερα, συγκεντρώθηκαν όλες οι σημαντικές εργασίες πάνω στην τοπική εύρεση κοινοτήτων σε όλων των ειδών τα δίκτυα (στατικά, δυναμικά, ροές γραφημάτων) με έμφαση στην τελευταία δεκαετία (2012-2022), και ταξινομήθηκαν προκειμένου να βοηθήσουν τον εκάστοτε ενδιαφερόμενο ερευνητή να εντοπίζει εύκολα τη μέθοδο που ταιριάζει καλύτερα στα ερευνητικά του ερωτήματα. Παράλληλα, συγκεντρώθηκαν και παρουσιάζονται τα σημαντικότερα εργαλεία που βοηθούν στην συγκεκριμένη κατεύθυνση αλλά και τα πιο συχνά χρησιμοποιούμενα πραγματικά δεδομένα για αξιολόγηση των μεθόδων. Τέλος, παρουσιάζονται για κάθε μέθοδο τα σημαντικότερα χαρακτηριστικά της αλλά και η διαθεσιμότητα του κώδικα υλοποίησης προκειμένου να γίνεται ακόμη πιο εύκολη η επιλογή προσέγγισης των ενδιαφερόμενων ερευνητών.