Revealing evolutionary patterns in dynamic graphs: exploration and visualization techniques

Abstract

Graphs are a fundamental data structure used to model a wide range of complex systems, such as social networks, biological processes, and transportation systems. These graphs are often dynamic, evolving over time with changes in both their structure and attributes. This introduces significant challenges in the analysis of temporal graphs, which require specialized methods to capture evolving patterns and identify key events. Understanding how systems change over time, and extracting meaningful insights from these changes, is crucial for many real-world applications. This thesis addresses these challenges by developing new techniques for the exploration and visualization of temporal graphs. We introduce the GraphTempo framework, which combines attribute-based and time-based aggregation techniques to enable efficient exploration and analysis of temporal graphs. The framework incorporates novel event detection algorithms that identify key structural and attribute-based changes, such as stability, growth, and shrinkage events, capturing variations in the graph’s structure and attributes. A core aspect of this research is the development of an interactive visualization system that enables users to navigate the temporal evolution of graphs. By combining graph overview, aggregation, and exploration with intuitive visualizations, our approach uncovers trends and highlights important transitions over time. These techniques are evaluated on real-world datasets, including social and collaboration networks, demonstrating their efficiency and effectiveness in revealing insights into dynamic systems. The contributions of this thesis provide novel algorithms and a comprehensive framework for analyzing the evolution of temporal graphs, along with an intuitive visualization system. These techniques offer valuable tools for understanding dynamic systems across various domains, such as social network analysis, epidemiology, and transportation systems, where tracking the evolution of interactions and relationships is crucial. Overall, this research advances the field of temporal graph analysis by offering efficient methods for detecting significant events and visualizing the dynamic behavior of complex systems over time.

Οι γράφοι αποτελούν μια θεμελιώδη δομή δεδομένων που χρησιμοποιείται για τη μοντελοποίηση ενός ευρέος φάσματος πολύπλοκων συστημάτων, όπως τα κοινωνικά δίκτυα, οι βιολογικές διεργασίες και τα συστήματα μεταφορών. Οι γράφοι αυτοί είναι συχνά δυναμικοί, εξελίσσονται με την πάροδο του χρόνου παρουσιάζοντας αλλαγές τόσο στη δομή όσο και στα χαρακτηριστικά τους. Αυτό εισάγει σημαντικές προκλήσεις στην ανάλυση χρονικών γράφων, οι οποίες απαιτούν εξειδικευμένες μεθόδους για την αποτύπωση εξελισσόμενων προτύπων και την αναγνώριση βασικών γεγονότων. Η κατανόηση του τρόπου με τον οποίο τα συστήματα αλλάζουν με την πάροδο του χρόνου και η εξαγωγή ουσιαστικών συμπερασμάτων από αυτές τις αλλαγές είναι κρίσιμη για πολλές εφαρμογές του πραγματικού κόσμου. Η παρούσα διατριβή αντιμετωπίζει αυτές τις προκλήσεις με την ανάπτυξη νέων τεχνικών για την εξερεύνηση και την οπτικοποίηση χρονικά μεταβαλλόμενων γράφων. Παρουσιάζουμε το πλαίσιο GraphTempo, το οποίο συνδυάζει τεχνικές συσσωμάτωσης βασισμένες στα χαρακτηριστικά και στο χρόνο για την αποδοτική εξερεύνηση και ανάλυση των δυναμικών γράφων. Το πλαίσιο περιλαμβάνει καινοτόμους αλγόριθμους ανίχνευσης γεγονότων που εντοπίζουν βασικές αλλαγές στη δομή και τα χαρακτηριστικά, όπως γεγονότα σταθερότητας, ανάπτυξης και συρρίκνωσης, καταγράφοντας τις διακυμάνσεις στη δομή και τα χαρακτηριστικά του γράφου. Βασικό στοιχείο της έρευνας αποτελεί η ανάπτυξη ενός διαδραστικού συστήματος οπτικοποίησης που επιτρέπει στους χρήστες να αναλύουν τη χρονική εξέλιξη των γράφων. Συνδυάζοντας την επισκόπηση γράφου, τη συσσωμάτωση και την εξερεύνηση με διαισθητικές οπτικοποιήσεις, η προσέγγισή μας αποκαλύπτει τάσεις και αναδεικνύει σημαντικές μεταβολές με την πάροδο του χρόνου. Οι τεχνικές αυτές αξιολογούνται σε πραγματικά σύνολα δεδομένων, συμπεριλαμβανομένων κοινωνικών και συνεργατικών δικτύων, αποδεικνύοντας την αποδοτικότητα και την αποτελεσματικότητά τους στην αποκάλυψη της γνώσης σε σχέση με τα δυναμικά συστήματα. Οι συνεισφορές αυτής της διπλωματικής εργασίας περιλαμβάνουν νέους αλγορίθμους και ένα ολοκληρωμένο πλαίσιο για την ανάλυση της εξέλιξης χρονικά μεταβαλλόμενων γράφων, καθώς και ένα διαισθητικό σύστημα οπτικοποίησης. Οι τεχνικές αυτές παρέχουν χρήσιμα εργαλεία για την κατανόηση δυναμικών συστημάτων σε διάφορους τομείς, όπως η ανάλυση κοινωνικών δικτύων, η επιδημιολογία και τα συστήματα μεταφορών, όπου η παρακολούθηση της εξέλιξης των αλληλεπιδράσεων και των σχέσεων είναι κρίσιμη. Συνολικά, η έρευνα αυτή προωθεί το πεδίο της ανάλυσης χρονικών γράφων, προσφέροντας αποδοτικές μεθόδους για την ανίχνευση σημαντικών γεγονότων και την οπτικοποίηση της δυναμικής συμπεριφοράς πολύπλοκων συστημάτων με την πάροδο του χρόνου.