Storage, processing and analysis of large evolving graphs

Abstract

In recent years, increasing amounts of graph structured data are being made available from a variety of sources, such as social, citation, computer and hyperlink networks. Their continuous evolution is becoming a subject that attracts considerable attention, and finds a wide spectrum of applications ranging from social network marketing to virus propagation and digital forensics. Although the analysis of the graph evolution is important of our understanding of the network, the main focus of research has been on efficiently storing and retrieving the graph snapshots. Furthermore, processing graph data through a variety of graph queries including reachability, distance and pattern-based ones, is limited to static graphs, leaving query processing on evolving graphs unexplored. This dissertation focus on managing and querying the full history of a graph as it evolves. We introduce a compact representation of an evolving graph, where each graph element i.e., node or edge is annotated with the set of time intervals that refer to the existence of each element through the graph evolution. We then include studies of different ways of extracting information from the evolving graph by posing different queries on a sequence of graph snapshots. We call such queries historical queries. In particular, we first introduce historical graph traversal queries that consider paths that exist in a sufficient number of graph snapshots. We exploit variants of two types of historical traversal queries, reachability and shortest paths. Historical reachability queries ask whether two nodes are connected in some time instance, in all time instances, or in a sufficient number of time instances whereas historical shortest path queries ask for the shortest path between two nodes posing requirements on the lifespan of such paths. We provide efficient algorithms for supporting historical graph traversal queries. We propose effective implementations of our algorithms based on time index structures for in-memory and graph database systems, and provide an extensive experimental evaluation of various aspects of our approach. We also formalize a new problem that of finding the top-k most durable matches of an input graph pattern query, that is the matches that exist for the longest period of time. Locating durable matches in the evolution of large graphs is important for our understanding of the network, and it may be crucial for many applications. Applying previous approaches to pattern matching problem at each snapshot and aggregating the results for large networks and long sequences is computationally expensive, since all matches have to be generated at each snapshot, including those appearing only once. Thus, we propose a new efficient and effective approach that uses appropriate time indexes to prune the search space and strategies to estimate the duration of the seeking matches in large evolving graphs. Furthermore, we systematically study density in evolving graphs, and provide definitions for density over multiple graph snapshots, that capture different semantics of connectedness over time. We study the complexity of the different variants of the problem and we propose a generic algorithmic framework for solving our problems, that works in linear time. Our experimental evaluation shows both the efficiency of our algorithms and the usefulness of the problems.Finally, we introduce three approaches of modeling evolving graphs in native graph databases, as well as, algorithms for processing historical queries that use these approaches.

