Study Of Evolutionary Model And Navigability Of Spatially Embedded Networks

In present time,the study of complex systems represented by complex networks has become an advanced research hotspot in the scientific community,including the empirical research of real networks' structural features,the study of network measurement,evolutionary model of networks,network robustness,network control performance and network dynamics.Complex spatial networks is a kind of special complex networks which are embedded an Euclidean space.Some empirical research indicate that complex spatial networks have many special features,such as small world property,scale free property,high clustering coefficient and the power law distribution of network links.Although there are numerals researches on static model of networks which have those features we mentioned,a self-organized model that emerge the features is still absent.In other words,the formation mechanism of complex spatial networks is still unknown.This thesis introduces and studies a self-organized evolutionary complex spacial network model to explore this mechanism.The network is built by considering two elements of the network,popularity and similarity.Popularity is represented by the node birth time,and to model similarity,we consider it as the Euclidean distance between a newly emerging node and preexisting nodes.Through the minimization of the product of popularity and similarity,the network is established.Based on a one-dimensional network and a two-dimensional one,we study the topological properties of the networks emerged by this mechanism and find that the networks emerge four features:(1)small world property;(2)sale free property;(3)high clustering coefficient;(4)a power law distribution of network links.Those features meet the structural features of the real networks very well.The navigability of complex spacial networks can help us to understand the relationship between network structure and function.We propose a bias navigation algorithm,where bias is represented as a probability p of the packet to travel at every hop toward the node which has the smallest Manhattan distance to the target node.First,we investigate the biased random walk on a Kleinberg's spatial network which is built from a d-dimension regular lattice improved by adding long-range shortcuts with probability P(rij)?rij-?,where rij is the lattice distance between sites i and j,and a is a variable exponent.We study the mean first passage time(MFPT)and find that there exists a threshold probability pth,for p?pth the optimal transportation condition is obtained with an optimal transport exponent ?op= d,while for 0<p<pth,the value of ?op depends on p.Specially,when ?=?op,the MFPT may scale logarithmically with L for p>pth,and increases with L less than a power law and get close to logarithmical law for 0<p<pth.Our results indicate that the proper addition of shortcuts to a regular substrate can lead to a formation of complex network with a highly efficient structure for navigation although nodes hold null local information with a relatively large probability.Furthermore,We investigate random walk with a bias towards a target node in spatially embedded networks with total cost restriction and find that the best transportation condition is obtained with an exponent ? = d + 1 for all p.The special phenomena can be possibly explained by the theory of information entropy,we find that when?=d + 1,the spatial network with total cost restriction becomes an optimal network which has a maximum information entropy.