Πτυχιακές Εργασίες GRI-2014-13489

Τίτλος:ΜΕΛΕΤΗ, ΥΛΟΠΟΙΗΣΗ ΚΑΙ ΕΠΕΚΤΑΣΗ ΑΛΓΟΡΙΘΜΩΝ ΑΝΙΧΝΕΥΣΗΣ ΚΟΙΝΟΤΗΤΩΝ
STUDY, IMPLEMENTATION AND EXTENSION OF COMMUNITY DETECTION ALGORITHMS
Συγγραφείς:'Ανδρονίδης' 'Αναστάσιος'
Σχολή/Τμήμα: Αριστοτέλειο Πανεπιστήμιο Θεσσαλονίκης, Σχολή Θετικών Επιστημών, Τμήμα Πληροφορικής
Γλώσσα:Ελληνικά
Φυσική Περιγραφή:124 σελ.
Ημ/νία έκδοσης:2014
Περίληψη:Οι γράφοι (ή αλλιώς δίκτυα) είναι ένα πολύ δυνατό εργαλείο για την κατανόηση της δομής, αλληλεπίδρασης και εξέλιξης πολύπλοκων τεχνολογικών, βιολογικών και κοινωνικών συστημάτων. Ένα από τα σημαντικότερα χαρακτηριστικά των γράφων που αναπαριστούν πραγματικά συστήματα είναι η ύπαρξη κοινοτικών δομών, όπου κοινότητα θεωρείται ένα σύνολο κόμβων οι οποίοι μοιράζονται μια κοινή - κρυφή τις περισσότερες φορές - ιδιότητα. Η ανίχνευση κοινοτήτων σε αυθαίρετους γράφους είναι ένα πολύ δύσκολο υπολογιστικά πρόβλημα καθώς ο αριθμός τους τις περισσότερες φορές είναι άγνωστος και οι ίδιες είναι συνήθως διαφορετικού μεγέθους και πυκνότητας. Παρ’ όλα αυτά έχουν αναπτυχθεί διάφορες μέθοδοι για ανίχνευση κοινοτήτων σε δίκτυα, οι οποίες ποικίλουν σε βαθμό επιτυχίας και αποδοτικότητας. Το πρόβλημα ανίχνευσης κοινοτήτων σε γράφους εντείνεται, καθώς το μέγεθος των γράφων εκτινάσσεται σε εκατομμύρια ή και δισεκατομμύρια κόμβους και ακμές. Ένα απλό σημερινό παράδειγμα μπορεί να αποτελέσει το κοινωνικό δίκτυο του Facebook1, θεωρώντας τους χρήστες του ως κόμβους και τις διαπροσωπικές τους σχέσεις ως ακμές, ή ακόμα το δίκτυο μεταξύ των σελίδων της Wikipedia όπου οι σελίδες θεωρούνται κόμβοι και οι υπερσύνδεσμοι μεταξύ τους, ακμές. Εύκολα διαπιστώνει κανείς ότι το μέγεθος ενός τέτοιου γράφου είναι αποτρεπτικό για την αποτελεσματική εφαρμογή αλγορίθμων οι οποίοι παρουσιάζουν προβλήματα επεκτασιμότητας. Έτσι ανακύπτει η ανάγκη για παράλληλες μεθόδους οι οποίες θα μπορέσουν να δώσουν ικανοποιητικά αποτελέσματα σε μικρό χρόνο. Στην πτυχιακή αυτή i) ερευνούμε και υλοποιούμε συγκεκριμένες μεθόδους ανίχνευσης κοινοτήτων σε μεγάλους γράφους, ανακαλύπτοντας τα πλεονεκτήματα και τα μειονεκτήματά τους, ii) τις αξιολογούμε πειραματικά και συγκρίνουμε τα αποτελέσματά τους, και τέλος, iii) παρουσιάζουμε επεκτάσεις για την βελτίωσή τους. The graphs (or networks) are a very powerful tool for understanding the structure, the interactions and the evolution of complex technological, biological and social systems. One significant feature of graphs that represent real systems is the existence of community structures, where a given community is considered as a set of nodes that share a common – usually hidden - property. Detecting communities in arbitrary graphs is a very difficult computational problem because their number is mostly unknown and they usually have different size and density. However, several methods have been developed for detecting communities in networks, which vary in terms of degree of success and efficiency. The problem of detecting communities in graphs grows as the size of the graph increases to millions or even billions of nodes and edges. As a simple example, today one can consider the social network of Facebook2, which comprises users as nodes and their interpersonal relationships as edges, or even the network between the pages of Wikipedia where the pages are considered as nodes and the hyperlinks between them as edges. It is easy to observe that the size of such graphs is detrimental to the efficient implementation of algorithms that are characterized by scalability issues. Thus, the need for parallel methods arises, which can derive qualitative results in short time. In this thesis: i) we investigate and implement methods for detecting communities in large graphs, discovering their advantages and disadvantages, ii) we, next, experimentally evaluate them comparing their results, and finally iii) we present extensions to improve them.
Επιβλέπων:Α. Βακάλη
Λέξεις Κλειδιά:Big Data, Graphs, Μεγάλα δεδομένα, Γράφοι, Δίκτυα, Networks
Σχετικά αρχεία:Πλήρες κείμενο: PDF Αρχείο με άδεια χρήσης Δείτε την σχετική άδεια κάνοντας κλικ εδώ!


 Δημιουργία εγγραφής 2014-12-02, τελευταία τροποποίηση 2015-04-30


Πλήρες κείμενο:
Κατέβασμα πλήρους κειμένου
PDF Αρχείο
με άδεια:Δείτε την σχετική άδεια κάνοντας κλικ εδώ!