Community detection in signed and directed graphs / Εξαγωγή κοινοτήτων από υπογεγραμμένα κατευθυνόμενα γραφήματα

Summary

In recent 2 decades, one of the most popular methods for processing data , is to convert it to a network, where data units are vertices and their relations are the links that connects them. Such Networks in a clustering problem are usually represented as graphs where each element to be clustered is represented as a node and the distance between two elements is modeled by a certain weight on the edge linking the nodes. Graph clustering aims at partitioning a set of nodes into different groups called clusters or communities that share some form of similarity, similarity score can be formulated by using a distance-based criterion, a topology structural criterion or an “attitude” (polarity) criterion.

These clusters will help us to explore information hidden in the data, there is a wide area of applications as e.g. Social Network Analysis, Statistical Data Analysis, Machine Learning, Data mining, Consuming Behavior Analysis, VLSI design, Computer graphics and Gene analysis. This particular Thesis is putting under the spotlight Signed and Directed graphs and examines two community detection algorithms that cluster nodes with similar characteristics, the goal of the procedure is to emerge the Similarity score as the main and most important factor of Graph Clustering between nodes based on the connectivity pattern they follow including both directionality and polarity of the links which connects them.

The initial step is to work with the negative and positive subgraph of the examined Data Set. For each Subgraph we apply Coupling (Reference) and Cocitation as the Methodologies by which Directionality dominates criteria to reach Similarity and we calculate the appropriate co-citation and co-reference matrices. The Reference or bibliographic coupling Matrix of two nodes in a directed network is the number of nodes to which both these two nodes point on the other hand the Cocitation Matrix of two nodes in a directed network is the number of nodes that point to these both exact nodes. The procedure continues with the similarity Matrix calculation normalized by taking account of the degree of each node and under the influence of Amsler [Amsler, 1972] who pointed out that Co-citation and Bibliography coupling can be combined. And finally we apply two clustering algorithms affinity propagation and spectral clustering, both standalone and combined. In this Thesis, we provide a concluded implementation of these proposed algorithms in Python, and the datasets that were used to evaluate in practice their precision and certainty. We display that these two algorithms have the theoretically expected results for both random Generated signed directed graphs and real networks data sets.

Περίληψη

Τις τελευταίες 2 δεκαετίες μια από τις δημοφιλέστερες μεθοδολογίες για την επεξεργασία δεδομένων είναι η μετατροπή τους σε δικτύωμα όπου οι μονάδες δεδομένων ταυτίζονται με τους κόμβους και οι σχέσεις που τις συνδέουν είναι οι ακμές του δικτυώματος. Τέτοια Δίκτυα σε ένα πρόβλημα συσταδοποίησης συνήθως αντιπροσωπεύονται από Γράφους όπου κάθε συστατικό στοιχείο αντιπροσωπεύεται από κόμβους και οι σύνδεσμοι ανάμεσα στα συστατικά στοιχεία μοντελοποιούνται με συγκεκριμένης βαρύτητας ακμές. Η συσταδοποίηση σε γράφους στοχεύει στην κατηγοριοποίηση των κόμβων ενός γράφου σε ομάδες (συστάδες) ή κοινότητες, οι κόμβοι αυτοί μοιράζονται κάποιο βαθμό ομοιότητας, ο οποίος υπολογίζεται με κριτήρια την απόσταση ανάμεσα στους κόμβους του γράφου την τοπολογική δομή αλλά και την «συμπεριφορά» ανάμεσα στους κόμβους (φίλοι ή εχθροί).

Οι συστάδες αυτές μας βοηθούν να εξερευνήσουμε τις πληροφορίες που κρύβονται μέσα στα σύνολα δεδομένων. Η μεθοδολογική αυτή προσέγγιση χρησιμοποιείται ευρέως σε επιστημονικά πεδία όπου είναι απαραίτητη η μελέτη και ανάλυση συμπεριφορικών μοντέλων η κοινωνιολογικών στερεοτύπων, όπως η ανάλυση κοινωνικών δικτύων, η στατιστική ανάλυση δεδομένων, η Εξόρυξη Δεδομένων, η Μηχανική Μάθηση, ο σχεδιασμός ολοκληρωμένων κυκλωμάτων, η Βιολογία και άλλα. Η παρούσα Διπλωματική εργασία βάζει στο μελετητικό επίκεντρο τους Υπογεγραμμένους και Κατευθυντικούς γράφους και εξετάζει δύο αλγορίθμους εντοπισμού κοινοτήτων που συσταδοποιούν κόμβους με παρόμοια χαρακτηριστικά , ο σκοπός της διαδικασίας είναι η ανάδειξη του βαθμού ομοιότητας ως το κύριο και πιο σημαντικό παράγοντα συσταδοποίησης γράφων ανάμεσα σε κόμβους με βάση το μοτίβο συνδεσιμότητας ακολουθώντας ταυτόχρονα και την κατευθυντικότητα αλλά και την πόλωση των συνδέσμων που τους διασυνδέουν.

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