Αλγόριθμοι διαχείρισης δεδομένων και εξαγωγή γνώσης σε εφαρμογές γράφων

Abstract

This thesis focuses on exploring and developing methods for data management and knowledge extraction in environments where data is represented in the form of graphs. Specifically, this thesis presents algorithms applied in Sensor Networks and Social Networks, using theoretical tools from the Graph Theory research area. For applications in sensor networks, this thesis examines problems related to data storage and topology control. While in storage control, the incentive is to minimize the stored data without increasing the time taken to reply to queries from the user (query latency), in the topology control area, the motivation is to minimize the energy consumption among sensors, by creating structures that utilize the logical neighbors of each sensor rather than the physical neighbors. In the research area of social networks, this thesis explores the problem of link prediction. The motive in this case is the most efficient recommendation of friends to a user when it comes to social networks that contain information about the friendships between users, and the efficient recommendations of locations and activities to a user, when it comes to the so-called geo-social networks, which store both user information and geographic data. Finally, the thesis deals with the field of explaining recommendations and presents the different types of explanations that have been analyzed in the literature, while experimental results are also presented and are used to decide upon the most efficient explanation style.

Η παρούσα διατριβή εστιάζει στη διερεύνηση και την ανάπτυξη μεθόδων διαχείρισης δεδομένων και εξαγωγής γνώσης σε περιβάλλοντα όπου τα δεδομένα αναπαριστώνται με τη μορφή γράφων. Συγκεκριμένα, η διατριβή παρουσιάζει αλγορίθμους εφαρμοσμένους σε Δίκτυα Αισθητήρων (Sensor Networks) και Κοινωνικά Δίκτυα (Social Networks), χρησιμοποιώντας θεωρητικά εργαλεία από το αντικείμενο της Αλγοριθμικής Θεωρίας Γράφων. Όσον αφορά στις εφαρμογές σε Δίκτυα Αισθητήρων, η διατριβή εξετάζει προβλήματα σχετικά με την αποθήκευση δεδομένων (storage) και τον έλεγχο τοπολογίας (topology control). Στη μεν αποθήκευση δεδομένων, το κίνητρο είναι η ελαχιστοποίηση των αποθηκευμένων δεδομένων χωρίς όμως και την αύξηση του χρόνου παραλαβής απαντήσεων στα ερωτήματα του χρήστη (query latency). Στο δε έλεγχο τοπολογίας το κίνητρο είναι η ελαχιστοποίηση της καταναλισκόμενης ενέργειας μεταξύ των αισθητήρων, δημιουργώντας δομές που ξεχωρίζουν τους λογικούς γείτονες (logical neighbors) του κάθε αισθητήρα, από τους φυσικούς (physical neighbors). Στον τομέα των Κοινωνικών Δικτύων, η διατριβή διερευνά το πρόβλημα της πρόβλεψης συνδέσμων (link prediction). Το κίνητρο σε αυτήν την περίπτωση είναι η αποδοτικότερη σύσταση φίλων (friend recommendation) σε ένα χρήστη, όταν αναφερόμαστε σε κοινωνικά δίκτυα που εμπεριέχουν μόνο πληροφορία για τις φιλίες μεταξύ χρηστών, καθώς και η αποδοτικότερη σύσταση τοποθεσιών και δραστηριοτήτων (location/activity recommendation) σε κάποιο χρήστη, όταν αναφερόμαστε στα λεγόμενα γεω-κοινωνικά δίκτυα (geo-social networks) που εμπεριέχουν και γεωγραφικά δεδομένα των χρηστών. Τέλος, η διατριβή ασχολείται και με τον τομέα της επεξήγησης συστάσεων (recommendation explanations) και παρουσιάζει τους διαφορετικούς τύπους επεξηγήσεων που έχουν αναλυθεί στη βιβλιογραφία, ενώ καταλήγει και στον αποδοτικότερο τύπο βάσει αντίστοιχων πειραμάτων που έχουν πραγματοποιηθεί.