Research On Influence Maximization For Specific Users In Social Network

In recent years, with the development of social network, the applications of social network have been greatly attracted the attention of researchers. Influence maximiza-tion in social network is one of the most popular problems. Influence maximization is to pick up a small number of initial users to spread influence in the network, maximiz-ing the number of influenced users in the propagation. The problem is NP-hard. The approximation methods for it has received tremendous attention from researchers. The majority of the related work aims at approximation optimization methods for influence maximization and improvement of influence spread model. They ignore the adaptive scope of influence maximization. Taking concrete scenario in real world into consider-ation, we propose two improved problems for influence maximization. The details of our paper are as follows:1. In real world, Information or opinion is always propagated via multiple chan-nels. Based on the motivation, we propose influence maximization across multi-channels. It is to pick up a few users to spread influence across multiple chan-nels, maximizating the number of influenced users. We formulate the problem and prove it is NP-hard through reducing it into standard influence maximization. Moreover, we approve the computation of influence spread is #P-hard. Accord-ing to the characters of the problem, we propose three approximation methods: greedy method, degree based method and composition graph based method. The experiments on real network data sets show our methods are effective.2. Considering the scope of initial users is always constrained, we propose the im-proved version of influence maximization for targeted users——influence max-imization for constrained users. It is to pick up a few users from constrained user set, with the goal of maximizing the number of targeted users. We prove the prob-lem is NP-hard and the computation of influence spread is#P-hard. Moreover, we approve the function of influence spread is non-negative, monotonically in-creasing and sub-modular. According to the properties, we propose three approx-imation methods:ccelf、candidate based method and preprocess based method, ccelf can return a certain approximation guarantee. The preprocess based method basically meets the need of online problem via the preprocess of offline stage. The experiments on real network data sets show the effectiveness of our methods.