Recommender systems and community detection in graphs.

Abstract

This thesis consists of two parts. The first part presents an overview of the literature and the proposals that exist in general, with which techniques work, what properties each one has, the pros and cons of each method, what problems they are facing and how these systems are evaluated. Each algorithm is presented along with examples from the real world. At the end of the first part of the thesis is an extensive description as well as results from an experiment based on the SCoR algorithm, an algorithm constructed to produce optimal recommendations based on the modified Vivaldi algorithm. The second part is about community detection systems in social media. This has to do with systems that, based on some “relationships” of the end-users of a social network, discover the "hidden" community of users hidden behind these explicit relationships. There is a description of how such a community can be formed at the graph level, depending on the logic of the algorithm that is required to discover this graph. We present the available techniques that are used by the various approaches. In addition, the best-known algorithms of the field are presented with results from experiments that have been performed and the advantages and disadvantages are presented for each case. At the end of the second part, we present the results of the experiment of the SCCD algorithm, which is again based on the Vivaldi algorithm and performs accurate community detection.

Η εργασία αυτή αποτελείται από δύο σκέλη. Το πρώτο σκέλος έχει να κάνει με τα συστήματα συστάσεως που υπάρχουν γενικά, τις τεχνικές στις οποίες βασίζονται, τις ιδιότητες έχει το καθένα, τα υπέρ και τα κατά της κάθε μεθόδου, τα προβλήματα που καλούνται να αντιμετωπίσουν καθώς και τους τρόπους με τους οποίους αυτά τα συστήματα αξιολογούνται. Γίνεται μια παρουσίαση κάθε καταγεγραμμένης τεχνικής – αλγορίθμου και γίνεται αναφορά σε συγκεκριμένα παραδείγματα από τον πραγματικό κόσμο. Στο τέλος του πρώτου σκέλους υπάρχει εκτενής περιγραφή του αλγορίθμου SCoR καθώς και τα αποτελέσματα των πειραμάτων που έγιναν με βάση τον SCoR, έναν αλγόριθμο που κατασκευάστηκε για να παράγει βέλτιστες συστάσεις δεδομένων και βασίζεται στον τροποποιημένο αλγόριθμο Vivaldi. Το δεύτερο σκέλος αυτής της μεταπτυχιακής εργασίας έχει να κάνει με τα συστήματα αναγνώρισης κοινοτήτων στα μέσα κοινωνικής δικτύωσης. Εστιάζει σε συστήματα τα οποία με βάση κάποιες επιλογές των τελικών χρηστών ενός κοινωνικού δικτύου, έρχονται να ανακαλύψουν τις «κρυφές» κοινότητες των χρηστών όπως αυτές διαμορφώνονται από τις «κοινές» επιλογές των χρηστών. Γίνεται μια περιγραφή για το πως μπορούν να σχηματιστούν αυτές οι κοινότητες σε επίπεδο γράφων, ανάλογα με τη λογική του αλγορίθμου ο οποίος καλείται να τις εντοπίσει. Παρουσιάζονται οι διαθέσιμες τεχνικές που μπορούν να χρησιμοποιηθούν από τους διάφορους αλγορίθμους. Επιπλέον παρουσιάζονται οι πιο γνωστοί αλγόριθμοι του χώρου με αποτελέσματα από πειράματα που έχουν γίνει και αποτυπώνονται τα υπέρ και τα κατά της κάθε περίπτωσης. Στο τέλος του δεύτερου σκέλους γίνεται παρουσίαση των αποτελεσμάτων του πειράματος του αλγορίθμου SCCD ο οποίος είναι πάλι βασισμένος στον τροποποιημένο αλγόριθμο του Vivaldi.