Location Based Social Network Influence Propagation Research

The research on the influence propagation is a significant part in the field of complex network analysis,propagation problems on complex networks study the propagation behavior of things in real systems.The issues of influence maximization and influence blocking maximization have become hot topics that have attracted much attention.With the emergence and the growth of various social network platforms,mass data has been generated based on social network platforms,which provides a good environment for the research of social networks.The influence maximization originates from viral marketing,and social networks have gradually become a new way of marketing.Therefore,research on issues such as influence maximization and influence blocking maximization have theoretical and practical significance.The traditional problem of influence maximization aims to find a set of key nodes,so that their spread is maximized.With the emergence of location-based social networks(LBSN),study on traditional social networks have changed.The methods for traditional influence maximization are unable to meet the needs of real distance,space region,etc.in real life.In this work,we propose a more realistic research on the influence of social networks based on location information.Both influence maximization and influence blocking maximization are proved to be NP-hard problems.To solve such NP-hard problems,an effective approximation algorithm must be used.Therefore,based on the problems above,the main contributions of this work are as follows:(1)We investigate the distance-aware influence maximization problem on the independent cascade(IC)model.A random walk based algorithm is presented to find the seed set to maximize the influence for a distance aware query.Random walk method is used to perform path sampling for simulating the influence propagation process.Based on the result by random walk method,greedy method is used to select the optimum seed set.Our experimental results show that the algorithm can efficiently select the seed set to maximize the influence propagation.(2)We study the problem of location-aware influence maximization with the targeted region.The user's historical check-in data is used to calculate the user's geographic preferences in a certain area,and are considered when calculating the influence spread.We use VC-dimensional theory to compute the number of samples,and construct a corresponding number of possible worlds.The activation path calculation was performed in the possible worlds in order to calculate the probability for each node to activate the nodes in the targeted region.The k nodes with the largest probabilities are selected to form the seed set,so that the influence transmission in a certain area is maximized.(3)We study the problem of location-aware influence blocking maximization(IBM).We define the IBM problem with the region awareness,and present a method to select the positive seed nodes to maximize the blocking effect of the negative influence.Based on the greedy method,the idea of independent path is used to calculate the propagation probability.The positive seed set is iteratively selected by the formula calculation method,and the correctness of the related theory is proved.Experimental results show that the proposed greedy algorithm can have better guarantee.