Τα τελευταία χρόνια, αυξανόμενες ποσότητες δεδομένων που αναπαριστώνται από γραφήματα διατίθενται από διάφορες πηγές, όπως τα δίκτυα κοινωνικής δικτύωσης, τα δίκτυα παραπομπής, τα δίκτυα ηλεκτρονικών υπολογιστών και τα δίκτυα υπερσύνδεσης. Η συνεχής εξέλιξη τους γίνεται ένα θέμα που προσελκύει ιδιαίτερη προσοχή και βρίσκει ένα ευρύ φάσμα εφαρμογών που κυμαίνονται από το μάρκετινγκ στα κοινωνικά δίκτυα έως τη διάδοση των ιών και την ψηφιακή εγκληματολογία. Αν και η ανάλυση της εξέλιξης των γραφημάτων είναι σημαντική για να κατανοήσουμε το δίκτυο, ο κύριος στόχος της έρευνας τα τελευταία χρόνια ήταν η αποτελεσματική αποθήκευση και ανάκτηση των στιγμιότυπων της εξέλιξης του γραφήματος. Επιπλέον, η επεξεργασία δεδομένων γραφημάτων μέσω μιας ποικιλίας ερωτήσεων σε γραφήματα (graph queries), όπως της προσπελασιμότητας, της εύρεσης απόστασης και μοτίβων, περιορίζεται στα στατικά γραφήματα, αφήνοντας ανεξερεύνητη την επεξεργασία ερωτήσεων στα εξελισσόμενα γραφήματα. Παρόλο που υπάρχει μεγάλο ενδιαφέρον για την επεξεργασία στατικών γραφημάτων μέσω μιας ποικιλίας ερωτήσεων σε γραφήματα (graph queries), όπως της προσπελασιμότητας, της εύρεσης απόστασης και μοτίβων, η αναζήτηση στο ιστορικό ενός εξελισσόμενου γραφήματος είναι πολύ λιγότερο μελετημένη. Στόχος αυτής της διατριβής είναι η διαχείριση και διερεύνηση της ιστορίας ενός γραφήματος καθώς εξελίσσεται. Παρουσιάζουμε μια συμπαγή αναπαράσταση ενός εξελισσόμενου γραφήματος, όπου κάθε στοιχείο του π.χ. κόμβος ή ακμή, σημειώνεται με το σύνολο χρονικών διαστημάτων που δηλώνουν την ύπαρξη κάθε στοιχείου κατά την διάρκεια της εξέλιξης του γραφήματος. Στη συνέχεια παρουσιάζουμε μελέτες διαφορετικών τρόπων εξαγωγής πληροφοριών από το εξελισσόμενο γράφημα θέτοντας διαφορετικά ερωτήματα σε μια ακολουθία στιγμιότυπων γραφημάτων. Αναφερόμαστε σε τέτοιου είδους ερωτήματα ως ιστορικά ερωτήματα (historical queries). Συγκεκριμένα, παρουσιάζουμε πρώτα ιστορικά ερωτήματα διάσχισης ενός γραφήματος που λαμβάνουν υπόψη τις διαδρομές που υπήρχαν σε επαρκή αριθμό στιγμιότυπων του γραφήματος. Χρησιμοποιούμε παραλλαγές δύο τύπων ιστορικών ερωτήσεων διάσχισης, της προσβασιμότητας και της εύρεσης συντομότερων διαδρομών. Τα ερωτήματα ιστορικής προσβασιμότητας ρωτούν αν δύο κόμβοι συνδέονται είτε σε κάποια χρονική στιγμή, είτε σε όλες τις χρονικές στιγμές ή σε επαρκή αριθμό χρονικών στιγμών, ενώ τα ιστορικά ερωτήματα εύρεσης συντομότερων διαδρομών ζητούν τη συντομότερη διαδρομή μεταξύ δύο κόμβων θέτοντας περιορισμούς ως προς τη διάρκεια ζωής αυτών των διαδρομών. Παρέχουμε αποτελεσματικούς αλγόριθμους για την υποστήριξη ιστορικών ερωτημάτων διάσχισης σε γραφήματα. Προτείνουμε αποτελεσματικές υλοποιήσεις των αλγορίθμων μας που κάνουν χρήση χρονικών ευρετηρίων σε συστήματα που βρίσκονται εξολοκλήρου στη μνήμη και σε συστήματα βάσεων γραφημάτων. Στη συνέχεια, παρουσιάζουμε μια εκτενή πειραματική αξιολόγηση διαφόρων πτυχών της προσέγγισής μας. Ορίζουμε επίσης το νέο πρόβλημα της εύρεσης των k πιο ανθεκτικών ισομορφικών γραφημάτων ενός μοτίβου εισόδου, δηλαδή την εύρεση των γραφημάτων που είναι ισομορφικά με το μοτίβο εισόδου και υπάρχουν για το μεγαλύτερο χρονικό διάστημα. Η εύρεση τέτοιων γραφημάτων είναι σημαντική για την κατανόηση του δικτύου και μπορεί να είναι κρίσιμη για πολλές εφαρμογές. Εφαρμόζοντας τις προηγούμενες προσεγγίσεις στο πρόβλημα εύρεσης ισομορφικών γραφημάτων ενός μοτίβου εισόδου σε κάθε στιγμιότυπο και τη συγκέντρωση των αποτελεσμάτων, είναι υπολογιστικά ακριβό για μεγάλα δίκτυα. Αυτό συμβαίνει γιατί όλα τα ισομορφικά γραφήματα του μοτίβου εισόδου πρέπει να βρεθούν σε κάθε στιγμιότυπο, συμπεριλαμβανομένων εκείνων που εμφανίζονται μόνο μία φορά. Για τον λόγο αυτό, προτείνουμε μια νέα αποδοτική και αποτελεσματική προσέγγιση που χρησιμοποιεί κατάλληλα χρονικά ευρετήρια για να μειώνει τον χώρο αναζήτησης όπως και στρατηγικές αναζήτησης για να υπολογίζει τη διάρκεια ζωής των γραφημάτων που αναζητούμε. Επιπλέον, μελετάμε το πρόβλημα της εύρεσης του συνόλου των κόμβων που είναι πιο πυκνά συνδεδεμένοι σε όλα τα στιγμιότυπα του εξελισσόμενου γραφήματος. Παρέχουμε ορισμούς για την πυκνότητα σε πολλαπλά στιγμιότυπα γραφημάτων, που καταγράφουν διαφορετικές σημασιολογίες της συνδεσιμότητας των κόμβων κατά την πάροδο του χρόνου, και μελετάμε τις αντίστοιχες παραλλαγές του προβλήματος. Μελετάμε την πολυπλοκότητα των διαφορετικών παραλλαγών του προβλήματος και προτείνουμε ένα γενικό αλγοριθμικό πλαίσιο για την επίλυση των προβλημάτων μας, που λειτουργεί σε γραμμικό χρόνο. Η πειραματική μας αξιολόγηση δείχνει τόσο την αποτελεσματικότητα των αλγορίθμων όσο και τη χρησιμότητα των προβλημάτων. Τέλος, παρουσιάζουμε τρεις προσεγγίσεις για τη μοντελοποίηση των εξελισσόμενων γραφημάτων σε βάσεις γραφημάτων, καθώς και τους αλγορίθμους για την επεξεργασία ιστορικών ερωτημάτων που χρησιμοποιούν αυτές τις προσεγγίσεις.