Soutenance de thèse de Lan YANG

Avec la prédominance des médias sociaux en ligne au cours des dernières décennies, l’échange des idées, des informations et même l’adoption des innovations ou de nouveaux produits sur ces plateformes sont devenus monnaie courante ce qui facilite la propagation de ces contenus. De nombreuses études ont été consacrées à l’influence des problèmes de maximisation qui tiennent habituellement compte de la diffusion d'événements désirables comme l’information positive et l’innovation. Des événements indésirables, tels que les pannes techiniques, les rumeurs, les maladies épidémiques, etc., peuvent également se propager de manière similaire et causer des dommages importants à la société. Par conséquent, le problème de contenir ou de contrôler la diffusion des événements indésirables est intéressant. Cette thèse porte sur l’endiguement des rumeurs et la minimisation de l’influence dans les réseaux sociaux. Dans la première partie, supportée par l’analyse de scénarios réels, nous formalisons deux problèmes distincts de minimisation d’influence en généralisant les scénarios sous le modèle à LTM, c'est-à-dire la minimisation des pertes avec perturbation (LMD) et la minimisation de la diffusion avec cible garantie (DMGT). Pour le problème LMD, nous montrons qu’il est équivalent à la résolution d’un problème de programmation linéaire en nombres entiers et décrivons deux algorithmes heuristiques pour trouver des solutions approximatives. Pour le problème DMGT, nous fournissons une technique pour rechercher une solution optimale qui fonctionne dans certains cas particuliers et discutons d’une heuristique simple pour trouver une solution (généralement sous-optimale) dans le cas général. La maîtrise des rumeurs est analysée dans les deuxième et troisième parties de cette thèse en adoptant différentes stratégies de contrôle des rumeurs. Nous adoptons d’abord la stratégie du contrepoids en diffusant une information correcte. Nous proposons une version compétitive et généralisée du modèle à LTM, c'est-à-dire le modèle à seuil linéaire avec transition d’état unidirectionnelle (LT1DT), qui prend en compte les situations pratiques dans lesquelles la rumeur et la vérité sont en concurrence dans un même réseau et comble certaines lacunes des modèles de diffusion concurrentiels existants. Le problème de la minimisation de la propagation des rumeurs (MRS) est abordé et s'est avéré difficile pour notre modèle généralisé. En raison de la dureté théorique du problème MRS, nous présentons trois heuristiques différentes (PageRank, MinGreedy, ContrID) et définissons leurs versions contraintes (ProxPageRank, ProxMinGreedy, ProxContrId) pour souligner l’effet de proximité pour résoudre le problème MRS. Les nouvelles approches heuristiques ContrId et ProxContrId peuvent garantir la monotonie du LT1DT qui assure qu’un budget limité pour limiter les rumeurs peut être utilisé correctement. Pour contrôler la propagation de la rumeur, nous considérons ensuite la stratégie de perturbation du réseau en bloquant un ensemble de noeuds. Nous montrons d’abord que la fonction objective du problème d’identification des top-k bloqueurs est monotone mais non sous-modulaire et non supermodulaire pour le LTM. Nous proposons ensuite une formulation non linéaire du problème d’identification des top-k-bloquants dans le LTM basée sur la notion de cohésion et introduisons quelques techniques mathématiques pour linéariser la formulation non linéaire. La complexité de la programmation linéaire en nombres entiers peut être encore réduite en montrant qu’avec un jeu de semences, le processus d’évolution dans l’ensemble du réseau est équivalent à celui de son sous-réseau actif.

With the prevalence of online social media in the past decades, people are more and more likely to exchange ideas, share information, and even adopt innovations or new products on social networking platforms which facilitate the propagation of those contents. Many studies have been devoted to the influence maximization problems usually consider the spread of desirable entities such as positive information and innovation. Undesirable entities, such as failures, rumors, epidemics, etc., may also spread in a similar fashion and could produce significant damages to the society. Therefore, the problem of containing or controlling the diffusion of undesirable entities is meaningful. This thesis mainly focuses on the rumor containment and influence minimization problems in social networks and three main contributions are presented. In the first part, motivated by real-world scenarios, we formalize two different influence minimization problems generalizing the scenarios under the Linear Threshold model (LTM), i.e., the Loss Minimization with Disruption (LMD) and the Diffusion Minimization with Guaranteed Target (DMGT). For the LMD problem, we show that it is equivalent to solving an integer linear programming problem and we provide two heuristic algorithms to find approximation solutions. For the DMGT problem, we provide a technique to search for an optimal solution that works in some particular cases and discuss a simple heuristic to find a solution (in general suboptimal) in the general case. Rumor containment is analyzed in the second and third part of this thesis by investigating different rumor control strategies. We first adopt the counterbalance strategy by spreading truth. We propose a competitive and generalized version of the LTM, i.e., Linear Threshold model with One Direction state Transition (LT1DT), which captures practical situations in which rumor and truth compete in the same network and overcomes some shortcomings of the existing competitive diffusion models. The problem of minimizing rumor spread (MRS) is addressed and proved to be NP-hard for our generalized model. To cope with the computational complexity of the MRS problem, we present three different heuristics (PageRank, MinGreedy, ContrID) and define their constrained versions (ProxPageRank, ProxMinGreedy, ProxContrId) to highlight the proximity effect for solving the MRS problem. The novel heuristic approaches ContrId and ProxContrId guarantee the monotonicity for the LT1DT which ensures that effective strategies for constraining rumor can be devised. To control the rumor spread, we then consider the network disruption strategy by blocking a set of nodes. We first show that the objective function of the top-k blockers identification problem is monotone but non-submodular and non-supermodular for the LTM. We then propose a non-linear formulation of the top-k blockers identification problem in the LTM based on the notion of cohesiveness and introduce some mathematical techniques to linearize the non-linear formulation. The complexity of the integer linear programming can be further reduced by showing that given a seed set, the evolution process in the whole network is equivalent to that in its active sub-network.