Unit:
Department of Informatics and TelecommunicationsΠληροφορική
Author:
Liakos Panagiotis
Dissertation committee:
Αλέξιος Δελής, Καθηγητής, Τμήμα Πληροφορικής και Τηλεπικοινωνιών, Εθνικό και Καποδιστριακό Πανεπιστήμιο Αθηνών
Μέμα Ρουσσοπούλου, Αναπληρώτρια Καθηγήτρια, Τμήμα Πληροφορικής και Τηλεπικοινωνιών, Εθνικό και Καποδιστριακό Πανεπιστήμιο Αθηνών
Αλέξανδρος Ντούλας, Επίκουρος Καθηγητής, Τμήμα Πληροφορικής και Τηλεπικοινωνιών, Εθνικό και Καποδιστριακό Πανεπιστήμιο Αθηνών
Δημήτρης Γουνόπουλος, Καθηγητής, Τμήμα Πληροφορικής και Τηλεπικοινωνιών, Εθνικό και Καποδιστριακό Πανεπιστήμιο Αθηνών
Γιάννης Ιωαννίδης, Καθηγητής, Τμήμα Πληροφορικής και Τηλεπικοινωνιών, Εθνικό και Καποδιστριακό Πανεπιστήμιο Αθηνών
Αντώνιος Δεληγιαννάκης, Αναπληρωτής Καθηγητής, Σχολή Ηλεκτρολόγων Μηχανικών & Μηχανικών Υπολογιστών, Πολυτεχνείο Κρήτης
Γιάννης Κοτίδης, Αναπληρωτής Καθηγητής, Τμήμα Πληροφορικής, Οικονομικό Πανεπιστήμιο Αθηνών
Original Title:
Distributed and Streaming Graph Processing Techniques
Translated title:
Distributed and Streaming Graph Processing Techniques
Summary:
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.
Main subject category:
Technology - Computer science
Keywords:
Distributed graph processing, streaming graphs, graph compression, com- munity detection, opinion formation
Number of references:
136
