Algorithmic analysis of user behavior in social media

Abstract

Social networks are ubiquitous in our lives, the communities and the societies we participate in. Recently, the emergence of online social networks has triggered a major milestone in our interaction with our social circles. Online social networks have dramatically changed our social interactions and the way we seek information in the digital, interconnected world. Online users can interact with their family, their friends, or other users almost instantaneously, share their opinions and beliefs, and comment or react to other users' content. For this reason, online social networks play an increasingly significant role noawdays in both research and commercial applications. Naturally, most leading commercial entities are providing social connectivity services and compete for the users' online time, while researchers study a wide variety of components existing in social networks and online social networks, such as the behavior of users or utilizing the knowledge present in these massive databases to solve real problems.In the context of structural analysis, social networks can be naturally thought as a collection of nodes that represent the entities that participate in them and a collection of links among them that represent their relationships. As a result, the activities performed by online users can also be thought as structural in more than one ways. One natural example would be the decisions of users to connect to others users based on real life social relationships or based on the content they choose to expose themselves to. A significant amount of research focuses on this structural data exclusively, with the most common being the direct friendship network among individuals, as a means of understanding how opinions, beliefs or other content propagates through the network. In addition, this knowledge and understanding can then be utilized in an attempt to solve real world problems that often occur within the context of online social networks. These concepts refer to social network analysis, which is the study of social networks by using graph theory as the underlying mechanism. The aforementioned tasks and problems, however, are sometimes challenging to address as they are based on studying the complex nature of human behavior in the online world.In the work presented in this thesis we use both established and novel structural methodology social network analysis in order to recognize the online behavior of users and utilize the observations in order to attempt to solve problems that commonly arise in online social networks. Our assumption, that is confirmed -to an extent- through our analysis, is that users will behave consistently with their interests, beliefs or tastes. This phenomenon gives rise to patterns and structure to real social networks as users have the tendency to create connections with other users or other entities based on criteria of interest, taste or exposure. Our methods are exclusively structural, i.e. they rely on the links formed in an explicit or implicit network between the relevant entities, which may not be necessarily formed among real users. In summary, our analysis is twofold: (1) structural analysis and (2) based on the expected behavior of users.We focus our applications in problems that commonly arise in online social networks and are of particular interest to the context of study in this thesis: Greece. The first application being discussed is political affinity and, more specifically, applied to the multiparty, complex, political scene of Greece, as imprinted in social media. In this scenario, we apply methods in order to uncover the political affinity of important nodes of interest: the members of the Greek parliament (MPs) and the most popular news media active on social media. This topic is relevant as it is related to fundamental issues in online social networks, such as the reliability or bias in news stories. Another application discussed in this thesis is recommender systems in another area of important in Greece, which is tourism. We attempt to capitalize on the assumption that users will group related points of interest (POIs) together in order to infer the similarities among the POIs and power a recommendation system based on these similarities. Finally, we also study the preferential attachment mechanism, a fundamental mechanism that can explain certain properties of real social networks with respect to the decision of nodes to connect to other nodes. Here, the preferential attachment mechanism is studied in relation to the random sampling problem and a strictly correct and efficient implementation of the mechanism is developed as a growing random graph generator.We have managed to utilize structural data from online social networks in order to extract useful knowledge using social network analysis methods. The knowledge is originating from the simple observation that the behavior of online users is consistent with their interests and beliefs, a phenomenon that creates structural patterns in the network. Our multi-perspective evaluations throughout this thesis supports this assumption. In particular, for the application of political affinity extraction, we managed to classify the vertices to their known political parties with surprising accuracy and arranged them into the left to right political axis using the minimum linear arrangement problem, whose application is novel in the context of social network analysis. For the case of tourism and the recommender system, we showed that there exists significant useful information in user defined point of interest lists. Our recommendation system achieved high effectiveness with respect to multiple evaluation scenarios and firmly surpassed the popularity baselines that are often considered difficult to exceed. The datasets and supplementary material in these works, such as the surveys, are new. We finally developed an algorithm that imprints the preferential attachment mechanism accurately and efficiently into the Barabási-Albert model and proved both its correctness and asymptotic performance.

