We propose a routing strategy to improve the transportation efficiency on complex networks. Instead of using the routing strategy for shortest path, we give a generalized routing algorithm to find the so-called efficient path, which considers the possible congestion in the nodes along actual paths. Since the nodes with the largest degree are very susceptible to traffic congestion, an effective way to improve traffic and control congestion, as our strategy, can be redistributing traffic load in central nodes to other noncentral nodes. Simulation results indicate that the network capability in processing traffic is improved more than 10 times by optimizing the efficient path, which is in good agreement with the analysis. DOI: 10.1103/PhysRevE.73.046108 PACS number͑s͒: 89.75.Hc Since the seminal work on scale-free networks by Barabási and Albert ͑BA model͒ ͓1͔ and on the small-world phenomenon by Watts and Strogatz ͓2͔, the structure and dynamics of complex networks have recently attracted a tremendous amount of interest and attention from the physics community ͑see the review papers ͓3-5͔ and references therein͒. The increasing importance of large communication networks such as the Internet ͓6͔, upon which our society survives, calls for the need for high efficiency in handling and delivering information. In this light, to find optimal strategies for traffic routing is one of the important issues we have to address. There have been many previous studies to understand and control traffic congestion on networks, with a basic assumption that the network has a homogeneous structure ͓7-11͔. However, many real networks display both scale-free and small-world features, and thus it is of great interest to study the effect of network topology on traffic flow and the effect of traffic on network evolution. Guimerá et al. present a formalism that can cope simultaneously with the searching and traffic dynamics in parallel transportation systems ͓12͔. This formalism can be used to optimize network structure under a local search algorithm, while to obtain the formalism one should know the global information of the whole networks. Holme and Kim provide an in-depth analysis on the vertex/edge overload cascading breakdowns based on evolving networks, and suggest a method to avoid such avalanches ͓13,14͔. By using a global and dynamical searching algorithm aimed at the shortest paths, Zhao et al. provide the theoretical estimates of the communication capacity ͓15͔. Since global information is usually unavailable in large-scale networks, Tadić et al. investigate the traffic dynamics on the WWW network model ͓16͔ based on local knowledge, providing insight into the relationship of global statistical properties and microscopic density fluctuations ͓17-19͔. The routing strategies for the Internet ͓20͔ and disordered networks ͓21͔ are also studied. Another interesting issue is the interplay of traffic dynamics and network structures, which suggests a new scenario of network evolutionary ͓22-26͔. In this context, for simplicity, we treat all the nodes as both hosts and routers ͓12,27͔. In communication networks, routers deliver data packets by ensuring that all converge to a best estimate of the path leading to each destination address. In other words, the routing process takes place according to the criterion of the shortest available path from a given source to its destination. When the network size N is not too large, it is possible to calculate all the shortest paths between any nodes, and thus the traffic system can use a fixed routing table to process information. As for any pair of source and destination, there may be several shortest paths between them. We randomly choose one of them and put it into the fixed routing table, which is followed by all the information packets. Though it becomes impractical in huge communication systems, the fixed routing algorithm is widely used in medium-sized or small systems ͓28,29͔. This is because the fixed routing method has obvious advantages in economical and technical costs, compared with the dynamical routing algorithm and information feedback mechanism. The model is described as follows: at each time step, there are R packets generated in the system, with randomly chosen sources and destinations. It is assumed that all the routers have the same capabilities in delivering and handling information packets, that is, at each time step all the nodes can deliver at most C packets one step toward their destinations according to the fixed routing table. We set C = 1 for simplicity. A packet, upon reaching its destination, is removed from the system. We are most interested in the critical value R c ͑as measured by the number of packets created within the network per unit time͒ where a phase transition takes place from free flow to congested traffic. This critical value can best reflect the maximum capability of a system handling its traffic. In particular, for R Ͻ R c , the numbers of created and delivered packets are balanced, leading to a steady free traffic flow. For R Ͼ R c , traffic congestion occurs as the number of accumulated packets increases with time, simply because the capacities of the nodes for delivering packets are limited. We use *Electronic address: zhutou@ustc.edu PHYSICAL REVIEW E 73, 046108 ͑2006͒
Betweenness centrality, which is widely used as a precise estimation of the information flow controlled by a vertex in social and information networks, assumes that information flow is done through shortest paths REF .
Efficient routing on complex networks
Phys. Rev. E 73, 046108 (2006)
Physics Medicine