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

Τίτλος:Ανίχνευση κοινοτήτων σε γράφους: Συγκριτική μελέτη και εφαρμογή σε γράφους από δεδομένα Web 2.0
Συγγραφείς:ΠλούταρχοςΣπυρίδωνος
Σχολή/Τμήμα: Αριστοτέλειο Πανεπιστήμιο Θεσσαλονίκης, Σχολή Θετικών Επιστημών, Τμήμα Πληροφορικής
Γλώσσα:Ελληνικά
Φυσική Περιγραφή:118 σελ.
Ημ/νία έκδοσης:2011
Περίληψη:Η σημερινή εποχή χαρακτηρίζεται από αυξημένο όγκο δεδομένων σε όλους τους τομείς και ιδιαίτερα όσον αφορά στον Παγκόσμιο Ιστό. Παράλληλα, η εμφάνιση του Web 2.0 εισήγαγε νέες τεχνολογίες στις οποίες η οργάνωση της γνώσης προσέλαβε περισσότερο κοινωνικό χαρακτήρα, με την έννοια ότι ο ρόλος των χρηστών είναι πλέον περισσότερο ενεργός. Τα συστήματα διαμοιρασμού πόρων με ετικέτες χρηστών ή αλλιώς Συστήματα Κοινωνικής Σήμανσης είναι μία από τις πιο γνωστές και δημοφιλείς εφαρμογές του Web 2.0. Χάρη σε αυτά, οι χρήστες έχουν τη δυνατότητα να διαμοιράζονται δεδομένα ποικίλων τύπων, όπως φωτογραφίες και βίντεο, να αλληλεπιδρούν με αυτά, αλλά και να χρησιμοποιούν λέξεις-κλειδιά, που συχνά αναφέρονται και ως ετικέτες (tags), για να τα περιγράψουν. Για τη μοντελοποίηση τέτοιων συστημάτων συνήθως γίνεται χρήση γράφων. Η διαδικασία αυτή αποτελεί πρόκληση καθώς το μέγεθος των γράφων πολλές φορές φτάνει τα εκατομμύρια ή ακόμα και δισεκατομμύρια κόμβους.

Ένα από τα βασικά χαρακτηριστικά των γράφων που αναπαριστούν πραγματικά συστήματα είναι η ύπαρξη δομής κοινοτήτων (community structure), δηλαδή ομάδων από κόμβους με περισσότερες εσωτερικές συνδέσεις παρά μεταξύ διαφορετικών ομάδων. Οι ομάδες αυτές, που στη βιβλιογραφία αναφέρονται ως κοινότητες (communities), μπορούν να αξιοποιηθούν για την επιτάχυνση διαδικασιών αναζήτησης και πλοήγησης των δεδομένων.

Η διαδικασία ανίχνευσης κοινοτήτων (community detection) εφαρμόζεται σε διαφόρους τομείς όπως είναι η κοινωνιολογία, η βιολογία και η επιστήμη των υπολογιστών, τομείς δηλαδή όπου είναι δυνατή η μοντελοποίηση των δεδομένων με χρήση γράφων. Στη συγκεκριμένη εργασία παρουσιάζουμε μια εκτενή ανάλυση της περιοχής, μελετώντας στη συνέχεια τέσσερις από τις πιο χαρακτηριστικές μεθόδους ανίχνευσης κοινοτήτων. Επιπλέον, στο πλαίσιο της εργασίας υλοποιήθηκε μία από αυτές τις μεθόδους που ανήκει στην κατηγορία των ιεραρχικών συσσωρευτικών αλγορίθμων ομαδοποίησης και περιγράφεται στο παράρτημα.

Η ανάπτυξη ενός αλγορίθμου είναι άρρηκτα συνδεδεμένη με την αξιολόγησή του. Ωστόσο, η έλλειψη δεδομένων με γνωστή δομή οδήγησε στη χρήση τεχνητών γράφων αναφοράς (benchmark graphs) με προκαθορισμένη δομή. Σημαντικό μέρος της εργασίας αφιερώνεται στη διεξαγωγή πειραμάτων με τεχνητά και πραγματικά σύνολα δεδομένων.

Συνοψίζοντας, πρέπει να τονίσουμε πως οι εξεταζόμενοι αλγόριθμοι μπορούν να φανούν χρήσιμοι σε ένα μεγάλο φάσμα εφαρμογών ομαδοποίησης και αναγνώρισης κοινοτήτων.



The prosperity of Web 2.0 and social media has resulted in the generation of diverse social networks of unprecedented scales, which present new challenges for graph-mining techniques. Social Tagging Systems, a typical Web 2.0 application, enable users to label digital data sources by using freely chosen textual descriptions, also referred to as tags. These systems are usually represented by use of graphs. The sizes of graphs often reach to millions or even billions of vertices. The need to deal with such a large number of nodes has produced a deep change in the way graphs are approached.

One of the most relevant features of graphs representing real systems is community structure or clustering, i.e. the organization of vertices in clusters, with many edges joining vertices of the same cluster, and comparatively few edges, joining vertices of different clusters. Such clusters, known as communities, can be considered as fairly independent compartments of a graph, and can be used to assist navigation and browsing of the network.

Community detection (i.e. a kind of graph-based clustering) is of great importance in sociology, biology and computer science, disciplines where systems are often represented as graphs. This problem is very hard and not yet satisfactory solved, despite the huge effort of a large interdisciplinary community of scientists working on it over the past few years. In this thesis project, we attempt a thorough exposition of the topic, first defining the main elements of the problem and then presenting four of the most significant community detection methods. Furthermore, in the context of this thesis project we have implemented one of these methods.

When a clustering algorithm is designed, it is necessary to test its performance, and compare it with that of other methods. The lack of data with known structure led to the use of computer generated networks, or benchmark graphs, for the evaluation of algorithms. Each benchmark graph encapsulates a pre-specified clustering. Clustering solutions derived by algorithms under evaluation are compared with the pre-specified clustering.

Our experimentation involves both experiments using a new class of benchmark graphs and experiments applied on real data collected from the usage of a popular Web 2.0 application. We conducted experiments on a dataset comprising publicly available images from Flickr©.

Finally, we present and discuss some research issues for

future exploration.
Επιβλέπων:Βακάλη,Α
Λέξεις Κλειδιά:1. Complex Networks, 3. Social Tagging Systems, 2. Ανίχνευση Κοινοτήτων, 1. Πολύπλοκα Δίκτυα, 3. Συστήματα Κοινωνικής Σήμανσης, 2. Community Detection
Σχετικά αρχεία:Πλήρες κείμενο: PDF Αρχείο με άδεια χρήσης Δείτε την σχετική άδεια κάνοντας κλικ εδώ!


 Δημιουργία εγγραφής 2011-02-09, τελευταία τροποποίηση 2015-05-05


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