Research On Local Search In Complex Network

Over the past decade, the study of complex networks has emerged as a theme running through research in a wide range of areas. The study of complex networks’search strategy has the vital significance to the real life. The main study of the complex networks’search strategy is to find the shortest path from the source node to the target node. There are two different search strategies in the complex networks, which are global search strategy and local search strategy. The global search strategy means we need to know the global information of the networks in the process of searching so as to find the target node while the local search strategy means we need to know the local information in the process of searching so as to find the target node. In many real networks, single node cannot get the global information out of the network. Thus, the study of local search strategy has always been a key subject in this area.In this paper, we introduce the basic topological characteristics, topological models and search strategies in the complex networks, and then compare, analyse and evaluate the basic search strategies. On the basis of this, we investigate the search strategy in the complex networks from two different aspects and propose two local search strategies. The contributions of this paper are as follows:1. On the basis of deeply study on the relationships of clustering coefficient and small world network’s topology. We modify the definition of clustering coefficient, use clustering coefficient which describes the complex network’s structural characteristics to design the least clustering coefficient (LCC) search strategy; namely, the nodes with information select the nodes with the least clustering coefficient to pass message. Then we compare the least clustering coefficient search strategy, the high degree seeking search strategy with random walk search strategy. Through experiments we find that the LCC strategy has the best performance in small world networks.2. On account of many real networks have the metric space, we create a family of parameterized spatial scale-free models that are heterogeneous in node degree. Based on this, according to the model’s structural characteristics, we combine metric distance with degree which impacts the search performance to design a new search strategy, namely, the high degree low distance search strategy. Then we investigate high degree low distance search strategy and several search strategies. Through experiments, we find out that high degree low distance search strategy more suitable to the spatial scale-free models.