Analysis Of The Spreading Phenomena On Complex Networks And Its Application To Structure Prediction

Due to the advancement of computer and information technologies,the massive data describes the relations between the entities in the networked systems and promotes network science.Interestingly,these different types of networks share common struc-tural features and present similar dynamics,among which the disease outbreak,informa-tion diffusion and other spreading phenomena have been the focus of current researches.Meanwhile,different immunization strategies are proposed to better utilize or control the spreading process.Since the spreading behaviors are closely related to the network structure,it is of great significance to investigate the spreading process and the under-lying network structure together.This dissertation explores the influence of network structure on spreading processes from theoretical and empirical analyses,and then ap-plies the research results to the prediction of network structure.In summary,the main contents and achievements are as follows:1.Empirical spreading processes on social networks are studied.By tracking the propagation paths of real spreading events on networks Twitter and Brightkite,the em-pirical analysis reveals that the spreading probability and the spreading velocity present the explosive growth within a short period,and there always exists the asychronism be-tween the maximal spreading probability and the maximal spreading velocity.Based on this,the improved Susceptible-Infected(SI)model with time-varying spreading prob-ability is proposed.Besides,the negative correlations between degree and threshold value of nodes are introduced into the Linear Threshold model.The analytic and ex-perimental results on real-world networks both reproduce the spreading phenomenon in real networks,which deepens the understanding of spreading problems.2.The connections between the critical threshold and immunization strategies are analyzed.Immunization strategies for raising the critical threshold can effectively sup-press the spreading of the virus and protect the population from the epidemics.Based on the heterogeneous mean-field(HMF)theory for the Susceptible-Infected-Susceptible(SIS)model,a general framework that quantitatively characterizes the critical threshold is proposed to evaluate different immunization strategies in heterogeneous networks,which also analytically explains that the targeted large-degree strategy shows the best immune effects in uncorrelated networks.Besides,the numerical experiments demon-strate the effectiveness of the proposed framework in both artificial and real-world net-works.3.The temporal trend of nodes and the applications to the prediction of network structure are studied.A few nodes are usually influential in the spreading process and network structure.Firstly,the relative popularity of nodes are evaluated according to the trend of edge increment,which are further combined with the inherent structural features to enhance the importance and attractiveness of popular nodes.Then a novel approach named popularity based structural perturbation method(PBSPM)is proposed to characterize the likelihood of a future edge from both existing connectivity structure and current popularity of its two endpoints.Besides,a fast algorithm that only considers a few dominant features is proposed for large-scale networks.Experiments on real-world networks show that the proposed algorithms outperform the state-of-the-art methods in accuracy and robustness.The achievements expand the knowledge of the interactions between the spreading behaviors and network structure,which can be applied to the control of information diffusion,social recommendations and other fields.