Identifying Information Sources Using Dominant Eigenvalue Of Nonbacktracking Matrix

With the development of technology,information diffusion in large-scale networks is very common nowadays.For example,the development of transportation networks make it more convenient for people to transfer from one place to another.Informa-tion,like news,messages,diffuses more widely and quickly in social networks.The information diffusion in networks not only facilitates people's life,but also cause some problems,such as infectious diseases,fake news in social networks,computer viruses and so on.So how to identify information sources in general networks is important to control those risk.Identifying information sources is to identify sources of an informa-tion diffusion process combined with the topology structure of infected network and the diffusion model of information.In this thesis,we consider the problem of identifying information sources with known number of sources in a general network,in which information spreading obeys a time-slotted susceptible-infected(SI)model.Unlike existing approaches,our pro-posed algorithm identifies as sources those nodes,which when set as sources,result in the minimal dominant eigenvalue of the corresponding reduced nonbacktracking ma-trix deduced from message passing equations.We also propose a reduced-complexity algorithm derived from the previous algorithm through a perturbation approximation.Moreover,an approximate theoretical analysis of the information source detector based on the dominant eigenvalue of nonbacktracking matrix is proposed.The stepwise linearization of message passing equations reveals the change of nonlinear dynamic system is related with the dominant eigenvalue of dynamical reduced nonbacktracking matrix.The analytical expression of the dominant eigenvalue of dynamical reduced nonbacktracking matrix is derived through Power Method,which shows when the re-duced nonbacktracking matrix has minimal dominant eigenvalue,the dynamic system tends to the stable states most quickly and verify the detector.Finally,the performance of the information source detector based on the domi-nant eigenvalue of the nonbacktracking matrix is verified by simulations.Simulations include three parts:single source detection in general networks,multiple source de-tection in general networks and single source detection in tree networks.Numerical experiments show that for several representative kinds of general networks,the pro-posed method is competitive with existing methods,and it also has a good performance in multiple source detection.