Τεχνικές αναλύσης κοινωνικών δικτύων, με έμφαση σε γράφους εμπιστοσύνης

Abstract

This PhD thesis presents novel techniques in the domain of social network analysis, by putting more emphasis on networks in which users can express trust or distrust on each other. Mining such networks is an interesting problem with a variety of application domains like the analysis of international relationships and the detection of user communities. The first three chapters examine the sign prediction problem by borrowing techniques from three different domains. At first, we employed standard , well-defined measures from the field of Social Network Analysis to study the propagation patterns of the positive and negative opinions in the social graph. Then, we adapted state of the art techniques from the domain of Biostatistics in order to perform microscopic network analysis of large social networks. Next, we investigated the possibility to reconstruct a social trust graph by exploiting external data such as the ratings of the users for certain items, using algorithms from the domain of deep learning. Finally, the last chapter presents a community detection algorithm based on recent advances in Natural Language Processing. The sequence of the chapters depicts the chronological order of the experiments. I tried to minimize the dependencies among the chapters in order to facilitate the interested reader.

Η παρούσα διατριβή προτείνει τεχνικές για την ανάλυση κοινωνικών δικτύων δίνοντας ιδιαίτερη έμφαση σε δίκτυα στα οποία οι χρήστες μπορούν να εκφράζουν εμπιστοσύνη ή δυσπιστία μεταξύ τους. Η ανάλυση τέτοιων γράφων εμπιστοσύνης είναι ένα ενδιαφέρον πρόβλημα με ευρύ φάσμα εφαρμογών όπως η ανάλυση γεωπολιτικών σχέσεων και η εύρεση κοινοτήτων χρηστών. Στα πρώτα τρία κεφάλαια εξετάζεται το πρόβλημα της πρόβλεψης της προδιάθεσης ενός χρήστη για έναν άλλο, αντλώντας τεχνικές από τρεις διαφορετικούς τομείς. Αρχικά, χρησιμοποιούνται κλασικές και διαδεδομένες τεχνικές από τον χώρο της Ανάλυσης Κοινωνικών Δικτύων (Social Network Analysis) με σκοπό να ερευνηθούν οι μηχανισμοί διάδοσης θετικών και αρνητικών απόψεων στο δίκτυο. Έπειτα, ενσωματώνουμε τεχνικές από τον τομέα της Βιοστατιστικής, ώστε να αναλύσουμε μεγάλα κοινωνικά δίκτυα από μικροσκοπική σκοπιά. Στη συνέχεια, με χρήση τεχνικών deep learning δείχνουμε πως είναι δυνατόν να "κατασκευαστεί" ένας γράφος εμπιστοσύνης αξιοποιώντας δεδομένα φαινομενικά άσχετα με αυτόν τον σκοπό, όπως οι κριτικές των χρηστών για διάφορα προϊόντα. Στο τελευταίο κεφάλαιο, παρουσιάζουμε έναν αλγόριθμο εύρεσης κοινοτήτων σε κοινωνικά δίκτυα, βασιζόμενοι σε πρόσφατες προόδους στον τομέα της Ανάλυσης Φυσικής Γλώσσας (Natural Language Processing). Η σειρά των κεφαλαίων αποτυπώνει την χρονική σειρά των πειραμάτων που εφάρμοσα αλλά κάθε κεφάλαιο είναι γραμμένο ώστε να μην έχει σημαντικές συσχετίσεις με τα προηγούμενα και έτσι να μπορεί να διαβαστεί αυτόνομα