Soutenance de thèse de Wenjing YANG

Récemment, un grand nombre de sites de réseaux sociaux (Facebook et LinkedIn, par exemple) ont apparu pour relier les personnes et les groupes. Les réseaux sociaux sont bon outils pour obtenir des informations et communiquer des idées. Influence de la propagation dans les réseaux sociaux a attiré d’intérˆ ets dans les domaines des réseaux complexes, de l’exploration de données et des théories algorithmiques. La propagation d’influence se produit lorsque les opinions ou les comportements d’un individu changent en conséquence des interactions avec les autres. Par exemple, on peut adopter une information ou partager une vidéo sur Facebook sous l’influence de ses connaissances. Un effet viral est enfin déclenché à tout le réseau. C’est appellé “l’effet de bouche à oreille”. Une stratégie marketing qui profite de l’effet est appelé marketing viral. Il est largement appliqué dans les entreprises et en ligne logiciels. 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. Il est un problème algorithmique pour le marketing viral. Deux modèles progressifs sont principalement utilisés dans l’analyse des réseaux sociaux, à savoir le modèle à cascade indépendante et le modèle à seuil linéaire. 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. Autrement, 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é. Nous appliquons le modèle à cascade indépendante dans notre thèse. La thèse aborde trois problèmes différents liés à la maximisation de l’influence dans les réseaux sociaux: l’estimation de l’influence, la maximisation de l’influence par la sélection des semences et la maximisation de l’influence par l’activation des liens. D’abord, l’estimation d’influence consiste à calculer la probabilité que chaque point puisse ˆ etre activé par un certain ensemble d’adoptants initiaux. C’est une étape préliminaire pour la réalisation de la maximisation de l’influence. Nous proposons la méthode du chemin pour donner un résultat exact, l’algorithme SSS-Noself et l’algorithme SSS-Bounded-Path pour donner un résultat approximatif. Deuxièmement, la maximisation de l’influence par la sélection des semences consiste à maximiser l’influence finale obtenue par un certain nombre des semences. Nous combinons nos approches pour l’estimation d’influence avec différentes heuristiques pour la sélection des semences afin d’atteindre l’objectif de maximisation d’influence. Troisièmement, nous proposons initialement le problème de la maximisation de l’influence par l’activation des liens. Il consiste à activer les liens les plus efficaces dans un budget limité pour maximiser l’influence. Diverses propriétés de ce problème et certaines solutions sous-optimales telles que l’algorithme Cost-Degree et l’algorithme Inf-Degree sont données.

In recent years, a large number of social network sites (e.g., Facebook and LinkedIn) 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 in social networks has attracted substantial interests from the fields of complex networks, data mining and algorithmic theories. Influence propagation occurs when an individual’s opinions or behaviors change as a result of interactions with others. For example, one may adopt an information or share a video on Facebook under the influence of his acquaintances and a viral effect is finally triggered through the whole network. It is called the “word-of-mouth effect”. A marketing strategy that takes advantage of the effect, which is applied extensively in companies and online softwares, is called viral marketing. The influence maximization problem, aiming to identify a subset of initial adopters in a social network to maximize the influence propagation, is an algorithmic problem for viral marketing. 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 innovation with 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. We apply the Independent Cascade model in the thesis. The thesis addresses three different problems related to influence maximization in social networks: influence propagation computation, influence maximization by seed selection and influence maximization by link activation. Firstly, the influence propagation computation consist in computing the probability that each node can be activated given a certain set of initial adopters. It is a preliminary step for the subsequent achievement of influence maximization. WeproposethePathMethod to give an exact result, theSSS-Noself algorithm and the SSS-Bounded-Path algorithm to give an approximate result. Secondly, the influence maximization by seed selection consist in maximizing the final influence propagation by targeting a seed set of certain cardinality. We combine our approaches for influence propagation computation with different heuristics for seed selection to reach the goal of influence maximization. Thirdly, we initially propose the problem of influence maximization by link activation, which is to activate the most effective links within a limited budget to achieve influence maximization. Various properties of this problem and some sub-optimal solutions such as Cost-Degree algorithm and Inf-Degree algorithm are given.