A social network is rich source of information about relationships between individuals, groups organizations or even entire societies and other entities. These relationships, that describe in fact, the social structure among the members-nodes of the network, can be represented and studied using graphs. In certain networks, the relationships between two different classes of objects, appear in the form of a bipartite graph. Bipartite graphs that are often studied as separate graph category. A practical example of a bipartite graph, is the subgraph of the social networking media Twitter, formed by a Set of nodes A and its respective Set B, comprising the followers of the nodes of A. Thus, Set A are the followees and Set B are the followers while the edges formed among them represent the follower relations from the elements of Set B to those of Set A. Another example of bipartite graph is the network formed between users-reviewers and products in the online retailer Amazon. An interesting question that arises is, given a bipartite graph of users and the products that they review, or followers and followees of a social media network, how can we detect patterned or even fake reviews, or groups of such an online network? In this thesis, we apply graph theoretic techniques for data analysis of social media. To that end, some popular software tools are used, for example the NetworkX python library or the Gephi software for analysis and visualization of graphs, both of which can be used in such analyses. These tools are pilot applied on networks of two popular internet based platforms; a) Twitter, the well known online news and social networking service, in particular two Twitter subgraphs defined by the accounts of Greece's most popular news sites, as well as Greek politicians and b) two graphs of users and product reviews on Amazon, the largest internet based retailer and cloud computing company in the united States. The Twitter datasets comprise the 22 news sites, and the 891,301 users who follow those sites, and the 171 politicians along with their 726,176 followers. The relations among them are exploited in order to form clusters of the sites and users, as well as an attepmt is made to reveal the sites' political affiliation, based on their followers. This procedure, also called community detection, is applied using several concepts and algorithms, including graph projection methods, the Jaccard similarity, a modularity optimization algorithm, an approach to the MinLA problem and a force based visualization algorithm, Gephi's Force Atlas 2. The data from Amazon reviews consists of two specific product categories, “musical instruments” and “digital music”, containing 500,176 and 836,006 reviews respectively. The patterned reviews detection issue is approached via heuristic methods, as no ground truth is available for the datasets. Thus, the graph theoretic methods that are applied on those networks, aim in uncovering any structural patterns and possible political affiliations for the news sites as well as strategic behavior of Amazon reviewers product categories. Certain procedures are presented for both of those goals, patterned and novel ones, the results of which are evaluated and discussed thoroughly. The main contributions of this work are: • Usage of the ELKI and Graphviz software tools in experimental level; application of the already implemented clustering algorithms on sample graphs, developed for the needs of learning these tools. The procedure includes data editing, file conversion, visualization and result evaluation. • Analysis of Amazon reviewer-product bipartite graphs. Statistical data extracted and suspicious reviewer behaviors are uncovered via heuristic method application, which are then evaluated via additional analysis and cross-dataset comparison. The methods are implemented as Python scripts, developed for the needs of this thesis. • Application of the Graph Projection method, Jaccard Similarity as well as the Louvainand Girvan-Newman clustering algorithms in Python environment, using the NetworkX Library. Experiments performed on Twitter subgraphs, in order to extract statistical data and analyze their community structure. • Usage of the Gephi software tool for graph visualization, application of a modularity clustering algorithm and data analysis, in order to visualize the Twitter accounts as clusters/communities. • Exploit the results of the modularity algorithm and use a heuristic method in order to place the news sites onto a straight line, based on their pairwise similarity. • Application of a linear arrangement algorithm on the nodes of a social graph derived from the Twitter network, using a version of the Jaccard Similarity as measurement. Evaluation of the information revealed by the linear arrangement for certain nodes.
Βιβλιογραφία: σ. 63-65
65 σ.
Ένα κοινωνικό δίκτυο αποτελεί μια εξαιρετική πηγή πληροφοριών σχετικά με τις σχέσεις ανάμεσα σε άτομα, ομάδες, και άλλες οντότητες. Οι σχέσεις αυτές που ουσιαστικά περιγράφουν μια κοινωνική δομή μεταξύ των μελών κόμβων του δικτύου, μπορούν να αναπαρασταθούν και να μελετηθούν γραφοθεωρητικά με την χρήση γράφων. Συχνά, κατά την μοντελοποίηση του δικτύου, οι σχέσεις μεταξύ δύο διακριτών ομάδων κόμβων, έχουν τη μορφή διμερούς γράφου. Οι διμερείς γράφοι συχνά μελετώνται ως ξεχωριστή κατηγορία γράφων. Ένα πρακτικό παράδειγμα διμερούς γράφου είναι το υποδίκτυο του μέσου κοινωνικής δικτύωσης Twitter που σχηματίζεται από ένα σύνολο κόμβων Α και το αντίστοιχο σύνολο Β με όλους τους followers των κόμβων του Α. Το σύνολο Α είναι “followees”, το σύνολο Β οι “followers” και οι ακμές του γράφου είναι σχέσεις follower από στοιχεία του συνόλου Β προς το σύνολο Α. Άλλο παράδειγμα διμερούς γράφου είναι το δίκτυο μεταξύ χρηστών-κριτών και προϊόντων στο ηλεκτρονικό κατάστημα Amazon. Ένα ενδιαφέρον ερώτημα που προκύπτει είναι, δεδομένου τους διμερούς γράφου ενός μέσου κοινωνικής δικτύωσης, πώς θα μπορούσαν να εντοπιστούν “τυποποιημένες” ή ακόμη και “ψευδής” κριτικές, ή οργανωμένες ομάδες χρηστών αυτών των μέσων δικτύωσης; Στη παρούσα διατριβή, εφαρμόζουμε γραφοθεωρητικές τεχνικές για την ανάλυση δεδομένων από δίκτυα κοινωνικής δικτύωσης. Για το σκοπό δοκιμάζουμε ορισμένα από τα δημοφιλή εργαλεία λογισμικού, για παράδειγμα η βιβλιοθήκη NetworkX σε περιβάλλον python ή η εφαρμογή Gephi για απεικόνιση και ανάλυση γράφων, τα οποία μπορούν να χρησιμοποιηθούν στα πλαίσια τέτοιων αναλύσεων. Τα παραπάνω εργαλεία εφαρμόζονται πιλοτικά στα δίκτυα δύο ευρέως διαδεδομένων διαδικτυακών εφαρμογών, α) το Twitter, τη πασίγνωστη υπηρεσία ενημέρωσης και κοινωνικής δικτύωσης, συγκεκριμένα ένα μέρος του δικτύου του Twitter οριζόμενο από τους λογαριασμούς των δημοφιλέστερων ελληνικών ηλεκτρονικών εφημερίδων, καθώς και ένα μέρος οριζόμενο από λογαριασμούς Ελλήνων πολιτικών και επιπλέον β) ένα δίκτυο χρηστών και κριτικών προϊόντων στο Amazon, την μεγαλύτερη διαδικτυακή εταιρία πώλησης προϊόντων και “cloud computing” της Αμερικής. Τα δεδομένα από το Twitter αποτελούνται αφενός, από 22 ειδησεογραφικές σελίδες και τους 891.301 “followers” τους και αφετέρου από 171 λογαριασμούς πολιτικών και τους 726.176 “followers” τους. Εκμεταλλευόμενοι τις σχέσεις μεταξύ τους, δημιουργούνται ομάδες (“clusters”) από σελίδες και χρήστες, ενώ γίνεται και μια προσπάθεια αποκάλυψης των πολιτικών πεποιθήσεων των ιστοσελίδων, βασισμένη στους “followers” τους. Εφαρμόζουμε μια διαδικασία “εύρεσης κοινοτήτων”, που στη συγκεκριμένη περίπτωση περιλαμβάνει μεθόδους “προβολής γράφου”, τον δείκτη ομοιότητας κατά Jaccard, έναν αλγόριθμο βελτιστοποίησης του “modularity”, και τον αλγόριθμο απεικόνισης “Force Atlas 2” της εφαρμογής “Gephi”. Τα δεδομένα από το Amazon αποτελούνται από δύο συγκεκριμένες κατηγορίες, τις “musical instruments” και “digital music”, με την καθεμία να περιέχει 500,176 και 836,006 κριτικές προϊόντων αντίστοιχα. Το ζήτημα εντοπισμού “τυποποιημένων” κριτικών προσεγγίζεται μέσω “ευρετικών” μεθόδων, καθώς για τα συγκεκριμένα σετ δεδομένων, δεν υπάρχει το “ground truth”. Εφαρμόζονται έτσι, γραφοθεωρητικές μέθοδοι σε αυτά τα δίκτυα, που σαν στόχο έχουν την αποκάλυψη “τυποποιημένων” δομών και τυχόν πολιτικών προτιμήσεων, όσον αφορά στους ειδησεογραφικούς ιστότοπους, καθώς και την ανεύρεση “στρατηγικών” συμπεριφορών κριτών στις παραπάνω κατηγορίες προϊόντων του Amazon. Παρουσιάζονται οι διαδικασίες που ακολουθήθηκαν προς επίτευξη αυτών των στόχων και τα αποτελέσματά τους περιγράφονται και αξιολογούνται διεξοδικά. Τα κυριότερες συνεισφορές αυτής της εργασίας είναι: • Χρησιμοποίηση των εφαρμογών ELKI και Graphviz σε πειραματικό επίπεδο. Εφαρμογή των ήδη υλοποιημένων στο ELKI αλγορίθμων clustering σε δείγματα γράφων, τα οποία αναπτύχθηκαν για τις ανάγκες εκμάθησης αυτών των εργαλείων. Η διαδικασία περιλαμβάνει την επεξεργασία δεδομένων, τις απαραίτητες μετατροπές αρχείων, καθώς και την απεικόνιση και αξιολόγηση των αποτελεσμάτων. • Ανάλυση των δεδομένων των διμερών γράφων χρηστών-κριτών και προϊόντων του Amazon. Εξήχθησαν στατιστικά δεδομένα και εντοπίστηκαν “ύποπτες” συμπεριφορές κριτών, μέσω εφαρμογής ευρετικών μεθόδων, τα αποτελέσματα των οποίων στη συνέχεια αξιολογούνται μέσω περεταίρω ανάλυσης και σύγκρισης ανάμεσα σε διαφορετικά σύνολα δεδομένων. Οι μέθοδοι εφαρμόστηκαν μέσω scripts της γλώσσας προγραμματισμού Python, που αναπτύχθηκαν για τις ανάγκες της εργασίας. • Εφαρμογή μιας μεθόδου Graph Projection, του δείκτη ομοιότητας κατά Jaccard, καθώς επίσης και των αλγορίθμων συσταδοποίησης, Luvain και Girvan-Newman σε περιβάλλον Python, με χρήση της βιβλιοθήκης NetworkX. Τα πειράματα πραγματοποιήθηκαν σε τμήματα γράφων του Twitter, με σκοπό την εξαγωγή στατιστικών δεδομένων και την ανάλυση των κοινωνικών τους δομών. • Χρησιμοποίηση του εργαλείου Gephi για την απεικόνιση γράφων, εφαρμογή ενός αλγόριθμου modularity, καθώς και για την ανάλυση των δεδομένων που προκύπτουν από αυτό, με σκοπό την απεικόνιση των λογαριασμών του Twitter σε ομάδες/κοινότητες. • Εκμετάλλευση των αποτελεσμάτων του αλγόριθμου modularity και χρήση μιας ευρετικής μεθόδου για την τοποθέτηση των ειδησεογραφικών σελίδων σε μία ευθεία γραμμή, βάση την ομοιότητά τους ανά δύο. • Εφαρμογή ενός αλγορίθμου linear arrangement των κόμβων ενός κοινωνικού γράφου από το δίκτυο του Twitter, στο δίκτυο του twitter, χρησιμοποιώντας την ομοιότητα κατά Jaccard ως μετρική. Αξιολόγηση της πληροφορίας που αποκαλύπτει το linear arrangement για τους συγκεκριμένους κόμβους.
Δημοκρίτειο Πανεπιστήμιο Θράκης
