Influence minimization and rumor containment in social networks
Institution:
Aix-MarseilleDisciplines:
Directors:
Abstract EN:
This thesis mainly focuses on the rumor containment and influence minimization problems in social networks. In the first part, we formalize two different influence minimization problems generalizing the scenarios under the LTM model, 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. 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 the general case.Rumor containment is analyzed in the second and third parts 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., LT1DT. The problem of minimizing rumor spread (MRS) is addressed. To cope with the computational complexity of the MRS problem, we present three different heuristics and define their constrained versions to highlight the proximity effect for solving the MRS problem. To control the rumor spread, we then consider the network disruption strategy by blocking a set of nodes. 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
Abstract FR:
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, nous formalisons deux problèmes distincts de minimisation d'influence 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. Pour le problème DMGT, nous fournissons une technique pour rechercher une solution optimale qui fonctionne pour les cas particuliers et discutons d'une heuristique simple pour trouver une solution 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, c'est-à-dire LT1DT. 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 et définissons leurs versions contraintes pour souligner l’effet de proximité pour résoudre le problème MRS. 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 proposons ensuite une formulation non linéaire du problème d'identification des top-k-bloquants et introduisons quelques techniques mathématiques pour linéariser la formulation non linéaire