The Research On Influence Blocking Maximization In Social Networks

With the development of internet technology,social networks are emerging such as Facebook,Twitter,Sina Weibo,Tencent Weibo,Douban and so on.The social network has become a part of people's daily life.Researchers have studied social network issues from different aspects and influence maximization(IM)is one of the most popular issue.The goal of the IM problem is to identify at most k users in a given social network to propagate influence to maximize the influenced users by utilizing word-of-mouth.In contrast,the influence blocking maximization(IBM)problem is an extension of the IM problem and the goal of the IBM problem is to select at most k users to propagate positive influence to block the propagation of negative influence as much as possible.IBM has very important applications such as rumor control,viral marketing and so on.Especially for rumor control,due to the virtual and openness of social networks,it can easily become a hotbed of rumors.When the rumor occurs,IBM can effectively block the influence propagation of rumors by finding the most influential users to propagate the truth.So,this thesis studies the IBM problem in social networks and the main aspects are as follows.Firstly,the existing algorithms for IBM do not consider the location information of nodes such that these algorithms can not select optimal seeds for different regions.To solve this problem,this thesis proposes the location-aware influence blocking maximization(LIBM)problem for the first time,and proves that the LIBM problem is NP-hard and the influence function is monotone and submodular under the homogeneous competitive independent cascade model.To overcome the inefficiency of the traditional greedy algorithm,this thesis proposes a holistic-based location-aware influence blocking maximization algorithm,called LIBM-H.LIBM-H utilizes Quadtree to store location information of nodes,utilizes the maximum influence arborescence(MIA)structure to simulate the propagation of positive and negative influence,utilizes a dynamic programming algorithm to calculate the blocked negative influence of candidates to nodes located in a given region,and greedily selects the candidates with the largest blocked negative influence as the positive seeds.Experiments on three realworld social networks demonstrate that LIBM-H can identify the optimal seeds according to the given region and the blocking effect of LIBM-H is close to that of the theoretical optimal greedy algorithm,but the running time of LIBM-H is four orders of magnitude faster than that of the greedy algorithm.At the same time,the blocking effect of the LIBM-H algorithm is much better than that of other baseline algorithms.Secondly,it is time-consuming for LIBM-H to identify optimal seeds for the reason that LIBM-H needs to calculate the blocked negative influence of each candidate to nodes located in the whole region in real time.To solve this problem,this thesis proposes a cell-based location-aware influence blocking maximization algorithm,called LIBM-C.Instead of directly calculating the blocked negative influence of candidates to nodes located in the whole region,the LIBM-C algorithm preconstructs the cell index and the node index according to Quadtree,and preserves the blocked negative influence of nodes in cell lists in the pre-processing step.In the online processing step,the LIBM-C utilizes the preconstructed node index and cell index to calculate the initial blocked negative influence of nodes,and identifies positive seeds in a maxheap by utilizing an upper bound based method to eliminate many insignificant candidates with little blocked negative influence.Experimental results show that the average running time of the LIBM-C algorithm is 2.5 times faster than that of the LIBM-H algorithm,and the blocking effect of the LIBM-C algorithm is close to that of the LIBM-H algorithm.Thirdly,the existing algorithms for IBM do not consider the location information for seeds selection such that these algorithms can not select optimal seeds for the given query region and block region.In order to solve this problem,this thesis proposes the location-based seeds selection for influence blocking maximization(LSSIBM)problem for the first time,and proves that the LSSIBM problem is NP-hard and the influence function has characteristics of monotonicity and submodularity under the homogeneous competitive independent cascade model.Further,this thesis devises an influence set(IS)based algorithm IS-LSS and its improved algorithm IS-LSS+ to overcome the low efficiency of the greedy algorithm.Both of the IS-LSS and IS-LSS+ algorithms calculate the regional-constrained blocked negative influence of each candidate based on its influence set,and identify optimal seeds based on a maximum heap.Compared with the IS-LSS algorithm,the optimization of the IS-LSS+ algorithm is that it utilizes an upper bound based method to further improve the running time.Experimental results demonstrate that the proposed two algorithms can identify the optimal seeds according to the given query region and block region and the blocking effect of the proposed algorithms is close to that of the greedy algorithm,but the efficiency of the proposed algorithms is improved by four orders of magnitude than that of the greedy algorithm.At the same time,the blocking effect of the proposed algorithms is much better than that of other baseline algorithms.In addition,compared with the IS-LSS algorithm,the IS-LSS+ algorithm takes less running time and is more robustness for queries of different size of regions than that of the IS-LSS algorithm.Finally,the existing algorithms for IBM do not consider the interests of users when selecting seeds such that these algorithms cannot select the optimal seeds for different topics and query regions.To solve this problem,this thesis proposes location-aware targeted influence blocking maximization(LTIBM)problem for the first time,and proves that the LTIBM problem is NP-hard and the influence function is submodular and monotone under the homogeneous competitive independent cascade model.Further,this thesis proposes a holistic-based algorithm to solve the LTIBM problem,called LTIBM-H.The LTIBM-H algorithm utilizes QT-tree to store locations and topics of nodes,calculates the targeted region-constrained blocked negative influence of candidates to nodes located in the given region and having preferences on the given topics by utilizing a dynamic programming algorithm,and greedily selects the nodes with the largest targeted region-constrained blocked negative influence as positive seeds.Experimental results demonstrate that the proposed algorithm can identify the best seeds according to the given topic and location information and the blocking effect of the proposed algorithm is obviously better than that of other baseline algorithms.