Distributed Clustering of Uncertain Graphs
Creators: name: Πέσιος, Δημήτριος Ιωάννη
Publisher: name: Aristotle University of Thessaloniki
Year: 2019
Subjects: Αβέβαιοι γράφοι
Συσταδοποίηση
Αλγόριθμος pKwik
Uncertain graphs
Clustering
pKwik algorithm

description: Σε αυτήν την διπλωματική εργασία, είχαμε ως σκοπό την υλοποίηση του αλγορίθμου συσταδοποίησης pKwik με κατανεμημένο τρόπο, ο οποίος είναι ένας αλγόριθμος σχεδιασμένος για αβέβαια γραφήματα, δηλαδή γραφήματα για τα οποία υπάρχει μια πιθανότητα ύπαρξης επισυναπτόμενη με κάθε ακμή του. Σε αντίθεση με τα αιτιατά ή συμβατικά γραφήματα, τα αβέβαια γραφήματα απαιτούν ειδική αντιμετώπιση γιατί παρουσιάζουν υπολογιστικές προκλήσεις σε ακόμη και τα πιο απλά και συνηθισμένα προβλήματα της Επιστήμης Δεδομένων. Για να ξεπεραστούν αυτές οι προκλήσεις έχουν επιστρατευθεί πολλές στρατηγικές όπως εξειδικευμένοι προσεγγιστικοί αλγόριθμοι, ωστόσο, με κεντρικοποιημένο τρόπο. Η καινοτομία της διπλωματικής έγκειται στο γεγονός ότι η κατανεμημένη επεξεργασία μπορεί να διευκολύνει την δημιουργία λύσεων όταν είναι ακριβό ή αδύνατο να σχεδιαστεί μια λύση με κεντρικοποιημένο τρόπο. Για να χρησιμοποιήσουμε παράλληλη επεξεργασία, επιλέξαμε το ευρέως γνωστό Apache Spark framework και την υποβιβλιοθήκη αυτού GraphX, σε συνδυασμό με γλώσσα προγραμματισμού Scala σε έναν υπολογιστή 80 πυρήνων προορισμένο για βαρείς υπολογισμούς. Τα αποτελέσματα μας έδειξαν ότι ο αλγόριθμος pKwik κλιμακώνεται πολύ καλά όταν αυξάνει το μέγεθος του γραφήματος, ενώ παρατηρήθηκε ότι baseline αλγόριθμος Louvain δεν επηρεάζεται από την κλιμάκωση του μεγέθους του γραφήματος. Επιπλέον, όταν οι διαθέσιμοι πυρήνες του υπολογιστή αυξάνονται και οι δύο αλγόριθμοι κλιμακώνονται πολύ καλά και φαίνεται ότι ο αριθμός των 16 πυρήνων είναι αρκετός και για τους δύο διότι δεν υπάρχει σημαντική απόκλιση στον χρόνο εκτέλεσης για παραπάνω πυρήνες. Χρησιμοποιήσαμε δύο δείκτες, τον Rand index και έναν δείκτη που μοιάζει με τον Dunn Index, για να μετρήσουμε την ευρωστία των συσταδοποιήσεων που παρήγαγαν οι αλγόριθμοι, με τον πρώτο να βασίζεται σε δεδομένα βασικής αλήθειας και τον δεύτερο σε πιο διαισθητικά κριτήρια. Υπολογίσαμε ότι ο Rand Index για το πλήρες γράφημα είναι 0.6 για τον pKwik αλγόριθμο, ενώ είναι για τον baseline αλγόριθμο είναι μικρότερος και ίσος με 0.1, το οποίο σημαίνει ότι ο pKwik αλγόριθμος είναι πιο κοντά στην βασική αλήθεια. Επιπρόσθετα, ο Dunn Index είναι ακόμη μεγαλύτερος και ίσος με 0.7 για τον pKwik αλγόριθμο και 0.4 για τον baseline Louvain αλγόριθμο, το οποίο στην ουσία σημαίνει ότι οι συστάδες που δημιουργήθηκαν από τον πρώτο είναι πιο συμπαγείς και διαχωρισμένες
description: In this dissertation, we were initiated with the purpose of implementing the pKwik clustering algorithm in a distributed fashion, which is an algorithm designed for uncertain graphs, that is graphs for which there is a probability of existence incurred with every edge. Unlike deterministic or conventional graphs, uncertain ones require special treatment since they present computational challenges in even the simplest and ordinary problems of data science. To overcome those challenges many strategies are employed such as specialized approximation algorithms, however, mainly in a centralized fashion. The novelty of this dissertation lies in the fact that distributed processing can facilitate the formation of solutions when it is too costly or impossible for the solution to be designed in a centralized fashion. In order to leverage parallel processing, we use the well-known Apache Spark framework and its GraphX module on top of it, in conjunction with the Scala programming language in a 80-core mainframe machine dedicated for heavy computations. Our results demonstrated that the pKwik algorithm scales very well when the size of input graph increases, while it was observed that the baseline Louvain algorithm is irrespective of the graph size scaling. Furthermore, when the available execution cores in the mainframe machine increase both algorithms scale well and it seems that the number of 16 cores is adequate for both since there is no substantial variation in the execution time. We used two indexes, the Rand index and a Dunn-like index, to measure the robustness of the clustering algorithms produced, the first one based on ground-truth data and the second one on more intuitive criteria. We calculated that the Rand Index for the full-fledged graph is 0.6 for the pKwik algorithm while is even smaller and equal with 0.1 for the baseline Louvain algorithm, which means that the specialized pKwik algorithm is more close to the ground-truth. Additionally, the Dunn-like Index is even higher and equal with 0.7 for the pKwik algorithm and 0.4 for the baseline Louvain algorithm which essentially means that the clusters created are more compact and well-separated