Ανάλυση Και Εξαγωγή Ρόλων Σε Μεγάλους Γράφους

Abstract

Σκοπός της εργασίας αυτής αποτελεί η ανάλυση της συμπεριφοράς μεγάλων γράφων και η προσπάθεια μοντελοποίησης της.Ο γράφος αποτελεί υπολογιστικό τρόπο αναπαράστασης ενός δικτύου, όπου κάθε κόμβος αντιπροσωπεύει ένα στοιχείο ή μια οντότητα του δικτύου και οι ακμές αντιπροσωπεύουν συνδέσεις και σχέσεις μεταξύ των στοιχείων.Με τον όρο συμπεριφορά, εννοούμε την προσπάθεια διαχωρισμού της λειτουργίας κάθε κόμβου που ανήκει στον γράφο. Παραδείγματα λειτουργίας ενός κόμβου μέσα στον γράφο μπορεί να είναι η κεντρικότητα, η ιδιότητα της γέφυρας, ή η πηγή μιας ροής μέσα στον γράφο. Περιλαμβάνεται επίσης η έννοια της εξέλιξης, δηλαδή πως ένας κόμβος θα μεταβεί από μια λειτουργία σε μία άλλη κατά τη διάρκεια του χρόνουΜοντελοποίηση εννοούμε την προσπάθεια εύρεσης ενός τρόπου αναπαράστασης όλων των δυνατών συμπεριφορών των κόμβων σε έναν γράφο με τέτοιο τρόπο που να ευνοείται η ομαδοποίηση, η εξαγωγή συμπερασμάτων και η ερμηνεία της κάθε πιθανής συμπεριφοράς. Στη μελέτη μας, ο τρόπος μοντελοποίησης που εξετάζουμε είναι η ανάλυση και εξαγωγή ρόλων και επικεντρωνόμαστε κυρίως σε κοινωνικά δίκτυα.Ρόλος είναι ένας τρόπος ομαδοποίησης συγκεκριμένων λειτουργιών και χαρακτηριστικών ενός κόμβου ή μιας ακμής. Με τον τρόπο αυτό, κόμβοι, ή ακμές με συγκεκριμένες λειτουργίες και χαρακτηριστικά τα οποία έχουν προκαθοριστεί, ομαδοποιούνται και θα ανήκουν στον ίδιο ρόλο.Τελικά όλες οι παραπάνω διαδικασίες, μπορούν να αναχθούν σε πράξεις πάνω σε γράφους.Αρχικά προσπαθήσαμε να ακολουθήσουμε ένα μέρος της ερευνητικής πορείας προκειμένου να ορίσουμε ορθά το πρόβλημα. Έγινε προσπάθεια σύνδεσης της εργασίας με την εξέλιξη ενός δικτύου. Μέσα από αυτή την ανάλυση προέκυψε, ως μοντέλο περιγραφής της συμπεριφοράς του δικτύου, η εξαγωγή και η ανάλυση ρόλων.Αφού αναλύσαμε πλήρως την έννοια του ρόλου και της ισοδυναμίας, τόσο σε κοινωνικό, όσο και σε μαθηματικό και τεχνικό επίπεδο, παρουσιάσαμε μερικά μαθηματικά μοντέλα εφαρμογής τους. Δόθηκε μεγαλύτερη έμφαση σε ένα από τα μοντέλα - αλγόριθμους, προκειμένου να αναλυθεί η λειτουργία του.Προέκυψαν έτσι δύο επιμέρους αλγόριθμοι, ένας για ανάλυση χαρακτηριστικών και ένας για την εξαγωγή ρόλων, ο Refex και ο Rolx. Αναλύσαμε τι σημαίνει αναπαράσταση γράφου με χαρακτηριστικά, τι σημαίνουν τα χαρακτηριστικά και εξηγήσαμε τους επιμέρους υπολογισμούς των αλγορίθμων.Στο τελικό στάδιο πραγματοποιήσαμε δύο πειράματα με εκτελέσεις των αλγορίθμων. Έγινε στατιστική ανάλυση των δεδομένων εισόδου, των παραμέτρων καθώς και τον αποτελεσμάτων και προσπαθήσαμε να εξαγάγουμε κάποια συμπεράσματα.Τέλος αναφέραμε πρακτικές εφαρμογές και βελτιώσεις των παραπάνω εργαλείων.