Παράλληλοι Αλγόριθμοι για την Ανεύρεση των top-k Μοτίβων σε Γραφήματα
Creators: name: Κουτουνίδης Νικόλαος Χρήστου
Publisher: name: Aristotle University of Thessaloniki
Year: 2022
Subjects: Γράφοι
Παραλληλισμός
Μοτίβα
Graphs
Parallelism
Motifs

description: Οι Γράφοι χρησιμοποιούνται για την αναπαράσταση πληροφορίας για μια πληθόρα από επιστημονικά πεδία. Επίσης χρησιμοποιούνται για την εξαγωγή πληροφορίας. Το σετ των τεχνικών και των εργαλείων που χρησιμοποιούνται για την εξαγωγή χρήσιμων πληροφοριών από γράφους ονομάζεται graph mining. Οι κλίκες είναι από τα βασικές χρήσιμες πληροφορίες που μπορούν να εξαχθούν από έναν γράφο. Μπορούν να υποδηλώνουν αρκτά διαφορετικά πράγματα, με βάση τα δεδομένα που αναπαριστά ο γράφος και αυτές οι πληροφορίες έχουν πολλές χρήσεις. Η απαρίθμηση όλων των κλικών ενός γράφου αλλά και η εύρεση της μεγαλύτερης κλίκας που υπάρχει σε έναν γράφο είναι χρήσιμες πληροφορίες αλλά είναι δύσκολο να εξαχθούν. Τα προβλήματα αυτά είναι NP-hard που σημαίνει ότι για μεγάλους γράφους απαιτούν υπερβολικά πολύ χρόνο κάτι που τα καθιστά αδύνατο να λυθούν. Στην εργασία Retrieving Top Weighted Triangles in Graphs ένας αλγόριθμος για την γρήγορη απαρίθμηση των k βαρύτερων τριγώνων προτείνεται. Σε αυτή την εργασία ο προτινόμενος αλγόριθμος συγκρίνεται με τον αλγόριθμο brute force για γράφους με διαφορετικές κατανομές στα βάρυ των ακμών τους Ο κύριως στόχος αυτής της εργασίας είναι η μετατροπή του προαναφερθέντος αλγορίθμου από κεντρικοποιημένο σε παράλληλο και η επέκταση του για κλίκες μεγαλύτερου μεγέθους. Ο επεκταμένος αλοριθμος εμφανίζεται σε δύο εκδοχές, κεντρικοποιημένος και παραλλήλος, επίσης ανάλυση έχει πραγματοποιηθεί για την ορθότητά του και την απόδοσή του. Ο παράλληλος αλγόριθμος που βρίσκει τα βαρύτερα τρίγωνα συγκρίνεται με τον κεντρικοποιημένο και ελέγχεται για την δυνατότητα κλιμάκωσής του. Ο επεκταμένος παράλληλος αλγόριθμος επίσης ελέγχετε για την δυνατότητα κλιμάκωσής του
description: Graphs are used to represent information for a variety of scientific fields. They also are used in order to extract information. The set of techniques and tools used to extract useful information from graphs is called graph mining. Cliques are one of the core valuable information that can be extracted from a graph. It can denote several things depending on the data that the graph is representing and that information have many applications. Enumerating all the cliques in a graph or finding the order of the biggest clique in it are valuable information but they are hard to attain. Those problems are NP-hard meaning that for big graphs they require so much time that they are impossible to be solved. In paper Retrieving Top Weighted Triangles in Graphs an algorithm that can enumerate quickly the heaviest k triangles is proposed. In this thesis the proposed algorithm is compared against the brute force algorithm for graphs with edge weights that follow different distributions. The main goal of this thesis is to convert the aforementioned algorithm which is centralized to parallel and also to extend it for cliques of greater size. The extended version of the algorithm is presented in two versions, centralized and parallel and an analysis has been made for its correctness and performance. The parallel version of the algorithm that finds the heaviest triangles has been compared against the centralized algorithm and tests for its scalability have been executed. The extended parallel algorithm has also been tested for scalability