Exploring Complex Networks By Random Graph Evolution And Random Walks

In recent years,complex networks attract extensive attention from variousfields of science and engineering.In this dissertation, we apply the theory ofstochastics and method of numerical computation to investigate a number ofproblems in complex networks. The main work is to study two dynamicallyevolving random graphs and random walks on complex networks,which can helpto deeply understand network topological structures,dynamical processes on itand the relationship between them .In details, the main contents of the disserta-tion are summarized as follows:1. A mixing evolving model of power law graph is proposed.The evolutionof real-world networks doesn't follow a single mechanism.In order to understanddi?erent in?uences of preferential attachment and other mechanisms in networkevolution,we study a dynamically evolving random graph which adds vertices andedges using both preferential and uniform attachment. We prove that its degreedistribution obeys power law. Comparing to the random graph with only uniformattachment that gives geometric distribution, the degree distribution of the modelin this dissertation is dominated by preferential attachment. Simulations confirmour analysis and get further results.2. A kind of random network model generated by random graph processis constructed.Taking into account the time evolution characteristic of complexnetworks,we study a kind of simple random graph evolution model.By recursionand generating function,we investigate the probability distributions and expec-tations of the order and size of the evolving random network,as well as networksparsity.Corresponding formulas are obtained,through which we can understandthe statistical characteristics of network evolution.3. Preferential random walks on complex networks are studied by using ran-dom walks on weighted graphs.We investigate preferential random walks(PRW)on complex networks and derive two exact expressions for the mean first passage time(MFPT) between two nodes.We introduce for each node the center productdegree and show that it determines essentially the MFPT of the PRW.Meanwhile,wecarry out comparative studies of simple random walks(SRW). We found that, assearch strategies,the average search steps of the two random walks have similarscaling behaviour,while utterly di?erent from high-dgree search strategy.Numericalsimulations of an ensemble of random walkers moving on paradigmatic networkmodels confirm the above analytical predictions.Our studies show that randomwalks on complex networks can reveal a variety of characteristics of the underlyingnetwork, such as assortativity,heterogeneity of degree distribution, etc.4. Some theoretical and technological problems with relation to multiplerandom walks on complex networks are investigated.We mainly discuss the be-haviors of the first and last arriving particles when all the particles start outfrom the same source simultaneously and head to the same destination ran-domly.We analyze the first passage time(FPT)and the MFPT of multiple prefer-ential random walks(MPRW),making comparative studies of multiple simple ran-dom walks(MSRW). By using the transfer matrix and order statistics,we explorethe FPT of the first and last arriving particles and derive the corresponding equa-tions of the probability distribution ,the joint distribution, moments as well.Wealso show the convergence of the MFPT of the first arriving particle and findthe MFPT of the last arriving particle closely related with the cover time.On avariety of commonly encountered networks, we observe first passage properties ofmultiple random walks from di?erent aspects. Simulations confirm our analysis.Based on theoretical studies, we also investigate some practical problems usingMPRW and MSRW, such as communication on P2P networks, optimal routingin Ad hoc networks, phenomenon of asymmetry in scale-free networks, etc.