Influence Propagation And Blocking Under Cost Constraint

Influence maximization has important research and application value in the field of complex social networks analysis.In the research of influence maximization and propagation suppression,cost limitation has attracted more and more attention from many researchers.Influence maximization with the cost constrain not only maximizes the influence but also takes into account the cost of selecting the seeds.The negative influence blocking under the cost constrain is to block as many negative influence spreading as possible under the limit of costSince the influence diffusion is a stochastic process,most of the influence maximization algorithms are based on probabilistic of models,and they require a lot of Monte-Carlo simulations,which is the most time-consuming process among all algorithms.In order to improve the efficiency of the algorithm,we use the method of sampling graph in algorithms for influence maximization and blocking.We use the reachable nodes of the seeds in the sampling graph to replace the dynamic process of influence diffusion to reduce the computation timeIn order to solve the problems of influence maximization and blocking under cost constrain,our main work and research results are as follows(1)Aiming at the problem of influence maximization under the cost limitation based on the linear threshold model,an algorithm of influence maximization based on sampling is proposed We find that in the current influence maximization algorithms,most of the computation time is for the Monte-carlo simulation that is used to measure the influence diffusion size.This process is a dynamic process and needs to be used for each batch of seed sets of different size.In order to reduce such simulation steps,we use a sampling graph to estimate the influence diffusion size.We introduce the possible world of the graph,then perform path sampling in the graph and use Chemoff bound to estimate the number of sample graphs that need to be calculated.Experiments show that our algorithm is highly accurate and efficient(2)The cost minimization problem of influence propagation based on probabilistic coverage is defined,and the problem is reduced to weighted set coverage problem(WCS),which proves that the problem is NP-hard.We also prove that the expected value function of the influence of the problem is monotone and submodular.A sampling-based greedy algorithm is proposed and its error is estimated.Experimental results show that our algorithm has higher precision(3)We define the problem of negative influence propagation blocking under the cost constraint,and defines the blocking set and the blocked set of each node.The expected blocked range of a positive seed set is estimated by sampling graphs.We propose a greedy algorithm to select the nodes to join the positive seed set one by one.We also propose the updating rules of the blocking and the blocked set of the corresponding nodes after a new node is selected to join the positive seed set.The experiment verified the feasibility of our algorithm.