Network Structure Mining And Its Influence On Spreading Dynamics

With the rapid development of the Internet,the availabilities of various data have been greatly improved in the past several years,which makes the scientific research gradually step into the era of data.Complex network theory is considered as a new powerful model of data analysis,which treats real complex systems as networks and then discovers useful information and hidden rules by using methods from many disciplines(e.g.,computer science,mathematics,physics and sociology).Many complex systems can be abstracted to networks with nodes and links,in which nodes represent individuals and links denote its interactions,such as transportation networks,biological networks and social networks.So we can study many problems from the perspective of complex network theory.Researches on complex networks are of both profound theoretical significance and important practical application value.In addition,researches on complex networks can promote the fast growth of interdisciplinary fields.Network structure is an important way to understand the function and hidden rules of complex networks,so this dissertation focuses on network structure.Firstly,we analyzed the network topological structure from the static perspective and uncovered its hidden driving factors;Secondly,we gradually brought the subjects to dynamic structure,involving evolution modeling and link prediction.Finally,we studied the influence of underlying structures to the spreading dynamics.The main contents are as follow:The structural analysis and evolution modeling of recipe network: Considering few works have studied food culture quantitatively,we analyzed the shaping and evolving problem of Chinese food culture quantitatively for the first time.Firstly,we abstracted the Chinese recipe network based on data crawled from online recipe website.Through correlation analysis on topological distance,temperature difference and similarity of cuisines,we found that frequent communication play an important role in shaping food culture.Finally,we proposed an evolution model based on copy-and-mutate mechanism,which agree well with our empirical findings.These findings not only can provide one theoretical framework for the in-depth study of food culture,but also shed some light on the analysis and modeling of social sciences.The link prediction problem of complex networks:(1)In order to better predict missing links with cold ends,we proposed an improved algorithm by adjusting the weight of link's popularity,which considerably improved the prediction accuracy of cold links by about 10%.This algorithm can alleviate the cold start problem of link prediction.(2)To solve the low-diversity problem,we proposed one hybrid algorithm by considering both heat conduction and local random walk,which can improve the diversity by about 32%in the condition of not decreasing the accuracy.This algorithm can ease the plight of the trade-off between accuracy and diversity to some extent.(3)In order to uncover missing links in directed networks,we proposed one algorithm based on directed subgraph,which can be nearly 90% right.The improved algorithms here can be used in many real applications and have high practical value.The influence of underlying structure to spreading dynamic:(1)We studied the influence of reciprocal links to simple spreading process by percolation theory.Our results demonstrated that the reciprocal links play a more important role than equal number of non-reciprocal ones.In particular,the coverage of spreading process can be significantly enhanced by considering the reciprocal effect.We also gave some possible explanations from the perspectives of network connectivity and efficiency.(2)We investigated the influence of heterogeneous structure to complex contagion model in both simulative and analytical ways.Our results demonstrated that degree heterogeneity can not only alter the dependence of final adoption size on unit transmission probability from discontinuous to continuous,but also enhance(reduce)the final adoption size at the small(large)value of unit infection probability.By contrast,the heterogeneity of weight distribution can hinder social contagion while not changing the dependence behavior of final adoption size on unit transmission probability.In addition,we confirmed these findings by edge weight-based compartmental approach.These studies can provide theoretical guidance for the control of some real propagation processes.