Research On The Spreading Influence And Source Localization In Complex Networks

With the rapid development of Internet technology,the data available to human society is growing at an unprecedented rate,proclaiming the official arrival of the era of big data.As one of the important tools of data analysis,the research about complex networks has received extensive attention by scholars in various fields.Especially with the rise of online social networks,the successful application of complex networks in analyzing user behavior patterns has already reflected its great value in economic and social areas.The main purpose of researching complex networks is to solve the dynamic problems on networks.Based on the spreading dynamics on complex networks,we study two kinds of application problems,i.e.the influence maximization problem and the source localization problem.The main contribution of this paper lays on four aspects:First,we propose a heuristic influence maximization problem via local effective spreading path.One of the main difficulties in influence maximization is that the influential areas of multiple nodes are always overlapping,seriously weakening their total influence on networks.In order to reduce the influence overlapping among nodes,we define the concept of local effective spreading path to describe the competitive spreading behavior of nodes on networks,and propose a heuristic algorithm to solve the influence maximization problem,which significantly increases the total influence of seed nodes.Second,we provide the percolation-based natural greedy algorithm to solve the influence maximization problem.Considering the fact that the spreading influence of nodes is closely related to the dynamical process in the network,we specifically study the influence maximization problem under the SIR(Susceptive-Infected-Recovered)dynamics.Inspired by the percolation theory,we re-model the influence maximization problem from the perspective of site percolation and design a greedy method to seek the seed nodes iteratively.The simulations results verified the superiority of our algorithm,and it performs even better than the general approach proposed in pervious chapter.Thirdly,we consider to locate the epidemic source based on Pascal distribution.Taking the SIR dynamics as an example,we try to solve the source localization problem in stochastic systems.It is found that under SIR dynamics,the infection time from the source to any node obeys the Pascal distribution,thus we design a probabilistic method and successfully find the real epidemic source.Our algorithm can show a clear advantage over other methods,especially when there is a strong randomness in the spreading process on networks.Fourthly,we derive a solution of source localization problem under time delay systems based on optimizations over Gaussian distribution.By modeling the time delay along edges in a probabilistic way,we realize that we can locate the spreading source via maximum likelihood estimation over a multivariate Gaussian distribution.Finally,we have successfully conducted the optimal solution of source localization problem on tree networks,and further expanded our conclusion to locate the source on general networks.Numerical analysis demonstrates that our algorithm performs obviously better than other benchmark methods under multiple indicators.