Influence Minimization And Rumor Containment In Social Networks

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.Besides that,the propagation phenomenon can also be observed in many other networked systems,such as epidemics spread in human and animal physical contact networks,cascading failures in infrastructure networks,and virus spread in computer networks.Many studies have been devoted to formalizing such complex individual behaviors through mathematical models that provide keys to understand the mechanism of the propagation phenomenon and to controlling the propagation process,among which the influence maximization problem receives much attention.This problem consists in identifying a small subset of early adopters(called seed set)that maximizes the total influence propagation for a given diffusion model and has a clear practical motivation in many applications including budget allocation in viral marketing,controlling the rumor spread,opinion formation,information spread forecasting,etc.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 the undesirable entities is meaningful.This dissertation mainly focuses on the influence minimization and rumor containment 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).We show that an exact solution to the LMD problem can be computed by solving an integer linear programming problem and also 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 parts of this dissertation by investigating different rumor control strategies.We first adopt the counterbalance strategy which consists in spreading correct information.In this case,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 proven to be NP-hard for our generalized model.To cope with the computational complexity of the MRS problem,we present three different heuristics(Page Rank,Min Greedy,Contr ID)and define their constrained versions(Prox Page Rank,Prox Min Greedy,Prox Contr Id)to highlight the proximity effect for solving the MRS problem.The novel heuristic approaches Contr Id and Prox Contr Id guarantee the monotonicity for the LT1 DT which ensures that efficient strategies for constraining rumor can be devised.Simulations are finally carried out under four different networks.Experimental results have shown that diffusion dynamics based approach(Contr Id)outperforms centrality based approach(Page Rank)while requiring the same level of computation complexity which grows linearly with the number of nodes in the network,and therefore can scale well to large networks.By introducing the proximity effect,Contr Id performs as well as Min Greedy but runs much faster than Min Greedy.The second rumor control strategy we adopt is network disruption strategy which consists in 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.In order to evaluate the effectiveness of our improved integer linear programming method,we compare it with a greedy based approach and two centrality based approaches in two synthetic and two real-word datasets.The experimental results show that the integer linear programming method outperforms all other three approaches and can scale to large networks due to its reasonable running time.