The Research And Application Of Path Optimization Issue For Complex Network

Since the end of last century, the research of complex networks has turned into anattractive subject for the rapid development of internet which is a representative ofinformation technology in human society. Due to its diverse applications in real world,complex network theory becomes an extremely important challenge of scientificresearch. Therefore, the further study for the complexity of the networks is in demandfor more thorough understanding of the networks in human life. Among a variety ofresearch areas of complex networks, search in complex networks is an open issue, lotsof practical problems are solved by the search theory of complex networks such as thesearch of the shortest relationship chain between any two people in social network,search of the pages in WWW and search of the specified data or files in P2P network.In order to solve these problems, many excellent algorithms have been proposedsuch as greedy algorithm (GA), random walk (RW) and high degree seeking (HDK)since the search capabilities of complex networks are proved by Kleinberg in2000.These conventional search algorithms achieved to send the message in the network,unfortunately, the search speed of these classic algorithms is not ideal and they aresuitable for specific networks due to their own defects. So as to increase the searchspeed and expand the scope of application of networks, this thesis presents two newsearch strategies for complex networks:1. High degree seeking with k steps which takes a few steps of random walk beforehigh degree seeking, ensures the advantages of the both two algorithms and expand thescope of application of networks.2. A novel k-walker search strategy for different types of complex networks whichsearches the networks with k walkers simultaneously and increase the speed of search.In this thesis, the brand new two algorithms will be described in detail, the pseudocode of them will be listed and instances will be illustrated to show the advantages. Thecomplexity analysis will be discussed and the comparison with other algorithms will bedisplayed in best, worst and average situation, the average case is particularly discussedin the regular, random, small world and scale-free networks. In the simulation, we willbuild WS, NW and BA model in different scale, and a new standard which considers search steps and query information both is put forward to measure the cost of the searchalgorithm. In the end, high degree seeking with k steps and a novel k-walker searchstrategy will run the simulations in three kinds of network model, the average searchsteps, query information and search cost are carried out and analyzed to illustrate theeffectiveness and efficiency of the proposed method.