Εύρεση Ανώμαλων Μοτίβων σε Δυναμικά Γραφήματα
Creators: name: Σουλεϊμάνης, Εμμανουήλ Χρήστου
Publisher: name: Aristotle University of Thessaloniki
Year: 2022
Subjects: Δυναμικά Γραφήματα
Μεθοδολογίες εντοπισμού Ανωμαλιών
Διεργασία Ανακάλυψης Γνώσης
Dynamic Graphs
Anomaly Detection
KDD – Knowledge Discovery in Database

description: Η ανίχνευση ακραίων τιμών στα δεδομένα γραφημάτων ήταν ένα σημαντικό ερευνητικό πεδίο για μεγάλο χρονικό διάστημα.. Σε αυτήν την εργασία παρουσιάζεται μια μεθοδολογία ανάλυσης δεδομένων που αναπαρίστανται σε δυναμικό γράφημα για την ανακάλυψή τιμών που αποκλίνουν σε μοτίβα του γραφήματος. Η μεθοδολογία περιλαμβάνει την δημιουργία και σύγκριση των προφίλ των κόμβων από τα χαρακτηριστικά τους και αποφασίζει για την ομαλότητα κόμβους ακμές και κοινότητες αφού οι τελευταίες εξαχθούν κατά την εξέλιξη του γραφήματος στον χρόνο. Ενώ τα πιο γνωστά έργα προσεγγίζουν το πρόβλημα ανίχνευσης ανωμαλιών μέσω δομικής ανάλυσης του γραφήματος και στατιστικών μεθόδων ή μεθόδων μηχανικής μάθησης, προσπαθούμε να προσθέσουμε περισσότερη αξία από τα χαρακτηριστικά του κάθε κόμβου που συμμετέχει στο γράφημα. Το γράφημα δημιουργήθηκε σύμφωνα με τα δεδομένα που παρέχονται ελεύθερα και τεχνικές NLP έχουν χρησιμοποιηθεί στην επεξεργασία κειμένου των αρχικών δεδομένων ώστε να σχηματιστεί ένα γράφημα με κόμβους, χαρακτηριστικά των κόμβων, ακμές και βάρος στις ακμές. Η ανάλυση εκτελείται σε τρία διαφορετικά επίπεδα, κόμβους, ακμές, κοινότητες. Επίσης δίνεται και η δυνατότητα ερωτήματος για συγκεκριμένους κόμβους, οι οποίοι αποτελούν κοινότητα είτε αυτούσια είτε είναι μέρος μιας μεγαλύτερης κοινότητας στο γράφημα, ως προς το αν παρουσιάζουν απόκλιση από την αναμενόμενη συμπεριφορά. Ως αρχικό γράφημα επιλέχθηκε το γράφημα με τα δεδομένα μιας χρονιάς και κάθε επόμενη προστέθηκε αυξάνοντας το γράφημα διατηρώντας τους προ υπάρχοντες κόμβους όπως και τις συνδέσεις τους. Τα αποτελέσματα υποδεικνύουν μια ενδιαφέρουσα συμπεριφορά σε σύγκριση με τα προφίλ των συγγραφέων που σύμφωνα με τη λειτουργία της απόφασής μας θεωρούνται ότι δεν ακολουθούν την ομαλή εικόνα που αναμέναμε τόσο σε επίπεδο οντότητας όσο και της εξέλιξης της στο χρόνο. Συγκεκριμένα παρατηρήθηκαν μεταβολές στο αποτέλεσμα της απόφασης, είτε σε επίπεδο κόμβου είτε σύνδεσης είτε κοινότητας, πού σε αντίστοιχη ανάλυση του γραφήματος ως στατικού δεν θα γινόταν αντιληπτές. Δεν υπάρχει προ υπάρχουσα γνωστή σύγκριση, είτε σχετικά με την ακρίβεια είτε τον χρόνο υπολογισμού των αλγορίθμων που χρησιμοποιούνται, καθώς δεν βρέθηκε παρόμοια έρευνα για το συγκεκριμένο σύνολο δεδομένων.
description: Outlier detection in graph data has been an important area of research for a long time. This thesis presents a data analysis methodology applied in a dynamic network to discover values on graph patterns that deviate from the expected behavior. The methodology involves the creation and comparison of node profiles by their characteristics and decides on the anomaly status of nodes edges and communities after the latter are extracted as the graph evolves over time. While the best-known projects approach the problem of anomaly detection through structural analysis of the graph and statistical methods or machine learning methods, we try to add more value from the characteristics of each node participating in the graph. The graph was created according to the open-source dataset provided by Kaggle and various NLP techniques were applied in pre- processing the text of the original data to create a weighted, undirected attributed graph. The analysis is performed at three different levels, edges, nodes, and communities. It is also provided a functionality to query for specific nodes, which are either a community as it is or are part of a larger community in the graph, and still connected between them, as to whether they deviate as community from the expected behavior. The dynamic graph was handled in a temporal manner, the data of one year were chosen as the initial graph and each subsequent snapshot was added by increasing the graph keeping the pre-existing nodes as well as their connections. The results indicate an interesting behavior compared to the profiles of the authors who according to the function of our decision are considered that they do not follow the expected behavior both at the level as entity and its evolution over time. Specifically, there were changes in the result of the decision, either at the level of node, edge or community, which in a corresponding analysis of the graph as static would not be perceived. There is no pre-existing comparison, either regarding the accuracy or the execution time of the algorithms used, as no similar research was found for this data set.