Please use this identifier to cite or link to this item: https://apothesis.eap.gr/handle/repo/36014
Title: Μελέτη και Υλοποίηση Αλγορίθμων Εύρεσης Κοινοτήτων σε Μεγάλα Γραφήματα
Authors: Γεμενετζής, Χρήστος
Advisor: Παπαδόπουλος , Απόστολος
Keywords: εύρεση κοινοτήτων;μεγάλα γραφήματα;k-Medoids;k-Center;Farthest First Traversal;Louvain;community detection;large graphs;clustering;partitioning graphs
Issue Date: 23-Sep-2017
Abstract: Με την δημιουργία του διαδικτύου αλλά και των ιστοσελίδων κοινωνικής δικτύωσης, οι περισσότεροι πολίτες κάθε χώρας μπορούν να διατηρούν προσωπικούς λογαριασμούς και να επικοινωνούν μέσω αυτών διαδικτυακά. Η συχνότερη ή πυκνότερη επικοινωνία μεταξύ ομάδων χρηστών του διαδικτύου σε σχέση με τους υπόλοιπους χρήστες, μπορεί να προκαλέσει το ενδιαφέρον των σύγχρονων επιστημών και να υποδηλώσει την ύπαρξη κοινοτήτων του διαδικτύου. Η αναπαράσταση του διαδικτύου και όχι μόνο, γίνεται με γραφήματα. Το μέγεθος των γραφημάτων αυτών μπορεί να έχει εκατομμύρια, αλλά και δισεκατομμύρια κορυφές ή ακμές, μέγεθος που χρονικά ή χωρικά δεν είναι εύκολο να διαχειριστεί ένας υπολογιστής. Η εύρεση κοινοτήτων, σε γραφήματα τέτοιου μεγέθους, είναι ένα τμήμα της επιστήμης εξόρυξης δεδομένων σε γραφήματα (Graph Mining), που είναι ακόμα ρευστό. Τα διαφορετικά είδη προβλημάτων, στην εύρεση ομάδων κορυφών σε ένα γράφημα ή η διαφορετική δομή των γραφημάτων, οδηγούν τους επιστήμονες να παράγουν πολλούς και διαφορετικούς αλγόριθμους εύρεσης κοινοτήτων σε γραφήματα, ώστε να πετύχουν την βέλτιστη λύση. Σε αυτήν την διπλωματική εργασία γίνεται υλοποίηση και μελέτη τριών γνωστών αλγορίθμων εύρεσης κοινοτήτων σε γραφήματα, του k-Medoids, του k-Centers Farthest First Traversal και του Louvain. Η υλοποίηση γίνεται στην γλώσσα προγραμματισμού Python, η οποία είναι μια ανερχόμενη γλώσσα προγραμματισμού με πολύ απήχηση και είναι μία από τις γλώσσες που υποστηρίζονται από την πλατφόρμα Apache Spark, η οποία χρησιμοποιείται ευρέως στην περιοχή της ανάλυσης μεγάλων δεδομένων (big data analytics). Με την υλοποίηση πειραμάτων αναλύονται η συμπεριφορά, η χρήση της μνήμης, το πλήθος των κοινοτήτων που παράγονται αλλά και ο χρόνος εκτέλεσης των αλγορίθμων σε μεγάλα γραφήματα. Αναδεικνύονται τα προβλήματα του κάθε αλγόριθμου ξεχωριστά, στους τέσσερις αυτούς τομείς, και υλοποιούνται παραλλαγές προγραμματισμού των αλγορίθμων, με στόχο την επίλυση των προβλημάτων. Τέλος, δημιουργείται και υλοποιείται υβριδικός αλγόριθμος που μπορεί να επιλύσει ταυτόχρονα τα προβλήματα όλων των προηγούμενων.
Appears in Collections:ΠΛΣ Διπλωματικές Εργασίες



Items in Apothesis are protected by copyright, with all rights reserved, unless otherwise indicated.