Unit:
Κατεύθυνση Ηλεκτρονικός Αυτοματισμός (Η/Α, με πρόσθετη εξειδίκευση στην Πληροφορική και στα πληροφοριακά συστήματα)Library of the School of Science
Author:
Tourgelis-Provatas Orestis
Supervisors info:
Παναγιώτης Σταματόπουλος, Επίκουρος Καθηγητής , Τμήμα Πληροφορικής και Τηλεπικοινωνιών, Εθνικό και Καποδιστριακό Πανεπιστήμιο Αθηνών
Ευστάθιος Χατζηευθυμιάδης, Καθηγητής, Τμήμα Πληροφορικής και Τηλεπικοινωνιών, Εθνικό και Καποδιστριακό Πανεπιστήμιο Αθηνών
Ιωάννης Κοτρώνης, Αναπληρωτής Καθηγητής, Τμήμα Πληροφορικής και Τηλεπικοινωνιών, Εθνικό και Καποδιστριακό Πανεπιστήμιο Αθηνών
Original Title:
Influence in social networks
Translated title:
Influence in social networks
Summary:
In this thesis we explored two main problems regarding influence in social networks. The one is the influence maximization problem and the main approximation algorithms that can be found throughout literature. In the same context we also present two different models for the information/in- fluence diffusion in the social networks Independent Cascade and Linear Threshold models. Under both of these models the influence function re- mains submodular which ensures the approximation efficiency of the greedy algorithm. We provide a robust python implementation for aforementioned models, the greedy algorithm, as well as an optimized version (lazy-greedy) which exploits the submodular property of the influence function to reduce computation steps.
The second problem regarding influence, is how we can learn these influ- ence probabilities that we take for granted in the first problem, in a real social network. We proceed in the implementation of the algorithms proposed in the literature which we use to calculate the influence probabilities and eval- uate the accuracy of the various proposed models. We have implemented minor modifications to the algorithms to adapt them to a directed network instead of the undirected initial implementation. We also create a ruby gem to parse github archive events into mysql tables, digestible from the learning and evaluating algorithms, producing a new social network dataset.
Running the learning algorithms over the action logs of both digg and github social networks we managed to confirm the findings in literature regarding the predictability of the proposed models. We did not detect any improvement though using time conscious models, which are a lot more expensive computationally compared to the static models. We found a minor improvement in the digg social network when restricting our evaluation only on users with influenceability above a certain threshold, a finding that is not reproducible on github dataset.
We proposed a novice approach in calculating influence probabilities by distinguishing the effect of different types of actions. The new model did not exhibit any improvement in roc curves but there was a significant improve- ment in precision recall curves which might be a better evaluation method for this specific problem due to the fact that our dataset is unbalanced.
Main subject category:
Science
Keywords:
Social networks, influence diffusion model, influence maximization
