Flow analytics in large graphs

Abstract

Numerous real-world applications can be represented as networks of dynamic structure, since the vertices correspond to entities that exchange data over time. Ex- amples include transportation networks, financial networks, social networks, traffic networks etc. We call these Temporal Interaction Networks (TINs). The importance of studying and analyzing TINs is high as we can use them to solve problems related to transportation and financial transactions. Moreover, analyzing TINs can extract interesting insights or reveal important information (e.g., cyclic transactions, message interception).TINs capture the data transfers between entities along a timeline. Specifically, at each interaction, a quantity (money, message, traffic) moves from one network vertex (entity) to another. We call this quantity flow. The main objective of this thesis is to introduce and analyze the flow concept in a variety of problems (flow computation, tracking the provenance of a quantity, extracting patterns etc.). Flow analysis in TINs can be used for congestion detection and explanation in traffic networks, identification of suspicious transactions in financial networks, to name a few applications. It also comes with a number of challenges and difficulties, most notably the potentially large graph size and huge number of interactions between the vertices of the TIN. Another issue is that solutions to well-studied problems in graphs, such as max-flow computation in static networks, cannot directly be applied to solve flow computation problems in TINs. Hence, it is necessary to design novel, scaleable, and memory- efficient solutions for this problem. In this thesis, we introduce and study a number of flow computation problems in TINs. In the first part of the thesis, we study the problem of computing in a sub- graph (DAG) of the TIN the total flow from a designated source node to a designated sink node. Specifically, for this problem we propose and study two models of flow computation. The first model is a greedy flow transfer approach where each inter- action transfers the maximum possible quantity. The second model is an approach inspired from the maximum flow computation problem. In this case, the interactions may not transfer the maximum possible quantity, but the one which results in the maximum flow transfer from the source to the sink along the timeline. This problem can be formulated and solved as a linear programming (LP) problem. We propose a number of preprocessing and graph simplification techniques that greatly reduce the complexity of the problem in practice. Lastly, we propose algorithms that enumerate DAG pattern instances and their flow in large graphs.The second problem we study is flow provenance tracking in TINs. Specifically, given a node in the graph, we study provenance of the total quantity that has been accumulated at the node by a time instant. We study provenance under a number of different models for the propagation of quantities; for each such model we define an- notation generation and propagation algorithm that can be used to track provenance. We also propose scaleable techniques for the most expensive model (propagation se- lection) in large graphs and analyze the space and time complexity of the provenance mechanisms that we propose.In the last part of this thesis, we introduce spatio-temporal flow patterns of pas- sengers in transportation networks. We study the problem of identifying interesting origin-destination-time (ODT patterns) at varying granularity. We propose algorithms for extracting such patterns efficiently. We also propose a number of optimizations to our baseline algorithm, which significantly reduce the time spent for generating candidate patterns and counting their support. Since the pattern enumeration can still be expensive, we propose practical variants of pattern search.For our evaluation, we use a number of real datasets from different application domain (e.g., bitcoin exchange network, passenger transportation network, loan exchange network) of varying scales and densities. Our results show that our proposed algorithms are scaleable and that their output can be useful in many applications of flow analysis in temporal networks.

