Random Walk On Complex Networks

Complex networks can describe the structure of some complex systems, such as the Internet, World Wide Web, scientist’s collaboration networks and neural networks. In recent years, the study of complex networks shows that real networks are not random networks. An important characteristic is that a few nodes have a large number of connections, most nodes have very few connections, and degrees follows the power law. We call this kind of the networks scale-free networks. One more characteristic of the real networks is that:the node connectivity is correlated. If nodes tend to connect to nodes with similar connection degree, the network is called association network. If nodes with larger connection degree tend to nodes with small degree, the network is called disassociation network. World Wide Web, Internet and other communication networks are disassociation scale-free networks.Random walk is an effective method to solve the problems in real networks, such as the congestion problem of data packes in the information transmission. The investigation of the random walk in the complex network model enables us to find the effective routing method. At present, the routing method is the shortest path strategy. The drawbacks of this strategy are that the node with the largest degree could be plugged easily. An alternative strategy is the local routing strategy, in which each node only knows the information of their neighbor nodes. Data packets are transmitted from a node to the nearest neighbor node according to certain rules. This process repeats until the package reaches the destination node. This method can overcome the disadvantages of the shortest path strategy, and has attracted a great deal of interest.Abiased random walk is an effective way to study the local data packet routing strategy. Previous works have investigated the random walk on uncorrelated scale-free networks. Since many real networks, including the Internet, are disassociate networks, this paper focuses on studying the biased random walk on such networks.In this paper, we have shown that the random walk particles can be uniformly distributed over the node with large degree on the disassociate networks, and the nodes with smaller degree have less particles. Random walk on the disassociation network is faster than on degree uncorrelated networks. We have found the best biased coefficient on the disassociation networks, and the random walk is much faster than that on the uncorrelated network in this case. Results presented in this paper suggest that the disassociation network not only utilize the nodes with small degree to contain particles but also utilize nodes with large degree to effectively transmit particles, which is the mechanism that governs the high efficiency of the disassociate networks.