Στοχαστική Δυναμική Απόψεων για Πρόβλεψη Ενδιαφερόντων σε Κοινωνικά Δίκτυα

Abstract

Σε αυτήν τη διπλωματική εργασία, εκμεταλλευόμαστε τη δομή πυρήνα-περιφέρειας και τις ισχυρές ομοφιλικές ιδιότητες των διαδικτυακών κοινωνικών δικτύων για την ανάπτυξη ταχύτερων και ακριβέστερων αλγορίθμων για την πρόβλεψη ενδιαφέροντος των χρηστών. Ο πυρήνας των σύγχρονων κοινωνικών δικτύων αποτελείται από σχετικά λίγους επιδραστικούς χρήστες, των οποίων τα προφίλ ενδιαφέροντος είναι διαθέσιμα στο κοινό, ενώ η πλειονότητα των περιφερειακών χρηστών ακολουθεί αρκετά από αυτά με βάση κοινά ενδιαφέροντα. Η προσέγγισή μας είναι να απορρίψουμε ένα μεγάλο μέρος του δικτύου, που αποτελείται από συνδέσεις μεταξύ περιφερειακών κόμβων και να προβλέψουμε τα συμφέροντα των περιφερειακών κόμβων ξεκινώντας από τα συμφέροντα των επιδραστικών τους συνδέσεων. Για το σκοπό αυτό, χρειαζόμαστε ένα επίσημο μοντέλο που να εξηγεί πώς τα κοινά ενδιαφέροντα οδηγούν σε συνδέσεις δικτύου. Με γνώμονα τις ισχυρές ομοφιλικές ιδιότητες που παρουσιάζουν τα σύγχρονα δια δικτυακά κοινωνικά δίκτυα (ΔΚΔ), προτείνουμε ένα νέο γενετικό μοντέλο βασισμένο στη δυναμική της γνώμης για απόψεις στα ΔΚΔ με βάση την ανταλλαγή απόψεων των πρακτόρων με τους k πλησιέστερους γείτονές τους. Πιο συγκεκριμένα, προτείνουμε ένα στοχαστικό μοντέλο σχηματισμού ενδιαφέροντος, το Nearest Neighbor Influence Model (NNIM), το οποίο είναι εμπνευσμένο από το μοντέλο Hegselmann-Krause και στοχεύει να εξηγήσει πώς η ομοφιλία διαμορφώνει το δίκτυο. Με βάση το ΝΝΙΜ, αναπτύσσουμε μια αποτελεσματική προσέγγιση για την πρόβλεψη των συμφερόντων των περιφερειακών χρηστών. Στη συνέχεια αναπτύσσουμε έναν αλγόριθμο για συμπερασμό παραμέτρων μέσω Μεταβολικού Expectation Maximization (EM) και αποδεικνύουμε ότι, κάτω από εύλογες υποθέσεις, οι εξισώσεις συμπερασμού μέσου πεδίου μοιάζουν με τις συμβατικές επαναληπτικές εξισώσεις των κλασικών ΔΔΑ και μπορούν να κλιμακωθούν αποτελεσματικά σε δίκτυα με εκατομμύρια χρήστες. Αποδεικνύουμε θεωρητικά ότι οι εξισώσεις μέσου πεδίου συγκλίνουν εντός πεπερασμένου χρόνου και ότι η Απόσταση Ολικής Μεταβολής (Total Variation Distance) σε κάθε χρονικό βήμα φράσσεται αυστηρά από πάνω από μια εκθετική συνάρτηση με βάση 1/ sqrt(k). Τέλος, αξιοποιούμε την ικανότητα του μοντέλου μας να προβλέπει ενδιαφέροντα μέσω κόμβων με μεγάλη επιρροή στα διαδικτυακά κοινωνικά δίκτυα, ξεπερνώντας τα σχετικά μοντέλα δυναμικής γνώμης και μεθόδους ενσωμάτωσης κόμβων (node embeddings) μέσω τυποποιημένων σημείων αναφοράς που υπάρχουν στην πρόσφατη βιβλιογραφία από άποψη των μετρικών Μέσου Τετραγωνικού Σφάλματος (ΜΤΣ) και Περιοχής κάτω από τη Χαρακτηριστική Καμπύλη Λειτουργίας του Δέκτη (AUC) και υπολογιστικού χρόνου σε δίκτυα διαφόρων μεγεθών.