Analysis of influence on social networks

Abstract

The emergence of Online Social Networks (OSNs) in the Internet era has provided a new dimension in the opinion diffusion. Online users can share freely and instantly their beliefs with their friends and comment or respond to posts of other users. New terms have arisen stemming from the settings of the modern online landscape. Influencers yield significant impact on other members of their community and it comes as no surprise that major companies have developed marketing strategies that utilize the properties of the most influential nodes in OSNs in order to promote their products and services. Recently, disturbing phenomena of misinformation and manipulative bias have occurred that kickstarted a vivid debate about the role of OSNs in modern societies.The structural characteristics of OSNs and the activity of their online users offer solid ground for research and experimentation. A significant number of scientific efforts focus on the analysis of the influence yielded to online users based on their relations with other members of the community and their activity. The theories and models proposed by the field of opinion dynamics serve as a valuable tool that supports the researchers’ endeavors. Many algorithmic approaches of the influence analysis base their incentives on the findings and formulations of opinion diffusion models in order to tackle their challenging task. In this thesis, we utilize the mathematical formulation of a prominent opinion diffusion model, the DeGroot model, in order to examine the mechanism of influence in social graphs. Our motivation stems from the need to investigate the range of intervention that can be achieved by strategic entities and the impact of their manipulative approach on the community. The mathematical formulation of the DeGroot model enables us to define influence scenarios and examine their behavior on a wide range of social graphs through model checking techniques. In order to produce realistic scenarios that can be applied on real – life cases, we develop intervention schemes that incorporate the activity of a single or multiple users in the social network. A variation of these scenarios entails the limitations of complex settings where the strategic entities are constrained in the construction of an optimal strategy. Experimental results confirm that our approach is applicable on large social networks although, in the case of the constrained settings, the analysis exhibits poor performance due to the increased complexity of the scenario.Furthermore, we develop a methodology based on the DeGroot model with stubborn agents for the analysis of complex real – life graphs generated by modern OSNs in order to extract valuable information from their structural characteristics. The application of our approach on the Greek news media and political scene confirms our hypothesis that the structure of OSNs suffice for the estimation of vague characteristics such as the political affinity and orientation of online nodes of interest. The efficacy of the proposed technique is undoubtably supported by our endeavor to approximate an elaborate feature such as the political impartiality of news media. The case study of the Greek news media and political scene of April 2018 provides clear evidence that our algorithmic approach can answer bewildering questions such as: “Which is the most impartial news media in a political scene”.

