Maximisation d'influence dans les réseaux sociaux
Institution:
Aix-MarseilleDisciplines:
Directors:
Abstract EN:
In recent years, a large number of social network sites have appeared to connect people and groups together. Networks have been proven to be a good tool to share information and communicate ideas. Influence propagation occurs when an individual’s opinions or behaviors change as a result of interactions with others. The influence maximization problem aims to identify a subset of initial adopters in a social network to maximize the influence propagation. There are two progressive models most used in the analysis of social networks, namely the independent cascade model and the linear threshold model. As a type of epidemic models, the independent cascade model assumes that an individual adopts an innovationwith a certain probability if at least one of its in-neighbors has adopted it. Differently, the linear threshold model assumes that an individual adopts an innovation if a certain ratio of its in-neighbors have already adopted it. The thesis addresses three problems: influence propagation computation, influence maximization by seed selection and influence maximization by link activation. The influence propagation computationconsist in computing the probability that each node can be activated given a certain set of initial adopters. We propose the PathMethod to give an exact result, the SSS-Noself algorithm and the SSS-Bounded-Path algorithm to give an approximate result. The influence maximization by seed selection consist in maximizing the final influence propagation by targeting a seed set of certain cardinality. We initially propose the problem of influence maximization by link activation. Various properties of this problem and some sub-optimal solutions are given
Abstract FR:
Récemment, un grand nombre de sites de réseaux sociaux sont apparus pour relier des personnes et des groupes. Les réseaux sociaux sont des bons outils pour obtenir des informations et communiquer des idées. La propagation de l’influence se produit lorsque les opinions ou les comportements d’un individu changent en conséquence des interactions avec les autres. Le problème de la maximisation de l’influence vise à identifier un sous-ensemble d’adopteurs initiaux dans un réseau social afin de maximiser la propagation de l’influence. Deux modèles progressifs sont principalement utilisés. Le modèle cascade indépendante suppose qu’un individu adopte une innovation avec une certaine probabilité si au moins un de ses voisins l’a adoptée. Le modèle à seuil linéaire suppose qu’un individu adopte une innovation si un certain ratio de ses voisins l’avons déjà adopté. Cette thèse aborde trois problèmes: l’estimation de l’influence, la maximisation de l’influence par la sélection des diffuseurs initiaux, et la maximisation de l’influence par l’activation des liens. L’estimation de l’influence consiste à calculer la probabilité pour que chaque noeud puisse être activé par un certain ensemble de diffuseurs initiaux. Nous proposons la méthode du chemin pour calculer un résultat exact, l’algorithme SSS-Noself et l’algorithme SSS-Bounded-Path pour calculer un résultat approximatif. La maximisation de l’influence par la sélection des diffuseurs initiaux consiste à maximiser l’influence finale obtenue par un certain nombre des ces diffuseurs initiaux. Nous proposons un problème de la maximisation de l’influence par l’activation des liens