Community detection in signed and directed graphs

Abstract

Τις τελευταίες 2 δεκαετίες μια από τις δημοφιλέστερες μεθοδολογίες για την επεξεργασία δεδομένων είναι η μετατροπή τους σε δικτύωμα όπου οι μονάδες δεδομένων ταυτίζονται με τους κόμβους και οι σχέσεις που τις συνδέουν είναι οι ακμές του δικτυώματος. Τέτοια Δίκτυα σε ένα πρόβλημα συσταδοποίησης συνήθως αντιπροσωπεύονται από Γράφους όπου κάθε συστατικό στοιχείο αντιπροσωπεύεται από κόμβους και οι σύνδεσμοι ανάμεσα στα συστατικά στοιχεία μοντελοποιούνται με συγκεκριμένης βαρύτητας ακμές. Η συσταδοποίηση σε γράφους στοχεύει στην κατηγοριοποίηση των κόμβων ενός γράφου σε ομάδες (συστάδες) ή κοινότητες, οι κόμβοι αυτοί μοιράζονται κάποιο βαθμό ομοιότητας, ο οποίος υπολογίζεται με κριτήρια την απόσταση ανάμεσα στους κόμβους του γράφου την τοπολογική δομή αλλά και την «συμπεριφορά» ανάμεσα στους κόμβους (φίλοι ή εχθροί). Οι συστάδες αυτές μας βοηθούν να εξερευνήσουμε τις πληροφορίες που κρύβονται μέσα στα σύνολα δεδομένων. Η μεθοδολογική αυτή προσέγγιση χρησιμοποιείται ευρέως σε επιστημονικά πεδία όπου είναι απαραίτητη η μελέτη και ανάλυση συμπεριφορικών μοντέλων η κοινωνιολογικών στερεοτύπων , όπως η ανάλυση κοινωνικών δικτύων, η στατιστική ανάλυση δεδομένων, η Εξόρυξη Δεδομένων, η Μηχανική Μάθηση, ο σχεδιασμός ολοκληρωμένων κυκλωμάτων, η Βιολογία και άλλα. Η παρούσα Διπλωματική εργασία βάζει στο μελετητικό επίκεντρο τους Υπογεγραμμένους και Κατευθυντικούς γράφους και εξετάζει δύο αλγορίθμους εντοπισμού κοινοτήτων που συσταδοποιούν κόμβους με παρόμοια χαρακτηριστικά , ο σκοπός της διαδικασίας είναι η ανάδειξη του βαθμού ομοιότητας ως το κύριο και πιο σημαντικό παράγοντα συσταδοποίησης γράφων ανάμεσα σε κόμβους με βάση το μοτίβο συνδεσιμότητας ακολουθώντας ταυτόχρονα και την κατευθυντικότητα αλλά και την πόλωση των συνδέσμων που τους διασυνδέουν. Στο αρχικό στάδιο εργαστήκαμε παράλληλα με τους θετικούς και αρνητικούς υπογράφους συγκεκριμένων συνόλων δεδομένων για κάθε υπογράφο εφαρμόσαμε τις μεθοδολογικές προσεγγίσεις Coupling (Reference) και Cocitation αναλύοντας αναφορές και συνδέσεις μεταξύ των κόμβων για υπολογίσουμε τους ανάλογους πίνακες η διαδικασία συνεχίστηκε με τον υπολογισμό του Πίνακα ομοιότητας και τις αναγκαίες κανονικοποιήσεις παίρνοντας υπόψη το βαθμό κάθε κόμβου αλλά και την επιστημονική εργασία του Αμσλερ που ανέδειξε ότι οι μεθοδολογικές προσεγγίσεις Coupling (Reference) και Cocitation μπορούν να συνδυαστούν. Τέλος εφαρμόσαμε δύο αλγορίθμους συσταδοποίησης affinity propagation και spectral clustering, τόσο ανεξάρτητα όσο και σε συνδυασμό. Στη Διπλωματική παρέχουμε μια ολοκληρωμένη εφαρμογή των προτεινόμενων αλγορίθμων σε Python και τα σύνολα δεδομένων πάνω στα οποία εργαστήκαμε για να αξιολογήσουμε την δουλειά που έγινε σε επίπεδο ακρίβειας και ορθότητας. Δείξαμε ότι οι αλγόριθμοι αυτοί απέδωσαν τα αναμενόμενα από την θεωρία αποτελέσματα τόσο σε τυχαία παραγόμενους γράφους αλλά και σε δεδομένα πραγματικών δικτυωμάτων.