Η εμφάνιση των μέσων κοινωνικής δικτύωσης στην εποχή του Διαδικτύου έδωσε μια νέα διάσταση στη διάχυση της απόψεων και στη διαμόρφωση της κοινής γνώμης. Οι χρήστες του Διαδικτύου μπορούν να μοιράζονται ελεύθερα και άμεσα τις απόψεις τους με τους διαδικτυακούς τους φίλους και να σχολιάζουν ή να απαντούν σε αναρτήσεις άλλων χρηστών. Επιπλέον, κάθε άτομο μπορεί να συμμετέχει σε συζητήσεις σχετικά με πληθώρα θεμάτων σε εικονικούς τοίχους και ιστολόγια και να έχει πρόσβαση σε ειδήσεις επίσημων και ανεπίσημων πηγών από όλο τον κόσμο. Νέοι όροι και φαινόμενα έχουν προκύψει από τα νέα δεδομένου του σύγχρονου διαδικτυακού τοπίου. Πολλοί κόμβοι ασκούν ισχυρή επιρροή σε άλλα μέλη της διαδικτυακής κοινότητάς τους και δεν αποτελεί έκπληξη το γεγονός ότι οι μεγάλες εταιρείες έχουν αναπτύξει στρατηγικές προώθησης που χρησιμοποιούν τις ιδιότητες των κόμβων αυτών για να επιτύχουν αύξηση των πωλήσεών τους. Πρόσφατα, εμφανίστηκαν ανησυχητικά φαινόμενα παραπληροφόρησης και χειραγώγησης της κοινής γνώμης με αποτέλεσμα να ξεκινήσει μια ζωηρή συζήτηση για το ρόλο των μέσων κοινωνικής δικτύωσης στις σύγχρονες κοινωνίες. Τα δομικά χαρακτηριστικά των μέσων κοινωνικής δικτύωσης και η δραστηριότητα των διαδικτυακών χρηστών τους προσφέρουν στέρεο έδαφος για έρευνα και πειραματισμό. Ένας σημαντικός αριθμός επιστημονικών προσπαθειών επικεντρώνεται στην ανάλυση της επιρροής που ασκείται στους χρήστες του Διαδικτύου μέσω των σχέσεών τους με άλλα μέλη της κοινότητας και τη διαδικτυακή τους παρουσία. Οι θεωρίες και τα μοντέλα που προτείνονται από το πεδίο της δυναμικής των απόψεων (opinion dynamics) χρησιμεύουν ως ένα πολύτιμο εργαλείο που υποστηρίζουν τις ερευνητικές προσπάθειες. Πολλές αλγοριθμικές προσεγγίσεις της ανάλυσης επιρροής βασίζουν τα κίνητρά τους στα ευρήματα και τις διατυπώσεις των μοντέλων διάχυσης απόψεων, προκειμένου να δώσουν απαντήσεις σε δύσκολα προβλήματα.Στην παρούσα διδακτορική διατριβή, αξιοποιούμε τη μαθηματική διατύπωση ενός εξέχοντος μοντέλου διάχυσης απόψεων, του μοντέλου DeGroot, προκειμένου να εξετάσουμε τον μηχανισμό επιρροής στα κοινωνικά γράφους. Το κίνητρό μας πηγάζει από την ανάγκη να διερευνηθεί το εύρος της παρέμβασης που μπορεί να επιτευχθεί από στρατηγικές οντότητες και ο αντίκτυπος της χειραγώγησης στη διαδικτυακή κοινότητα. Η μαθηματική διατύπωση του μοντέλου DeGroot μας επιτρέπει να καθορίσουμε σενάρια επιρροής και να εξετάσουμε τη συμπεριφορά τους σε ένα ευρύ φάσμα κοινωνικών γράφων μέσω τεχνικών ελέγχου μοντέλων (model checking).Στο πρώτο στάδιο της διδακτορικής έρευνας, εξετάζουμε τη δυνατότητα διατύπωσης του αυτούσιου μοντέλου DeGroot με τεχνικές ελέγχου μοντέλων και ελέγχουμε την επίδοση της ανάλυσής του. Οι μετρήσεις σχετικά με τους χρόνους εκτέλεσης και τις δυνατότητες εφαρμογής του μοντέλου σε ρεαλιστικά σενάρια μας ενθαρρύνουν να προχωρήσουμε σε περαιτέρω επεκτάσεις και σε διατυπώσεις σεναρίων επιρροής.Η δέσμευσή μας να διερευνήσουμε ρεαλιστικά σενάρια επιρροής μας κατηύθυνε στον ορισμό σεναρίων παρέμβασης από έναν μόνο ή πολλούς χρήστες. Το Πρόβλημα Επιρροής DeGroot (DeGroot Influence Problem - DIP) συνιστά την πρώτη προσπάθεια μας να εισαγάγουμε μια στρατηγική οντότητα που επιδιώκει την επικράτηση της άποψής του στη διαδικασία σχηματισμού της κοινής γνώμης του κοινωνικού γράφου. Τα πειραματικά αποτελέσματα του μοντέλου επιβεβαίωσαν την υπόθεσή μας ότι η στοχαστική φύση του μοντέλου απόψεων επιτρέπει την ανάλυση του σεναρίου μέσω λογισμικού από τον τομέα του ελέγχου μοντέλων. Η διατύπωση του σεναρίου και η απόδοσή του επέτρεψαν την εφαρμογή του σε μεγάλους κοινωνικούς γράφους και υποστήριξαν τον ισχυρισμό μας ότι το μοντέλο μπορεί να χρησιμοποιηθεί σε πραγματικά κοινωνικά δίκτυα.Η επέκταση του σεναρίου DIP με την εισαγωγή περιορισμών σχετικά με τις ενέργειες στη δόμηση στρατηγικής οδήγησε στον ορισμό του Προβλήματος Περιορισμένης Επιρροής DeGroot (Constrained DeGroot Influence Problem – CDIP) που αντιπροσωπεύει ρεαλιστικά σχήματα παρέμβασης όπου υπάρχουν περιορισμοί στην ανάπτυξη μιας στρατηγικής. Ο ορισμός του μοντέλου CDIP περιγράφει με επιτυχία ένα αφηρημένο σενάριο περιορισμένης επιρροής. Ωστόσο, τα πειραματικά αποτελέσματα αποκάλυψαν την αδυναμία της προσέγγισής μας στην εφαρμογή του μοντέλου σε μεγάλα κοινωνικά γραφήματα. Η επικρατέστερη αιτία του φαινομένου αυτού αποδίδεται στη σημαντικά αυξημένη πολυπλοκότητα του μοντέλου. Ωστόσο, εξ όσων γνωρίζουμε, τα λογισμικά αναλυτικής μαθηματικής επίλυσης αδυνατούν να αναλύσουν το προτεινόμενο μοντέλο σε μια περιγραφή υψηλού επιπέδου όπως επιτυγχάνεται από την προσέγγισή μας.Η εισαγωγή μιας δεύτερης στρατηγικής οντότητας στο μοντέλο DIP μετέτρεψε το μοντέλο στο Παίγνιο DeGroot (DeGroot Game - DG). Αυτή η επέκταση αποτελεί τη φυσική εξέλιξη της DIP που περιγράφει με μεγαλύτερη ακρίβεια πραγματικές καταστάσεις. Ο ορισμός του μοντέλου DG διατυπώνει ένα αφηρημένο σενάριο στρατηγικής παρέμβασης από δύο παίκτες και μπορεί να χρησιμοποιηθεί αποτελεσματικά για ανταγωνιστικές ή συνασπιστικές εκδοχές του παιχνιδιού. Με βάση μια σειρά πειραμάτων σε ανταγωνιστικές ρυθμίσεις του μοντέλου αποδείξαμε τη αποδοτικότητα της τεχνικής μας στην εφαρμογή του σε πραγματικά κοινωνικά γραφήματα.Η έρευνά μας επεκτείνεται με την εφαρμογή του μοντέλου DeGroot, και συγκεκριμένα της εκδοχής του με πεισματάρηδες κόμβους (stubborn agents), σε κοινωνικά γραφήματα που βασίζονται στη δομή των σύγχρονων μέσων κοινωνικής δικτύωσης. Στην παρούσα διατριβή, προτείνεται μια μεθοδολογία για την ανάλυση σύνθετων πλαισίων από την πραγματική ζωή την οποία και εφαρμόσαμε στο τοπίο της πολιτικής. Με την εφαρμογή της στην Ελληνική ειδησεογραφική και πολιτική σκηνή, η τεχνική μας κατάφερε να αντλήσει πολύτιμες πληροφορίες για κόμβους ενδιαφέροντος. Η πολιτική συνάφεια με κόμματα και ο πολιτικός προσανατολισμός των εκλεγμένων βουλευτών και των πηγών ειδήσεων αποτιμήθηκαν με ακρίβεια, όπως επιβεβαιώνεται από τα ευρήματά μας. Η αξιολόγηση των αποτελεσμάτων μας επιβεβαίωσε τόσο την πρότασή μας για την εξαγωγή ενός πυκνού πληροφοριακά κοινωνικού γραφήματος από τα σύγχρονα μέσα κοινωνικής δικτύωσης όσο και την αποτελεσματικότητα της τεχνικής μας στην εξαγωγή των πολιτικών προφίλ των μελών της κοινότητας.Επιπλέον, προβήκαμε στις απαραίτητες προσαρμογές για να αντιμετωπίσουμε το δύσκολο πρόβλημα της αποτίμησης των χαρακτηριστικών του ιδανικού αμερόληπτου μέσου και της εκτίμησης της απόκλισης των πραγματικών ειδησεογραφικών μέσων από αυτό. Το πρόβλημα της αποκάλυψης των πολιτικών κλίσεων των ειδησεογραφικών πηγών τυγχάνει σημαντικής προσοχής από τους ερευνητές της ανάλυσης κοινωνικών δικτύων και θεωρούμε ότι τα εντυπωσιακά επιτυχημένα ευρήματα της προσέγγισής μας αποτελούν σημαντική συμβολή της μελέτης μας.