Data analytics on graphs

Abstract

Nowadays, there is an increasing need for brands (stakeholders) to effectively and efficiently connect with their customers in both spatial and social domains so as to grow their revenues. In spatial field, there is a variety of location-based services (e.g., Google Maps, Uber, Foursquare) for utilization by brands, whereas in social area, there are several social networks (e.g., Facebook, Instagram, VK) in which brands can maintain their own social network pages for advertising. In this thesis, we analyze and study fundamental social and spatial data operations on graphs that can significantly contribute to successful connection among brands and customers.In spatial domain, our contribution is the development of a spatial RDF system, named SRX and built upon the popular RDF-3X store, that provides efficient spatial RDF data operations. In particular, SRX supports three types of spatial queries: range selections (e.g. find entities within a given polygon), spatial joins (e.g. find pairs of entities whose locations are close to each other), and spatial k nearest neighbors (e.g. find the three closest entities from a given location). Further, SRX supports spatial updates (e.g., insertions and deletions of spatial RDF triples). SRX relies its good performance on a grid-scheme that approximates the geometries of the spatial entities inside their integer IDs. We extensively evaluate the performance of SRX for both queries and updates by comparing it with the systems RDF-3X, Virtuoso, GraphDB, and Strabon on LGD and YAGO datasets. Results show that SRX outperforms other systems for queries and incurs a little overhead to RDF-3X for updates.In social domain, we contribute by studying three novel content-aware recommendation problems relative to the Influence Maximization (IM) problem; IM seeks for the k users who can maximize the influence of a given post in a social network.The first problem we study, named Content-Aware Influence Maximization (CAIM), is the inverse variant of IM and seeks for the k features that can form the content of a non-given post so as to make it viral in a social network, starting its diffusion from a given set of initial adopters (subscribers of brand's social network page). We prove that CAIM does not have influence guarantees, and our experimental results on Gnutella and VK datasets show that our deployed heuristic algorithm is more practical than baseline and conventional greedy approaches to solve CAIM.The second problem we study is an adaptive (online) version of CAIM, named Adaptive Content-Aware Influence Maximization (ACAIM), that takes place in many rounds. In each round, the content of a post is sought, comprising k features, and the influence feedback of posts in previous rounds is utilized for the content decision of posts in next rounds. The target is to maximize the cumulative influence over all rounds. To solve ACAIM, we integrate Online Learning to Rank (OLR) techniques to our machine learning IM framework, and we further deploy a propagation model, a simulator running that model to generate realistic feedback, three ACAIM learners, and a thorough experimental study on various VK datasets for several brands.Finally, the third problem we study relates with how brands can maximize their subscription (instead of influence as happens in CAIM and ACAIM) in social networks. Specifically, we propose a content recommendation policy to brands for Gaining Subscribers by Messaging (GSM). The GSM problem applies in many rounds. In each round, GSM recommends to brands what content (consisting of k features) to publish in their social network pages and which m users to notify of that content. The aim is to maximize the cumulative subscription gain over all rounds. We develop three GSM solvers, and by conducting a rich experimental evaluation on different VK datasets, we ascertain the importance and practical value of GSM.

Στις μέρες μας, υπάρχει ολοένα και μεγαλύτερη ανάγκη για τις εταιρείες να συνδέονται αποτελεσματικά και αποδοτικά με τους πελάτες τους, σε χωρικό αλλά και σε κοινωνικό επίπεδο, έτσι ώστε να αυξήσουν τα έσοδα τους. Στο χωρικό πεδίο, υπάρχουν διάφορες εφαρμογές που χρησιμοποιούν τοποθεσία (π.χ., Google Maps, Uber, Foursquare) από τις οποίες μπορούν να επωφεληθούν οι εταιρείες, ενώ στο κοινωνικό πεδίο, υπάρχουν αρκετά κοινωνικά δίκτυα (π.χ., Facebook, Instagram, VK) στα οποία οι εταιρείες μπορούν να διατηρούν τις κοινωνικές σελίδες τους για διαφημιστικούς λόγους. Στη διατριβή αυτή, παρουσιάζουμε θεμελιώδεις κοινωνικές και χωρικές λειτουργίες γράφων που μπορούν σημαντικά να συνεισφέρουν στην επιτυχή σύνδεση των εταιρειών με τους πελάτες τους.Στο χωρικό πεδίο, η συνεισφορά μας έγκειται στην ανάπτυξη ενός χωρικού RDF συστήματος, με όνομα SRX και βασισμένο στο δημοφιλές RDF-3X σύστημα, το οποίο παρέχει αποδοτικές λειτουργίες χωρικών RDF δεδομένων. Συγκεκριμένα, το SRX υποστηρίζει τρία είδη χωρικών ερωτημάτων: επιλογές εμβέλειας (π.χ., βρείτε τις οντότητες εντός ενός πολυγώνου), χωρικές ενώσεις (π.χ, βρείτε ζευγάρια οντοτήτων που έχουν κοντινές τοποθεσίες), και k κοντινότερων χωρικών γειτόνων (π.χ., βρείτε τις τρεις πλησιέστερες οντότητες σε μια τοποθεσία). Επιπλέον, το SRX υποστηρίζει χωρικές ενημερώσεις (π.χ., εισαγωγές και διαγραφές χωρικών RDF τριπλέτων). Η καλή απόδοση του SRX βασίζεται σε ένα σχήμα πλέγματος που προσεγγίζει τις γεωμετρίες των χωρικών οντοτήτων μέσα στα ακέραια αναγνωριστικά τους. Αξιολογούμε εκτενώς την απόδοση του SRX και στα ερωτήματα και στις ενημερώσεις, συγκρίνοντας το με τα συστήματα RDF-3X, Virtuoso, GraphDB, και Strabon στα σύνολα δεδομένων LGD και YAGO. Τα αποτελέσματα δείχνουν ότι το SRX υπερτερεί των άλλων συστημάτων στα ερωτήματα και επιφέρει μια μικρή επιβάρυνση στο RDF-3X στις ενημερώσεις.Στο κοινωνικό πεδίο, η συνεισφορά μας έγκειται στη μελέτη τριών καινοτόμων προβλημάτων σύστασης βάσει περιεχομένου που σχετίζονται με το πρόβλημα Μεγιστοποίησης Επιρροής (ΜΕ). Το πρόβλημα ΜΕ ψάχνει τους k χρήστες που μπορούν να μεγιστοποιήσουν την επιρροή μιας δεδομένης ανάρτησης σε ένα κοινωνικό δίκτυο.Το πρώτο πρόβλημα που εξετάζουμε, ονομάζεται Μεγιστοποίηση Επιρροής Βάσει Περιεχομένου (ΜΕΒΠ), και αποτελεί την αντίστροφη παραλλαγή του ΜΕ. Το πρόβλημα ΜΕΒΠ ψάχνει τα k χαρακτηριστικά που μπορούν να σχηματίσουν το περιεχόμενο μιας μη-δεδομένης ανάρτησης έτσι ώστε αυτή να μπορεί να γίνει δημοφιλής σε ένα κοινωνικό δίκτυο, ξεκινώντας τη διάδοση της από ένα δεδομένο σύνολο συνδρομητών της κοινωνικής σελίδας της εκάστοτε εταιρείας. Αποδεικνύουμε ότι το ΜΕΒΠ δεν έχει εγγυήσεις επιρροής, ενώ τα πειραματικά μας αποτελέσματα στα σύνολα δεδομένων Gnutella και VK δείχνουν ότι ο ευρετικός αλγόριθμος που υλοποιήσαμε είναι περισσότερο πρακτικός από απλές και άπληστες προσεγγίσεις που λύνουν το ΜΕΒΠ.Το δεύτερο πρόβλημα που εξετάζουμε είναι μια προσαρμοστική (πραγματικού χρόνου) εκδοχή του ΜΕΒΠ, ονομάζεται Προσαρμοστική Μεγιστοποίηση Επιρροής Βάσει Περιεχομένου (ΠΜΕΒΠ), και λαμβάνει χώρα σε πολλούς γύρους. Σε κάθε γύρο, αναζητείται το περιεχόμενο μιας ανάρτησης που αποτελείται από k χαρακτηριστικά, ενώ η ανάδραση επιρροής των αναρτήσεων σε προηγούμενους γύρους αξιοποιείται στη δημιουργία περιεχομένου για τις αναρτήσεις των επόμενων γύρων. Ο στόχος είναι η μεγιστοποίηση της συνολικής επιρροής σε όλους τους γύρους. Για να λύσουμε το ΠΜΕΒΠ, ενσωματώνουμε τεχνικές Πραγματικού Χρόνου Μάθησης Βάσει Κατάταξης στο μηχανικής μάθησης πλαίσιο εργασίας μας που σχεδιάσαμε για μεγιστοποίηση επιρροής, και περαιτέρω υλοποιήσαμε ένα μοντέλο διάδοσης, έναν προσομοιωτή που τρέχει το εν λόγω μοντέλο για την παραγωγή ρεαλιστικής ανάδρασης, τρεις αλγορίθμους μάθησης, και μια εξονυχιστική πειραματική μελέτη σε ποικίλα σύνολα δεδομένων VK για αρκετές εταιρείες.Τέλος, το τρίτο πρόβλημα που εξετάζουμε σχετίζεται με το πως οι εταιρείες μπορούν να μεγιστοποιήσουν την συνδρομή τους (αντί για την επιρροή τους όπως συμβαίνει στα ΜΕΒΠ και ΠΜΕΒΠ) στα κοινωνικά δίκτυα. Συγκεκριμένα, προτείνουμε μια πολιτική σύστασης περιεχομένου στις εταιρείες για την Απόκτηση Συνδρομητών μέσω Μηνυμάτων (ΑΣΜ). Το ΑΣΜ πρόβλημα εφαρμόζεται σε πολλούς γύρους. Σε κάθε γύρο, το ΑΣΜ συστήνει στις εταιρείες το περιεχόμενο (αποτελούμενο από k χαρακτηριστικά) που πρέπει να δημοσιεύσουν στις κοινωνικές σελίδες τους και τους m χρήστες που πρέπει να ειδοποιήσουν για το εν λόγω περιεχόμενο. Ο στόχος είναι η μεγιστοποίηση της συνολικής απόκτησης συνδρομητών σε όλους τους γύρους. Για να λύσουμε το ΑΣΜ, υλοποιήσαμε τρεις αλγορίθμους, ενώ πραγματοποιώντας μια εκτενή πειραματική αξιολόγηση σε διάφορα σύνολα δεδομένων VK, διαπιστώνουμε την σημαντική αξία του ΑΣΜ.