Research On Social Network Information Source Detection Algorithm

With the development of Internet technology, people's ways of communication have changed a lot. Large numbers of mobile social networking platforms such as Microblog, WeChat, QQ, which attracted a large number of users from different fields involved. They communicate with each other and publish what they have seen and heard through these mobile social network platforms. Consequently, various large-scale social networks have formed which provide more quickly and broader ways for a lot of information dissemination. Social network information source detection is a hot topic. We can manage information distribution and protect the healthy development of social networks if we could find information sources. Currently, information source detection based on social network topology has become a very popular research direction.This thesis presents an adaptive observer deployment strategy which can be dynamically adjusted according to the changes in the network topology. Then, records information dissemination data and figures out Kendall Coefficient to find information source. The main contents of this thesis are as follows:(1) Research on observer deployment strategy. The strategy is based on r-coverage rate optimization strategy. The key is propose a strategy which can make the observer has the maximum r-coverage rate. The concrete thought is build a mathematical model to convert the observed point set selection problem into a set covering problem. Commonly, we use greedy algorithm to solve set covering problem. However, in order to reduce the cost of computing time, we will give higher priority to the nodes which have bigger importance because they have greater impact on r-coverage rate than those nodes which have smaller importance. So, this thesis presents greedy algorithm based on heuristic strategy. There are many indicators to evaluate the importance of nodes. We use degree centrality to evaluate the importance of nodes. These nodes whose degree are less than the threshold value of the node will not be considered, compared with traditional greedy algorithm, the greedy algorithm based on heuristic strategy can accelerate convergence and improve time efficiency.(2) Research on single information source in social network. Since the information publisher is unique in the single information source network, the time when observer receive the information is related to the distance between information source and distance. In general, the longer the distance between two nodes, the more transmission time between these two nodes. Therefore, we can quantize the relationship between the time when observer receive information and the distance between candidate information source and observer, calculate Kendall Coefficient to achieve information source detection based on this point. Moreover, this paper proposed another information source detection algorithm based on the time difference when observer receive the information.(3) With considerable experiments we verify information source detection algorithm this paper proposed. We examine the proposed information source detection algorithm with simulate networks and actual networks respectively. The experimental results show that the proposed algorithm can decrease the executive time of the program, meanwhile, it also can improve the accuracy of information source detection.