Research On Influence Maximization Problem In Online Social Networks

With the rapid development of Internet technology and the popularity of mobile terminals,online social networks(e.g.,Microblog,Facebook,etc.)have flourished,and have also been integrated into various aspects of people’s daily life.They break through the limitations of time and space,which enable people to communicate and share information conveniently at anytime and anywhere.Moreover,due to the effect of social influence,information in the social networks can be rapidly disseminated through the interaction between individuals in a very short period of time.This unique mode of information interaction and dissemination has greatly improved people’s ability to create,acquire and spread information.Therefore,the analysis of the influence diffusion in the social networks has become one of the current hot research issues.In this field,one of the most fundamental problems is influence maximization problem,where its goal is to find a small number of seeders in a social network to maximize the spread of influence under a certain influence propagation model.The research of this problem also has very important practical significance in other fields,such as viral marketing,recommendation systems and community discovery.Based on the above background,in view of the deficiencies in the existing research field of influence maximization,and combining the characteristics of realistic marketing campaigns and the needs of various practical applications,we study the influence maximization problem more deeply from different perspectives.First,consider the fact that the actual viral marketing usually focuses on achieving the profit maximization under the limited marketing costs and bounded time,we explore a more realistic constrained influence maximization problem in the social networks.For this problem,its influence spread function maintains good properties of the monotonicity and submodularity.However,since the existing greedy hill-climbing algorithm has ignored the different costs and bounded time of selecting the seeds in the process of influence diffusion,it can not be directly applied to this problem.Therefore,in order to tackle this difficulty,we propose the PCRs of nodes,and devise a new greedy approximation algorithm to effectively solve the problem.Moreover,this algorithm can provide an approximate optimal solution with an approximate ratio of().Additionally,to further improve the computational efficiency of the greedy algorithm,an efficient maximum influence propagation path based heuristic algorithm(MIPP)is proposed to approximate the calculation of the influence spread,and several pruning techniques are also devised to filter out many candidate nodes.The experimental results show that the proposed algorithm can greatly improve the efficiency of solving the problem while ensuring its effectiveness.Second,for the diffusion of multiple products in the social networks,we focus on a novel compatible influence maximization problem,which involves more complex product adoption behavior analysis of users.By introducing two explicit parameters to capture the dynamics of nodes’ product adoption behaviors,a new compatible influence propagation model is devised to better simulate the influence spread of multiple products in the networks.However,the objective function of this problem no longer exhibits the properties of the monotonicity and submodularity.Therefore,we propose the heuristic algorithm AGA and its optimized heuristic algorithm FGA to effectively solve this problem.In actual calculations,FGA algorithm can greatly speed up the selection of the optimal seed set,and it does not lose the accuracy of AGA algorithm.Meanwhile,in order to reduce the computational complexity of the compatible influence spread in a network,a tree structure based heuristic algorithm is proposed.Furthermore,to implement FGA algorithm,we devise an approximate algorithm to estimate the tighter upper bound of the marginal influence increment of each node with little computational cost.The experimental results demonstrate that compared with the current influence maximization algorithms,the proposed algorithm has better performance in terms of the compatible influence spread,and achieves high efficiency and good scalability.Last,we study a new boosted influence maximization problem from a novel edge perspective in the social networks.This problem considers that when the initial seed set is selected,adding an optimal edge set into the network to increase the influence spread of the seed set as much as possible.The influence spread function of this problem is monotone,but it no longer exhibits the submodularity.Therefore,to tackle this challenge,by limiting the number of the added edges on the maximum influence path between nodes,we devise a restricted influence spread function,and propose a SGA algorithm with theoretical guarantee to solve the problem.Moreover,in order to effectively improve the efficiency of the algorithm in selecting the optimal edge set,an efficient IGA algorithm is proposed to prune the candidate edge sets,which can also provide the same theoretical guarantee.The experimental results show that the incremental influence spread of IGA algorithm is very close to that of SGA algorithm,and is better than other baseline algorithms.Furthermore,its efficiency is much higher than that of SGA algorithm,and it still has good stability under different parameter settings.