Research On Influence Maximization Algorithms In Social Networks From Multiple Dimensions

Recently,as the development of mobile communication techniques,mobile network applications are wildly utilized,and social network has become one of the most important way of sending and sharing information among people.The influence maximization problem has strong practical value and research significance,and has been one of the most fundamental and important problems in social networks.Most of the previous works in this area focus on the classical information diffusion models,however,there still lacks of research efforts on studying influence maximization problem from multiple dimensions facing the requirements motivated by real applications.Therefore,focusing on four different dimensions(dynamic influence,privacy protection,targeted influence,network structure),considering the factors affecting the influence between different nodes in social networks,the thesis focuses on the corresponding influence maximization problems.The main contents of the thesis are as follows.(1)Observing that the temporal and spatial factors will affect the influences between users seriously,the influence maximization problem when influence between nodes change dynamically is studied.Time and location are two typical factors affecting the influences in social networks.First,a new information diffusing model combining both the temporal and spatial factors is proposed and the formal definition of the corresponding influence maximization problem is given.Then,the hardness of the new influence maximization problem is analyzed,using a greedy based strategy,an approximation algorithm with ratio 1-1/e is designed.Finally,the experiments over public datasets are conducted to show both the efficiency and effectiveness of the algorithm.(2)Considering the requirements of privacy protection in real applications,the influence maximization problem supporting privacy protection is studied.First,the context based method for identifying privacy information is proposed.Then,a model for describing the procedure of information diffusing under the consideration of privacy is introduced,and the formal definition of the corresponding influence maximization problem is given.Then,after giving a theoretical analysis of the hardness of the problem,a 1-1/e approximation algorithm is designed.Finally,the experiments on public datasets are conducted to verify the performance of the proposed algorithm.(3)Considering the requirements of targeted information diffusing,targeted influence maximization problem based on multi-dimensional range selection queries is studied.Different from the classical influence maximization problem,the targeted influence maximization aims to find optimal seeding nodes which can influence maximum nodes within a specific set of nodes.Utilizing multi-dimensional range selection queries,which is an effective method for targeting in big data,it can achieve a convenient and directed method.There still lacks of research efforts focusing on solving query based targeted influence maximization problem.First,using a subclass of general queries,a useful and simple definition of the multi-dimensional selection based targeted influence maximization(MSTIM for short)problem is introduced.Then,after given a theoretical analysis of the hardness of MSTIM,a sophisticated sampling method based approximation algorithm for MSTIM with 1-1/e-ε ratio is designed.Then,an indexed based optimization is introduced to improve the performance of the proposed algorithm.Finally,the performance of the algorithms is shown based the experiments on public datasets.(4)Observing the facts that the influence between nodes is also affected by the topology structures,topology based influence maximization problem is studied.Most of the current information diffusing models,when considering whether a given node should be activated,process neighbor nodes independently and ignores the relations among those neighbor nodes totally.First,a new information diffusion model to support structural influence is proposed and the new influence maximization problem is formalized.Then,after giving the analysis of hardness of the influence maximization problem under structural influence,two heuristic algorithms are designed.To study the role of topology structures in the problem of structural influence maximization,a simplified model which only considers the structural factors is introduced and the corresponding influence maximization problem is well defined also.After showing that the above problem is still NP-hard,heuristic algorithms are presented.Finally,experiments on public datasets are conducted to verify the performance of algorithms proposed.