The Research Of Observers Placement About Source Localization For Network Diffusion And Optimization Of Localization Algorithm

In real life, many problems can be modeled as source localization of the complex network, such as determining the source of epidemics, looking for the source of rumors, etc. These phenomena tend to produce a cascading effect on the network. Thus, locating information sources quickly and accurately on the network has important significance on infectious diseases control and public opinion control.As for the source localization problem, it is a typical method to estimate the source according to the information recorded by the observers placed on the network. However, the placement of observers has great effect on the localization accuracy, and localization efficiency of large-scale network is low. For the problem above, this thesis has completed the following work based on the theory of complex networks.Firstly, the effect of different placement of observers on localization accuracy is considered. We adopt six kinds of placement of observers according to the centrality measurements of nodes in the network, and do experiments on the model network and actual network. The results show that the localization accuracy improves rapidly with the increase of proportion of observers, and the localization accuracy is relatively low when the average degree is high. Further, it is discovered that the distance variance between the information source and the observers has a direct relationship with localization accuracy. When this variance is high, the accuracy can be maintained at a high level, which provides the experimental basis for the optimization of placement.Secondly, the complexity of original localization algorithm is O(n3), it is difficult to accept the localization efficiency of large-scale network. For this problem, a fast localization algorithm is proposed, and the complexity of algorithm is reduced greatly according to the distribution rule of the node estimate in the network, by reducing the traversal number of candidate source. It is proved by experiments that the advantage of fast localization of the improved algorithm is more obvious in large scale networks.Both accuracy and efficiency are important to any localization algorithm. This thesis discusses the effect of placement on localization accuracy, and makes comment on optimizing the placement of observers. Through improving the algorithm, it enhanced the efficiency in the case of keeping the localization accuracy of the original algorithm.