Link Prediction And Source Location In Temporal Networks

Network is a basic form of the world material and a powerful tool to describe and characterize complex systems.Real systems have intrinsic time-varying characteristic,which means the structure and function of systems tend to evolve with time.Thus,networks modeling systems change with time as well,such as communication networks,social networks and protein-protein interaction networks,etc.These networks of which the nodes' properties and topological structures change with time are called as temporal networks.Temporal networks can be more precisely abstraction of the time-varying systems,so theories analysis and methods research has important theoretical significant and wide practical value.This paper focuses on the study of theoretical models and dynamic methods on temporal networks based on the time-varying characteristics of complex systems.We regard temporal networks as the mean for modeling and analyzing complex systems,with the hypothesis that the size of networks is constant and the topological structure is evolved with time,and the paper mainly includes the following three aspects:First,we summarize the fundamental knowledge of complex network.This paper introduces the common measures and typical network models for complex networks,and compares these measures to analyze the differences between several network models.We also summarize the traditional methods for link prediction and the classical propagation models,which provides necessary fundamental theories and methods for the further study.Second,for the reconstruction problem of topological structure in temporal networks,we propose an algorithm for link prediction with applying multivariate time series analysis.The model uses time series analysis method to depict the time dimension of temporal networks,and combines the multivariate time series analysis with tradition structural similarity indexes to effectively synthesize information of structure and time.The model is verified in Enron email network and High Energy Particle Physics co-authership network,and the result indicates that the single variate time series analysis can well describe the evolution of the network linkages,and the hybrid model combining the multivariate time series analysis with traditional methods considers the network as a whole which can further improve the accuracy of link prediction.Third,to the application problem of information spreading in temporal networks,we propose an algorithm based on backward temporal diffusion process to locate the spreading source.As the topological structure of networks and a part of observed nodes' information is known,the model can solve the inverse problem of source locating through minimizing the fluctuation of spreading time difference with observed nodes based on the information dissemination process.We also design three strategies for sampling the observed nodes by ranking nodes' importance,which can improve the efficiency for source locating.The experiments demonstrate that our algorithm can effectively deal with the source locating problem in temporal network.And Only 50 percent nodes of the whole network need to be detected,we can obtain more than 90 percent of the locating precision.