Data analytics on graphs
Authors: Θεοχαρίδης Κωνσταντίνος 
Published: September 2022

Στις μέρες μας, υπάρχει ολοένα και μεγαλύτερη ανάγκη για τις εταιρείες να συνδέονται αποτελεσματικά και αποδοτικά με τους πελάτες τους, σε χωρικό αλλά και σε κοινωνικό επίπεδο, έτσι ώστε να αυξήσουν τα έσοδα τους. Στο χωρικό πεδίο, υπάρχουν διάφορες εφαρμογές που χρησιμοποιούν τοποθεσία (π.χ., 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, διαπιστώνουμε την σημαντική αξία του ΑΣΜ.