Τεχνικές επεξεργασίας κατανεμημένων γράφων και ρευμάτων γράφων

Abstract

Beneath most complex systems playing a vital role in our daily lives lie intricate networks. Such real-world networks are routinely represented using graphs. The volume of graph data produced in today’s interlinked world allows for realizing numerous fascinating applications but also posses important challenges. Consider for example the friendship graph of a social networking site and the findings we can come up with when executing network algorithms, such as community detection, on this graph. However, the volume that real-world networks reach oftentimes makes even the execution of fundamental graph algorithms infeasible when following traditional techniques.In this thesis we focus on two directions that allow for handling large scale networks, namely distributed graph processing, and streaming graph algorithms. In this context, we first provide contributions with regard to memory usage of distributed graph processing systems by extending the available structures of a contemporary such system with memory-optimized representations. Then, we focus on the task of community detection and propose i) a local algorithm that reveals the community structure of a vertex and easily facilitates distributed execution and ii) a streaming algorithm that greatly outperforms non-streaming state-of-the-art approaches with respect to both execution time and memory usage. In addition, we propose a streaming sampling technique that allows for capturing the interesting part of an unmanageable volume of data produced by social activity. Finally, we exploit the available data of a popular social networking site to empirically investigate a well-studied opinion formation model, using a distributed algorithm.

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