Social network analysis is an important cross-disciplinary area of research, with applications in fields such as biology, epidemiology, marketing and even politics. Influence maximization is the problem of finding the set of seed nodes in an information diffusion process that guarantees maximum spread of influence in a social network, given its structure. Most approaches to this problem make two assumptions. First, the global structure of the network is known. Second, influence probabilities between any two nodes are known beforehand, which is rarely the case in practical settings. In this thesis we propose a different approach to the problem of learning those influence probabilities from past data, using only the local structure of the social network. The method is grounded in unsupervised machine learning techniques and is based on a form of hierarchical clustering, allowing us to distinguish between influential and the influenceable nodes. Finally, we provide empirical results using real data extracted from Facebook. / L'analyse des réseaux sociaux est un domaine d'études interdisciplinaires qui comprend des applications en biologie, épidémiologie, marketing et même politique. La maximisation de l'influence représente un problème où l'on doit trouver l'ensemble des noeuds de semence dans un processus de diffusion de l'information qui en même temps garantit le maximum de propagation de son influence dans un réseau social avec une structure connue. La plupart des approches à ce genre de problème font appel à deux hypothèses. Premièrement, la structure générale du réseau social est connue. Deuxièmement, les probabilités des influences entre deux noeuds sont connues à l'avance, fait qui n'est d'ailleurs pas valide dans des circonstances pratiques. Dans cette thèse, on propose un procédé différent visant la problème de l'apprentissage de ces probabilités d'influence à partir des données passées, en utilisant seulement la structure locale du réseau social. Le procédé se base sur l'apprentissage automatique sans surveillance et il est relié à une forme de regroupement hiérarchique, ce qui nous permet de faire la distinction entre les noeuds influenceurs et les noeuds influencés. Finalement, on fournit des résultats empiriques en utilisant des données réelles extraites du réseau social Facebook.
| Identifer | oai:union.ndltd.org:LACETR/oai:collectionscanada.gc.ca:QMM.114597 |
| Date | January 2013 |
| Creators | Bordianu, Gheorghita |
| Contributors | Doina Precup (Internal/Supervisor) |
| Publisher | McGill University |
| Source Sets | Library and Archives Canada ETDs Repository / Centre d'archives des thèses électroniques de Bibliothèque et Archives Canada |
| Language | English |
| Detected Language | French |
| Type | Electronic Thesis or Dissertation |
| Format | application/pdf |
| Coverage | Master of Science (School of Computer Science) |
| Rights | All items in eScholarship@McGill are protected by copyright with all rights reserved unless otherwise indicated. |
| Relation | Electronically-submitted theses. |
Page generated in 0.0018 seconds