Flow analytics in large graphs
Authors: Κοσυφάκη Χρυσάνθη 
Published: June 2023

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