Πολλές εφαρμογές που βασίζονται σε προβλήματα του πραγματικού κόσμου μπορούν να αναπαρασταθούν ως δίκτυα με δυναμική δομή όπου οι κόμβοι αντι- στοιχούν σε οντότητες που έχουν την δυνατότητα να ανταλλάζουν δεδομένα μεταξύ τους μέσα στον χρόνο. Μερικά παραδείγματα εφαρμογών αποτελούν τα δίκτυα με- τακίνησης, τα οικονομικά δίκτυα, τα κοινωνικά δίκτυα, δίκτυα κίνησης κτλ. Καλούμε αυτά τα δίκτυα χρονικά δίκτυα αλληλεπίδρασης. Η σημαντικότητα της μελέτης και της ανάλυσης των χρονικών δικτύων αλληλεπίδρασης είναι πολύ υψηλή εξαιτίας του ότι μπορούμε να τα χρησιμοποιήσουμε για την επίλυση προβλημάτων που σχετί- ζονται με χρηματικές συναλλαγές ή ταξίδια που πραγματοποιούνται. Επιπλέον, η ανάλυση των χρονικών δικτύων αλληλεπίδρασης μπορούν να βοηθήσουν στην εξα- γωγή χρήσιμων συμπερασμάτων ή την αποκάλυψη σημαντικών πληροφοριών (π.χ., κυκλικές συναλλαγές, υποκλοπή μηνυμάτων).Τα χρονικά δίκτυα αλληλεπίδρασης μοντελοποιούν την μεταφορά μιας ποσότη- τας μεταξύ οντοτήτων κατά την διάρκεια μιας χρονικής στιγμής. Πιο συγκεκριμένα, σε κάθε αλληλεπίδραση, μια ποσότητα (χρήματα, μηνύματα, κίνηση) μετακινείται από τον έναν κόμβο (οντότητα) του δικτύου στον άλλον. Καλούμε αυτή την ποσό- τητα ροή. Αντικείμενο της διδακτορικής διατριβής είναι η εισαγωγή και η ανάλυση της ροής σε ένα σύνολο διάφορων προβλημάτων (υπολογισμός ροής, ανίχνευση προ- έλευσης της ροής, εξαγωγή μοτίβων κτλ.). Η ανάλυση της ροής στα χρονικά δίκτυα αλληλεπίδρασης μπορεί να χρησιμοποιηθεί για την αποσυμφόρηση και τους λόγους που οδήγησαν στην κίνηση στους δρόμους, ο εντοπισμός παράνομων συναλλαγών σε οικονομικά δίκτυα και άλλα πολλά παραδείγματα. Επιπροσθέτως, το πρόβλημα ανάλυσης της ροής συνοδεύεται με μια σειρά από προκλήσεις και δυσκολίες που εντοπίζονται κυρίως σε σημεία που αφορούν το μεγαλό μέγεθος των γράφων και τον τεράστιο αριθμό αλληλεπιδράσεων μεταξύ των κόμβων σε ένα χρονικό δίκτυο αλ- ληλεπίδρασης. Ένα ακόμη πρόβλημα που υπάρχει έγκειται στο ότι οι προτεινόμενες λύσεις που υπάρχουν για γνωστά προβλήματα σε γράφους όπως π.χ., το πρόβλημα υπολογισμού της μέγιστης ροής σε στατικά δίκτυα, δεν μπορούν να εφαρμοστούν και να λύσουν προβλήματα υπολογισμού ροής σε χρονικά δίκτυα αλληλεπίδρασης. Λαμβάνοντας υπόψιν τα παραπάνω, είναι απαραίτητος ο σχεδιασμός πρωτοπόρων, κλιμακώσιμων καθώς και αποδοτικών λύσεων που σχετίζονται με την μνήμη προ- κειμένου να λύσουμε το προηγούμενο πρόβλημα.Στα πλαίσια της παρούσας διδακτορικής διατριβής, εισάγουμε και μελετάμε διάφορα προβλήματα που σχετίζονται με τον υπολογισμό της ροής σε χρονικά δί- κτυα αλληλεπίδρασης. Στο πρώτο μέρος της διδακτορικής διατριβής, μελετάμε το πρόβλημα υπολογισμού της ροής σε έναν υπογράφο από έναν αρχικό κόμβο σε έναν τελικό κόμβο. Πιο συγκεκριμένα, για το εν λόγω πρόβλημα προτείνουμε και μελετάμε δυο μοντέλα υπολογισμού της ροής. Το πρώτο μοντέλο είναι μια άπληστη προσέγγιση για την μεταφορά της ροής όπου σε κάθε αλληλεπίδραση μεταφέρεται η μέγιστη πιθανή ποσότητα. Το δεύτερο μοντέλο αποτελεί μια προσέγγιση εμπευν- σμένη από το γνωστό πρόβλημα του υπολογισμού της μέγιστης ροής. Σε αυτή την περίπτωση, οι αλληλεπιδράσεις ενδέχεται να μην μεταφέρουν την μέγιστη δυνατή ποσότητα αλλά εκείνη την ποσότητα όπου καταλήγει από έναν αρχικό κόμβο σε έναν τελικό κόμβο. Το πρόβλημα αυτό μπορεί να οριστεί και να επιλυθεί σαν ένα πρόβλημα γραμμικού προγραμματισμού. Λαμβάνοντας υπόψιν όλα τα παραπάνω, προτείνουμε μια σειρά λύσεων για την προεπεξεργασία του γράφου καθώς και τεχνικές απλοποίησης όπου μειώνουν σε μεγάλο βαθμό την πολυπλοκότητα του προβλήματος. Τέλος, προτείνουμε αλγορίθμους για την αρίθμηση στιγμιοτύπων των μοτίβο και της ροής τους σε μεγάλους γράφους.Το δεύτερο πρόβλημα που μελετάμε είναι η ανίχνευση της ροής σε χρονικά δίκτυα αλληλεπίδρασης. Πιο συγκεκριμένα, δοθέντος ενός κόμβου σε έναν γράφο, μελετάμε την προέλευση της συνολικής ποσότητας που έχει συγκεντρωθεί σε ένα κόμβο για μια χρονική στιγμή. Για την μελέτη του προβλήματος της ανίχνευσης, προτείνουμε διαφορετικά μοντέλα για την διάδοση των ποσοτήτων; για κάθε τέτοιο μοντέλο ορίσμους αλγορίθμους που σχετίζονται με την δημιουργία επισημάνσεων και διάδοσης που μπορούν να χρησιμοποιηθούν για την ανίχνευση της ροής της ποσότητας. Προτείνουμε κλιμακώσιμες τεχνικές για το ακριβό μοντέλο της αναλογικής επιλόγης της μεταφοράς της ποσότητας σε μεγάλους γράφους και την ανάλυση της πολυπλοκότητας του χώρου και του χρόνου των μηχανισμών της ανίχνευσης της ποσότητας που προτείνουμε.Στο τελευταίο κομμάτι της διδακτορικής διατριβής, εισάγουμε τα χωροχρονικά μοτίβα ροής σε δίκτυα μεταφοράς. Μελετάμε το πρόβλημα εντοπισμού ενδιαφε- ρόντων μοτίβων που χαρακτηρίζονται από τρεις διαστάσεις (αρχικό σημείο, τελικό σημείο, χρόνος) σε μεταβαλλόμενη λεπτομέρεια. Προτείνουμε αλγορίθμους για την εξαγωγή μοτίβων αποτελεσματικά. Επιπροσθετώς, προτείνουμε μια σειρά οπτικοποιήσεων βασιζόμενοι στον βασικό μας αλγόριθμο, όπου μειώνουν σημαντικά τον χρόνο που απαιτείται για την παραγωγή υποψήφιων μοτίβων. Ωστόσο, το πρόβλημα της αρίθμησης των μοτίβων παραμένει ακριβό. Για τον λόγο αυτό, προτείνουμε μια σειρά διάφορων παραλλαγών για την εύρεση των μοτίβων.Στα πλαίσια της αξιολόγησης, χρησιμοποιούμε πραγματικά σύνολα δεδομένων από διάφορες εφαρμογές (το δίκτυο Bitcoin, δίκτυα μετακίνησης, δίκτυο που σχετίζεται με δάνεια κτλ). Τα αποτελέσματα των πειραμάτων αποδεικνύουν ότι οι αλγόριθμοι που προτείνουμε είναι κλιμακώσιμοι και το αποτέλεσμα τους μπορεί να χρησιμοποιηθεί σε πολλές εφαρμογές για την ανάλυση της ροής σε χρονικά δίκτυα.