Community detection in signed, directected graphs

Abstract

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

Στη παρούσα διπλωματική επικεντρωνόμαστε σε κατευθυνόμενους γράφους και εξετάζουμε ένα αλγόριθμο ανίχνευσης κοινοτήτων, ο οποίος ομαδοποιεί κόμβους με παρεμφερή χαρακτηριστικά. Ο πιο σημαντικός παράγοντας για αποδοτική συσταδοποίηση είναι ο υπολογισμός του μέτρου ομοιότητας μεταξύ κόμβων. Η πιο σημαντική πρόκληση είναι ο καθορισμός της σχέσης ομοιότητας μεταξύ κόμβων, με βάση τα μοτίβα συνδεσιμότητας που ακολουθούν οι κόμβοι, δηλαδή ο συνδυασμός των εννοιών co-reference και co-citation.

Αρχικά, χωρίζουμε τον γράφο στο θετικό και αρνητικό υπο-γράφο του και δουλεύουμε παράλληλα και στους δύο υπο-γράφους. Για κάθε υπο-γράφο αναλύουμε τις αναφορές και τις συνδέσεις μεταξύ των κόμβων προκειμένου να υπολογίσουμε τους πίνακες co-citation και co-reference, αντίστοιχα. Ο πρώτος περιέχει τον αριθμό κόμβων στους οποίους αναφέρονται δύο κόμβοι, και ο δεύτερος δίνει τον αριθμό κόμβων που δείχνουν δύο κόμβοι. Χρησιμοποιούμε κανονικοποιημένα μαθηματικά μοντέλα για να εξομαλύνουμε τα δεδομένα, συν-υπολογίζοντας τον βαθμό κάθε κόμβου. Προκειμένου να απομακρυνθούν τα ακραία στοιχεία, επιχειρήσαμε να λάβουμε υπόψη την ισορροπία θετικών και αρνητικών εισερχόμενων και εξερχόμενων ακμών μεταξύ των κόμβων, ούτως ώστε ο αριθμός κοινών ακμών μεταξύ δύο κόμβων να μετράει λιγότερο όταν αυτοί οι κόμβοι μοιράζονται σημαντικά λιγότερες θετικές από αρνητικές ακμές και αντίστροφα.

Συνεχίζοντας, κάνουμε μια πλήρη υλοποίηση του αλγορίθμου σε python προκειμένου να ελέγξουμε πειραματικά την ορθότητα και την ακρίβεια του αλγορίθμου. Τέλος, παρουσιάζουμε τα πειραματικά αποτελέσματα του αλγορίθμου ο οποίος υλοποιείται σε signed, directed γράφους χιλιάδων κόμβων, ανάλογα με την πυκνότητα του γράφου.