Τα μέσα κοινωνικής δικτύωσης κατέχουν κεντρικό ρόλο στη ζωή του σύγχρονου ανθρώπου και συντελούν σε μεγάλο βαθμό στη διαμόρφωση των ατόμων και των ομάδων. Βασικό αντικείμενο έρευνας και μελέτης στον τομέα των κοινωνικών δικτύων αποτελούν οι διεπαφές και διαπροσωπικές σχέσεις μεταξύ των εμπλεκόμενων οντοτήτων (ατόμων, ομάδων ή υποομάδων, οργανισμών ή άλλων μονάδων) σε διάφορα πεδία εφαρμογής (την πολιτική, την οικονομία, τη βιολογία, την κατανομή του πλούτου, τις συναλλαγές, την ψυχολογία, την επιστήμη των υπολογιστών κ.ά.) καθώς και η μελέτη της αμφίδρομης ροής της πληροφορίας ανάμεσα στις οντότητες αυτές. Η ανάλυση κοινωνικών δικτύων (social network analysis) είναι η μελέτη των κοινωνικών δικτύων που πραγματοποιείται μέσα από το γνωστικό αντικείμενο της θεωρίας γράφων (graph theory) καθώς και της θεωρίας δικτύων (network theory), που αποτελούν θεμελιώδη γνωστικά πεδία της επιστήμης δικτύων (network science). Η προσέγγιση αυτή αποσκοπεί στην πληρέστερη κατανόηση αλλά και τη βαθύτερη ερμηνεία των ποικίλων δεσμών, των αλληλεπιδράσεων ή των αμοιβαίων επικοινωνιακών σχέσεων μεταξύ ατόμων ή ομάδων, μια σειρά δηλαδή παραγόντων που με τη σειρά τους διαμορφώνουν και ρυθμίζουν (πέρα και έξω των γενετικών ή περιβαλλοντικών επιρροών) την ατομική συμπεριφορά ή την συλλογική/ομαδική συνείδηση και έκφραση.Η συστηματική μελέτη των κοινωνικών δικτύων που καθιέρωσε την σύγχρονη ανάλυση κοινωνικών δικτύων εμφανίστηκε στα τέλη της δεκαετίας του 1990. Πληθώρα επιστημονικών μελετών αυτή την περίοδο συνέπεσε με την ραγδαία ανάπτυξη του Διαδικτύου καθώς και των υπηρεσιών άμεσης επικοινωνίας που εμφανίστηκαν σε αυτό. Οι συσχετίσεις ανάμεσα στις διασυνδεδεμένες οντότητες του αναδυόμενου ψηφιακού κόσμου ανέδειξαν την ανάπτυξη μεθόδων των δομικών ιδιοτήτων τέτοιων δικτύων αλλά και την κατανόηση των υποκείμενων μηχανισμών που διέπουν τη λειτουργία τους. Πολλά από τα θεμελιώδη είδη δικτύων που παρατηρούνται στις πραγματικές κοινωνίες των ανθρώπων ή ακόμη και στη φύση, όπως τα δίκτυα scale-free ή τα δίκτυα small world, μελετήθηκαν τη συγκεκριμένη περίοδο.Το πιο πρόσφατο ορόσημο των κοινωνικών δικτύων και της ανάλυσής τους σημειώθηκε με την μετάβαση του πεδίου στα διαδικτυακά κοινωνικά δίκτυα (online social networks). Η εμφάνιση των διαδικτυακών κοινωνικών δικτύων δεν άλλαξε μόνο την ποσότητα και ποιότητα της διαθέσιμης πληροφορίας αλλά και επηρέασε σε μεγάλο βαθμό την διαδραστικότητα των χρηστών με αυτές τις πλατφόρμες. Δισεκατομμύρια χρήστες καθημερινά ενασχολούνται με το περιεχόμενο διαφόρων υπηρεσιών κοινωνικής δικτύωσης, παράγουν χρήσιμη γνώση ενεργώντας με βάση τις προτιμήσεις τους, και αναζητώντας νέες πληροφορίες σχετικές με την παρουσία τους στην πλατφόρμα. Η διείσδυση τέτοιων κοινωνικών δικτύων στη ζωή μας είναι τόσο έντονη που η έννοια του κοινωνικού δικτύου είναι συχνά συνυφασμένη με τις διασυνδεδεμένες πλατφόρμες κοινωνικής δικτύωσης. Καθώς τα κοινωνικά δίκτυα έχουν δισεκατομμύρια ενεργούς χρήστες, τόσο οι επιπτώσεις αλλά και οι προοπτικές της χρήσης μιας τόσο πλούσιας δεξαμενής πληροφοριών είναι πολύπλευρες και εκτεταμένες.Στην έρευνα που έχει διαξαχθεί στα πλαίσια αυτής της διατριβής, προσανατολιζόμαστε στην εξόρυξη χρήσιμης πληροφορίας και γνώσης από διαδικτυακά μέσα κοινωνικής δικτύωσης και την εκμεταλλευόμαστε για να λύσουμε προβλήματα που συχνά συναντώνται όταν οι χρήστες αναζητούν πληροφορίες σε αυτά. Η ανάλυσή μας περιβάλλεται από δύο βασικές ιδιότητες:α. Βασίζεται σε μεθόδους που είναι καθαρά δομικές, δηλαδή εφαρμόζονται αποκλειστικά στην αναπαράσταση του δικτύου ως ένα σύνολο από κορυφές και ακμές.β. Βασίζεται στην υπόθεση ότι οι διαδικτυακοί χρήστες παίρνουν αποφάσεις και ενεργούν με βάση την προσωπικότητά τους (τα ενδιαφέροντα και τις προτιμήσεις τους).Συγκεκριμένα, εξετάζουμε εφαρμογές κοινωνικών φαινομένων που αφορούν την πολιτική και τον τουρισμό ως περιπτώσεις χρήσης. Επιπρόσθετα, επιχειρούμε να παρουσιάσουμε ένα γενικό θεωρητικό μοντέλο περιγραφής της δημιουργίας δικτύων που μπορεί εν δυνάμει να εξηγήσει ορισμένες από τις ιδιότητες των κοινωνικών δικτύων που αφορούν στην τάση των χρηστών να προσεγγίζουν συγκεκριμένους άλλους χρήστες στα δίκτυα αυτά.Η εμφάνιση των διαδικτυακών κοινωνικών μέσων άλλαξε δραματικά τον τρόπο με τον οποίο οι άνθρωποι επικοινωνούν και αλληλεπιδρούν. Τα κοινωνικά μέσα καθιέρωσαν ένα περιβάλλον στο οποίο η πρόσβαση και επαφή των χρηστών με την πλατφόρμα καθίσταται τετριμμένη με τη χρήση μοντέρνων διασυνδεδεμένων συσκευών. Επιπρόσθετα, οι πλατφόρμες κοινωνικής δικτύωσης εξελίσσονται διαρκώς με προσθήκες λειτουργιών, όπως μοίρασμα φωτογραφιών, τοποθέτηση ετικετών (tagging), πρόταση συστάσεων (recommendation) και άλλα. Στα κοινωνικά μέσα, οι χρήστες που συμμετέχουν παράγουν καθημερινά μεγάλη ποσότητα πληροφορίας. Η παραγωγή αυτή είναι συχνά διάφανη στους χρήστες οι οποίοι, μέσα από τις ενέργειές τους, συνεισφέρουν σε μια τεράστια δεξαμενή πληροφοριών που είναι συσχετισμένη με τις προτιμήσεις και τα ενδιαφέροντά τους. Ο ισχυρισμός μας είναι ότι η δομική συνιστώσα που εμπεριέχεται σε αυτή την πληροφορία πηγάζει από τα κίνητρα που δίνονται στους χρήστες για τη συμμετοχή τους στο κοινωνικό μέσο και μπορούν να χρησιμοποιηθούν για τη μελέτη μιας εφαρμογής στο κοινωνικό αυτό δίκτυο. Στην έρευνα αυτή, εξετάζουμε δύο σημαντικές περιπτώσεις: γνώση πολιτικού περιεχομένου και συναφής γνώση για τουριστικές εφαρμογές.Τα ζητήματα πολιτικής σημασίας αποτελούν αντικείμενο διαρκούς απασχόλησης ενώ την σύγχρονη εποχή εμφανίζονται συχνά στα κοινωνικά μέσα. Καθώς τα κοινωνικά μέσα συνεχίζουν να κατέχουν κεντρικό ρόλο στις πολιτικές καμπάνιες, φαινόμενα ψευδών ειδήσεων (fake news) ή πολιτικής προκατάληψης (bias) άρχισαν να κάνουν την εμφάνισή τους και να διαδίδονται μέσω κοινωνικών κύκλων στα κοινωνικά μέσα. Η μελέτη τέτοιων φαινομένων κρίνεται ιδιαίτερα σημαντική λόγω του αντίκτυπου που έχουν στην κοινωνική πόλωση καθώς και στους θεμελιώδεις μηχανισμούς της δημοκρατίας. Κρίνεται συνεπώς σημαντική η αυτόματη εξαγωγή πολιτικής πληροφορίας σχετικής με συγκεκριμένους κόμβους ενδιαφέροντος υψηλής κεντρικότητας σε ένα δίκτυο, όπως για παράδειγμα ο πολιτικός τους προσανατολισμός ή η τάση τους να παράγουν ψευδές ή προκατειλημένo περιεχόμενο. Χρησιμοποιώντας όμως τη συμπεριφορά και τις ενέργειες των ιδίων για τον αυτόματο εντοπισμό αυτής της πληροφορίας ίσως είναι πιο απαιτητικό να επιτευχθεί καθώς οι χρήστες έχουν τη δυνατότητα να προσαρμόσουν τη συμπεριφορά τους για να αποφύγουν μία τέτοια ενέργεια. Ο ισχυρισμός μας είναι ότι συχνά είναι πιο αξιόπιστος ο εντοπισμός του πολιτικού προσανατολισμού ενός χρήστη μέσω των συνδέσεών του με άλλους χρήστες. Συγκεκριμένα, χρησιμοποιούμε τους συνδέσμους που σχηματίζονται από άλλους χρήστες προς τους χρήστες ενδιαφέροντος, οι οποίοι μπορεί να μην είναι αμοιβαίοι. Με αυτόν τον τρόπο, ο πολιτικός προσανατολισμός των χρηστών ενδιαφέροντος εντοπίζεται με βάση τη συλλογική τους εικόνα στο δικτύου, και όχι μόνο με βάση του ατομικού τους προφίλ.Μια ακόμη ενδιαφέρουσα εφαρμογή ανάλυσης κοινωνικών δικτύων που είναι μέρος αυτής της διατριβής είναι τα συστήματα προσωποποιημένων συστάσεων (recommender systems) στα κοινωνικά μέσα που ειδικεύονται στον τουρισμό: τα τουριστικά κοινωνικά μέσα. Σε αυτή την περίπτωση, η υπόθεσή μας είναι πως η συμπεριφορά των χρηστών του κοινωνικού μέσου θα είναι συνεπείς με τις προτιμήσεις και τα ενδιαφέροντά τους. Ένας φυσικός τρόπος για υπόδειξη προσωποποιημένων συστάσεων είναι η εκμετάλλευση της εγγενούς πληροφορίας στα προφίλ των χρηστών που συμμετέχουν ενεργά στο κοινωνικό μέσο και προέρχονται από τις ενέργειες των ίδιων. Οι μέθοδοί μας χρησιμοποιούν δημόσιες συλλογές αντικειμένων που βασίζονται στο ότι οι χρήστες συχνά επιθυμούν να επισκέπτονται περισσότερους προορισμούς από ότι πραγματικά επισκέπτονται. Βασιζόμενοι σε αυτή την ιδιότητα, επιχειρούμε να εντοπίσουμε τις ομοιότητες ανάμεσα στις τοποθεσίες, έτσι όπως αυτή είναι αποτυπωμένη από τους χρήστες του κοινωνικού μέσου.Το τελευταίο μέρος της διατριβής είναι ένα θεωρητικό μοντέλο δημιουργίας γράφων που παρουσιάζει ομοιότητες με διαδικασίες που εμφανίζονται σε πραγματικά κοινωνικά, ή μη-κοινωνικά, δίκτυα, όπως βιολογικά δίκτυα ή δίκτυα υπολογιστών. Πιο συγκεκριμένα, η ιδιότητα αυτή αναφέρεται στα scale-free δίκτυα, δηλαδή τα δίκτυα των οποίων η κατανομή των βαθμών ακολουθεί κατανομή νόμου δύναμης (power law). Υπάρχουσες μελέτες στην βιβλιογραφία δείχνουν ότι η τωρινή κατάσταση στον χώρο δεν περιγράφει κάποιο μοντέλο που να είναι ακριβές σε σχέση με το πιθανοκρατικό μοντέλο που χρησιμοποιείται αλλά καλές προσεγγίσεις αυτού. Για τον λόγο αυτό, παρουσιάζουμε ένα μοντέλο που υλοποιεί επακριβώς τον εγγενή μηχανισμό της δημιουργίας του δικτύου χωρίς να περιορίζουμε τον χρόνο εκτέλεσης της διαδικασίας.Η ανάλυση που γίνεται στα πλαίσια της διατριβής αυτής βασίζεται σε μεθόδους που είναι αποκλειστικά δομικές, δηλαδή χρησιμοποιούν ως πρωτογενή πληροφορία μόνο δομικά χαρακτηριστικά του κοινωνικού δικτύου. Πιο συγκεκριμένα, η δομή ενός κοινωνικού δικτύου ορίζεται ως ένα σύνολο κόμβων που χαρακτηρίζουν τις οντότητες που συμμετέχουν στο κοινωνικό δίκτυο, και ένα σύνολο από ακμές που αντιπροσωπεύουν τις σχέσεις ανάμεσα στους κόμβους. Η ανάλυσή μας βασίζεται αποκλειστικά σε αυτό το είδος πληροφορίας και δεν λαμβάνεται υπόψη άλλος τύπος γνώσης σχετικός με τους κόμβους του δικτύου ή τις σχέσεις ανάμεσά τους. Επιπρόσθετα, οι μέθοδοι που χρησιμοποιούμε συνήθως μεταχειρίζονται τις ακμές ως δυαδικές σχέσεις ύπαρξης ή απουσίας σχέσης ενώ οι κόμβοι χαρακτηρίζονται με ένα αναγνωριστικό (ID) χωρίς φυσική ερμηνεία ή αξία. Υπό αυτό το πρίσμα, η ανάλυση κοινωνικών δικτύων θεωρείται το κύριο αντικείμενο αυτής της διατριβής σε ό,τι αφορά τη μεθοδολογία. Στην έρευνά μας χρησιμοποιούμε τόσο καθιερωμένες μεθόδους ανάλυσης του χώρου για την εξόρυξη της απαιτούμενης πληροφορίας από το δίκτυο όσο και καινοτόμες μεθόδους που δεν έχουν εφαρμοστεί στα κοινωνικά μέσα, και μελετάμε τη φυσική ερμηνεία της εφαρμογής τους.Η συχνότερη, καθιερωμένη στη βιβλιογραφία, μέθοδος που χρησιμοποιείται στην ανάλυσή μας είναι η μέθοδος graph projection, που αποτελεί έναν μετασχηματισμό του γράφου που μπορεί να συλλάβει ως ένα βαθμό τις σχέσεις ανάμεσα σε ζευγάρια κόμβων του γράφου, οι οποίες δεν μπορούν να αποτυπωθούν με τη χρήση των άμεσων σχέσεων στον αρχικό γράφο. Οι μέθοδοι graph projections απλοποιούν ένα δίκτυο, χωρίς να περιορίζουν σημαντικά την πληροφορία που υπάρχει σε αυτό, και κατευθύνουν την ανάλυση σε μια συγκεκριμένη επιλεγμένη ομάδα κόμβων. Άλλες μέθοδοι ανάλυσης κοινωνικών δικτύων αποτελούν οι τυχαία περίπατοι (random walks), η συσταδοποίηση κόμβων (community detection), ή άλλες μέθοδοι σημασιολογικής περιγραφής των οντοτήτων που συμμετέχουν στο δίκτυο. Σε αρκετές περιπτώσεις, η έρευνά μας περιλαμβάνει συγκριτική παρουσίαση αυτών των μεθόδων και των παραμέτρων τους. Τέλος, χρησιμοποιούμε μεθόδους αλγοριθμικής ανάλυσης δικτύων για καινοτόμα εφαρμογή στα κοινωνικά μέσα και δείχνουμε την καταλληλότητά τους ως προς την ανάδειξη της φυσικής ερμηνείας της πρωτογενούς πληροφορίας που υπάρχει στο δίκτυο.Η μεθοδολογία μας εφαρμόζεται σε πρωτογενή δεδομένα από τα κοινωνικά δίκτυα του Twitter και Foursquare. Τα δεδομένα που υπάρχουν και στις δύο αυτές υπηρεσίες ταιριάζουν απόλυτα με τα κίνητρα και τους στόχους μας καθώς και με την περιγραφή των προβλημάτων που επιχειρούμε να δώσουμε λύση σε αυτή την έρευνα. Το Twitter συχνά αντιμετωπίζεται ως ένα κοινωνικό μέσο με έντονη την παρουσία της πολιτικής συνιστώσας και αποτελείται από ένα πλούσιο σύνολο ενεργών χρηστών, όπως πολιτικοί, αντιπρόσωποι κομμάτων, υποψήφιοι, ή ακόμη και μέσα ενημέρωσης. Χρησιμοποιώντας ανάλυση κοινωνικών δικτύων, δείχνουμε την καταλληλότητα του Twitter για την ανάλυση φαινομένων πολιτικής προκατάληψης. Από την άλλη μεριά, το Foursquare είναι μια πλατφόρμα τουριστικού βοηθού και δεδομένων τοποθεσίας με περίπου 50 εκατομμύρια χρήστες. Οι χρήστες αλληλεπιδρούν με άλλους χρήστες ή με σημεία ενδιαφέροντος, χαρακτηριστικό του Foursquare που το κάνει ιδανικό για τη μελέτη προσωποποιημένων συστάσεων σημείων ενδιαφέροντος. Και τα δύο κοινωνικά μέσα αποτελούνται από ένα μεγάλο αριθμό χρηστών που έχουν κίνητρα να συμπεριφέρονται με συγκεκριμένο τρόπο, να παίρνουν αποφάσεις και να ενεργούν με βάση τις προτιμήσεις, τα ενδιαφέροντα και τις πεποιθήσεις τους. Στην έρευνα αυτή, επιχειρούμε να εκμεταλλευτούμε αυτό το φαινόμενο, συναθροίζοντας τις συμπεριφορές πολλαπλών χρηστών για την παραγωγή γνώσης επί τους αντικειμένου της μελέτης. Η ιδιότητα αυτή είναι βασισμένη στο γεγονός ότι οι χρήστες συχνά επιλέγουν να εκθέτουν τον εαυτό τους σε πληροφορίες που είναι σχετικές με τις προτιμήσεις τους ή ενδυναμώνουν τις απόψεις τους.Τέλος, παρουσιάζουμε μία αλγοριθμική προσέγγιση δημιουργίας κοινωνικού γράφου που επιχειρεί να εξηγήσει μία από τις θεμελιώδεις ιδιότητες πάνω στην οποία βασίζεται η δημιουργία σχέσεων σε κοινωνικά ή ακόμη και μη-κοινωνικά δίκτυα στον πραγματικό κόσμο. Η ιδιότητα αυτή αναφέρεται ως ο μηχανισμός του preferential attachment, σύμφωνα με τον οποίο οι κόμβοι που εισέρχονται στο δίκτυο συνήθως συνδέονται με παλαιότερους κόμβους που έχουν ήδη υψηλή συνδεσιμότητα. Οι αλγόριθμοι που προτείνουμε είναι αναλυτικές μέθοδοι αποδοτικής εκτέλεσης που συμπεριλαμβάνουν αυτή τη διάσταση της αλληλεπίδρασης μεταξύ των χρηστών.