Study On Method Of Locating Diffusion Source For Social Network

With the appearing of online social networks,users in the network are becoming not only the receivers of information but also promulgators.It not only provides users with a good platform for interactive communication,but also provides functions of convenient instant forwarding and comment.Therefore,the online social network has been recognized by the majority of users,and has become one of the most important ways of information exchange.However,the diffusion of misinformation,such ascomputer virus and network rumors,has brought great harm to people's lives.It has become to be a hot issue in the field of related researches to locate the diffision sources in the network accurately,which is an effective way to control and reduce the risk arising from misinformation.Existing diffusion source localization methods for online social network aremostly based on observers.That is to say,a few observers are deployed in the network,and the diffusion source is located by the diffusion data they record.Therefore,this kind of method only needs to observe a few nodes in the network,occupies network resources rarely,which is more appropriate for online social network.However,there are still some key problems to be further studied.First,the localization accuracy is directly depended on the network topology structure and the observer deployment method.But there is neither systematical analysis,nor clear conclusion on relationships of them.Secondly,existing observer deployment methods are based on the centrality of node,considering the significance of single node for the entire network.However,in the process of localization computation,the observer set is an entirety.Therefore,in order to get the best observer set,observers should be deployed from the overall point of view.Thirdly,in practical applications,there are often multi diffusion sources in the network.In this case,the diffusion source localization methods which are based on observers neither can determine the number of sources,nor distinguish the diffusion range of every source and locate the source accurately.Finally,in some online social networks,we can get partial diffusion paths through the comments which are appended on the information by the users when they forwarded it.By making full use of these path data,the diffusion process can be reproduced more accurately,which is great useful to localization computation.But existing works have not given any usage of partial diffusion paths.In view of above problems,diffusion source localization methods for online social networks are studied in this thesis.Through simulation experiments,relationships of localization accuracy to observer deployment and network topology structure are systematically analyzed firstly.The problems of optimizing of observer deployment,locating of multi diffusion source and usage of partial diffusion paths,are then studied in this thesis by analyzing the process of localization computation.Corresponding solutions are finally proposed in this thesis.Details are given as follows:(1)Analysis of the influence on localization accuracy based on the node centrality.In order to analyze the relationships of localization accuracy to observer deployment method and network topology structure,a simulation experiment analysis system is designed in this thesis.In this system,a variety of classical node centralities are selected as the measurement index of observers.Simulation experiments are then carried out on different types of model networks and actual networks.Experimental results of different observer deployment methods on the network are finally summarized and analyzed.(2)The optimized observer deployment method for locating diffusion source in social network.In terms of the optimizing problem of observer deployment method,the observers are considered as an entirety,the influence of deployment location on localization accuracy of specified source and any source is analyzed.On the basis of the conclusion,an observer deployment method based on r coverage rate first is proposed,and details of the method are then described.The validity of the theoretical analysis and the optimized method is validated by simulation experiments.Experimental results show that,localization accuracy of the proposed deployment method is higher than the existing methods.(3)A multi diffusion source localization method for online social network based on sub-graph extraction.In terms of the problem of the same information is spread by multi diffusion sources in the network,propagation process and characteristics of multiple source information diffusion in community networks are analyzed.On the basis of the conclusions,a multi diffusion source localization method based on sub-graph extraction is proposed.Accuracy of the proposed localization method is validated by simulation experiments.Experimental results show that,the method can effectively determine the number and spread range of the sources,and then accurately locate them.(4)Research on optimization method of diffusion source localization based on partial diffusion paths.In terms of the problem of the usage of partial diffusion paths,the locating process of observer based localization method is analyzed from the aspect of improving the localization accuracy and localization efficiency.On the basis of the conclusions,a spanning tree optimization algorithm and a candidate screening algorithm are proposed both based on the partial diffusion paths.The former is aimed at optimizing the the construction method of information diffuse tree to improve the localization accuracy based on partial diffusion paths.The latter is aimed at screening the candidate set to improve the localization efficiency.Correctness of the two.proposed algorithms is finally validated.Experimental results show that,the two algorithms achieve the desired objectives and are effective.