Research On Influence Competition Problem In Social Network Under Cost Constrant

With the popularity of the Internet, the number of social network users gradually increases and social network has become an important medium where the public obtain information. Influence propagation on social network means the user's thinking and behavior are affected by others, so that social network users accept certain ideas or perform certain actions. We collectively refer to these diffusions of information, ideas and so on in social network as influence propagation. Social network influence propagation problem has become the focus of research scholars. The research about influence propagation problem has a very wide range of applications in the dissemination of information, promotion of product, control of speech, etc.As the number of users of social networks continues to increase, more and more users participate in product marketing and information popularization in social network, which inevitably causes competition problem in influence diffusions. Most researches do not consider the competition problem. However, competition exists extensively in social network. When the presence of competitors, how do we choose a better strategy to spread the influence is a valuable research issue.Competitive influence propagation problem is a more complex problem compared with the traditional influence propagation problem. It is more challenging and worthy to be studied. Some recent studies have considered competitive influence propagation, but the current studies are not comprehensive enough and there are some issues that need to study. This paper is based on the actual needs of users, conducting a series of studies on the influence competition for the existing problems of the existing work. Our main works and contributions are as follows:1. We propose a new problem called minimizing cost to win competition (MCW) and prove it is NP-Hard. For MCW problem, we propose a cost-effective greedy algorithm to approximately solve the problem, which calculates the influence of each node at each round of the Monte Carlo simulation method and adds the node with best cost-effective to seed sets. We improve the efficiency of cost-effective greedy algorithm based on the submodularity. For large-scale social network, we propose a new Degree Adjust heuristic. Degree Adjust algorithm considers the number of neighbors and the neighbors'affected situation to quickly predict the influence of the nodes, and then adds the node with best cost-effective to seed sets, avoiding the Monte Carlo simulation, and thus greatly improves the efficiency. Finally, experimental results on real data sets show that cost-effective greedy algorithm achieves better effectiveness than other algorithms and the cost-effective Degree Adjust heuristic algorithm achieves high efficiency and gets better effectiveness.2. We propose the problem of maximizing the influence ranking under limited cost in social network problem (MRLC) and prove this problem is Np-Hard. For MRLC problem, we propose an intelligent greedy algorithm to approximately solve the problem and improve the efficiency of the algorithm based on submodularity of function. For large-scale social network, we propose Multi-Step Influence Adjust (MIA) algorithm. MIA algorithm considers the number of neighbors, neighbors'influence and affected status and loops through multiple iterations to compute nodes'influence. Our experiments on real data sets show that the intelligent greedy algorithm achieves the best experimental results and MIA algorithm significantly improves efficiency and also achieves good experimental results.