- Email: [email protected]

Contents lists available at ScienceDirect

Physica A journal homepage: www.elsevier.com/locate/physa

Routing in scale-free networks based on expanding betweenness centrality✩ Zhi-Hong Guan a,∗ , Long Chen a , Tong-Hui Qian b a

Department of Control Science and Engineering, Huazhong University of Science and Technology, Wuhan, 430074, PR China

b

School of Physics and Information Engineering, Jianghan University, Wuhan, 430056, PR China

article

info

Article history: Received 1 July 2010 Received in revised form 28 September 2010 Available online 7 November 2010 Keywords: Routing strategy Expanding betweenness centrality Traffic capacity Scale-free networks

abstract In this paper, an improved routing strategy is proposed for enhancing the traffic capacity of scale-free networks. Instead of using the information of degree and betweenness centrality, the new algorithm is derived on the basis of the expanding betweenness centrality of nodes, which gives an estimate of the traffic handled by the vertex for a certain route set. Since the nodes with large betweenness centrality are more susceptible to traffic congestion, the traffic can be improved by redistributing traffic loads from nodes with large betweenness centrality to nodes with small betweenness centrality in the process of computing the collective routing table. Comparing with results of previous routing strategies, it is shown that the present improved routing performs more effectively. © 2010 Elsevier B.V. All rights reserved.

1. Introduction Since the scale-free [1] and small-world [2] properties were identified, complex networks have been applied with success to describe a wide range of natural and social systems in which entities or people are connected by physical links or some abstract relationship. The study of dynamical processes taking place in complex network systems, such as the flow of information [3–5], traffic dynamics of information packets [6–10], synchronization dynamics [11–15], navigation [16–25], search ability [26–34] and so on [35–37], has attracted growing interest among the community of physicists. The traffic on a network, which is fundamental to large networked systems, is one of the hot topics of recent research on complex networks. Congestion pheromones on complex networks have been widely studied in the past few years [6–8]. It is found that there is a phase transition from free flow to congestion, while the number of packets created within the network per unit time grows gradually. There are two general ways to raise the critical packet generation rate where the phase transition takes place: to increase the capacity of each node and to improve the routing protocol. The former is less practical as it is usually difficult and costly to reorganize or adjust an extant network, such as the Internet. By contrast, it is more inexpensive and more convenient to alter the routing protocol [38–45]. As finding the global optimal routing protocol is proved to be an NP problem [38], a series of heuristics algorithms have already been proposed for enhancing the traffic capacity of networks. Yan et al. presented a variation of the shortest path routing protocol for enhancing the congestion threshold, which includes the degree information [39]. Wang et al. proposed a routing strategy with a tunable parameter based on threshold local structure information [40]. Echenique et al. designed a local algorithm named the traffic awareness protocol, which includes the number information of accumulated packets at nodes [41]. Tang et al. considered the effects of time-varying packet generation rates in the performance of communication

✩ This research was partly supported by the National Natural Science Foundation of China under Grants 60873021, 60973039, 60973012, 61073026 and 61073025. ∗ Corresponding author. Tel.: +86 27 87542145; fax: +86 27 87542145. E-mail address: [email protected] (Z.-H. Guan).

0378-4371/$ – see front matter © 2010 Elsevier B.V. All rights reserved. doi:10.1016/j.physa.2010.10.002

1132

Z.-H. Guan et al. / Physica A 390 (2011) 1131–1138

networks, and gave a modified traffic awareness protocol [42]. Ling et al. proposed a routing strategy for network systems based on the local information of the ‘‘pheromone’’ [43]. Danila et al. gave a collectively optimal routing for congested traffic limited by link capacity, by using routes that minimize the maximum ratio of betweenness to capacity in any link [45]. In this paper, we extend a collective static routing strategy on the basis of some variations of the shortest path routing protocol. It is known that both the node with high degree and the node with large betweenness, which is strongly dependent on the special routing protocol, are very susceptible to traffic congestion. So as to avoid congestion, the efficient routing algorithm in Ref. [39] aims to reduce traffic loads of nodes with large degree, while the optimal routing protocol in Ref. [44] balances traffic by minimizing the maximum node betweenness. Using these routing protocols, a network can sustain significantly higher traffic without jamming than in the case of traditional shortest path routing. But we find that one can enhance traffic capacity more by using a routing protocol based on the expanding betweenness of nodes, which is defined in Section 2. The routing protocol proposed here can perform effectively in the case where there is more than one path between two central nodes, which is common in complex networks. We give theoretical analysis from the angle of the structure of the network in the following sections. And the formulation demonstrates that the present routing protocol is better than the previous routings as regards handling and delivering information in large networked systems. The paper is organized as follows. In the next section, the underlying network model and the traffic model are introduced. Section 3 gives the simulation results for the improved routing strategy. The paper is concluded in Section 4. 2. The routing strategy For the network transport dynamics considered in this paper, particles are assumed to travel along the network according to static routing protocols. The number of nodes on the network is denoted by N. It is assumed that each node has a separate ‘‘first in, first out’’ particle queue, and the node v can deliver or handle at most Cv particles at each time step. For the sake of contrast, the transferring capacity of each node is fixed to 1 in this paper (Cv ≡ C = 1), while it can be adjusted easily so as to meet the demands of various cases, such as networks with a heterogeneous distribution of node capacities. Transport on the network proceeds in discrete time steps and is driven by inserting R new particles per time step at the nodes with randomly chosen sources and destinations. Each new particle is inserted at the end of the appropriate queue at its node of origin. And at each time step, every node delivers the packets there one step toward their destinations according to the fixed routing table calculated by using the given routing protocol. The load of the network is defined as the average ⟨R⟩ on the network. The transportation capability of the network is the critical value of the load Rc where a phase transition takes place from free flow to congested traffic. When the packet generation rate is above Rc , there is accumulation in the network and the transport becomes jammed. Recent studies [9,44] have reported that betweenness centrality plays an important role in the traffic on a network. For a given network, the betweenness centrality (BC) of a node is defined as Bi =

− σst (i) s̸=t

σst

,

(1)

where σst is the number of shortest paths going from s to t; and σst (i) is the number of shortest paths going from s to t and passing through i. The average number of packets passing through a given node is then RBi /N (N − 1). Therefore, a particular node will collapse when RBi /N (N − 1) > Ci . Since the transferring capacity of each node is fixed to 1 in this paper, Rc is given by [9,39] Rc = N (N − 1)/Bmax ,

(2)

where Bmax is the largest BC of any node on the network. Thus, to achieve optimal routing, the highest betweenness should be minimized. With the minimization, the algorithm will implicitly reshape the betweenness distribution of the whole network, by reducing traffic through the initially busy nodes at the expense of increased traffic through the initially idle nodes. The betweenness distribution will be as narrow as possible to make traffic congestion minimum [10]. There have been some static routing protocols proposed for enhancing the traffic capacity of networks, such as the efficient routing protocol proposed by Yan et al. [39] and the optimal routing protocol given by Danila et al. [44]. The efficient β routing algorithm sets a weight ki on each outgoing arc of node i, where ki is the degree of node i, and β is an adjustable parameter. And then the routing table can be attained by computing the weighted shortest paths between all pairs of nodes. The optimal routing algorithm first assigns weight 2 to every link and then adds 1 to the weight of every link connected to the node with highest betweenness until the highest betweenness cannot be reduced more. Both of these perform well at bypassing busy nodes, better than the traditional routing protocols, such as the original shortest path routing. But we find that they cannot handle the traffic between central nodes to the best advantage. When the paths between two central nodes number more than 1, the existing routings only choose one optimal path in accordance with their measurements. Since the optimal structure for minimizing traffic congestion should have a uniform distribution of load over all nodes [10], can we allocate the load to these paths to reduce the highest betweenness of nodes? In this paper we propose a collective protocol based on expanding betweenness to deal with the problem. To introduce the new routing strategy, we extend the concept of betweenness centrality from the whole routing table to an incomplete route set which consists of some paths between several nodes in the network. Similarly the expanding betweenness of node for a certain route set is defined as

Z.-H. Guan et al. / Physica A 390 (2011) 1131–1138

bi =

− σstϕ (i) ϕ

σst

s̸=t

,

1133

(3)

ϕ

ϕ

where σst is the number of paths going from s to t in the route set ϕ ; and σst (i) is the number of paths going from s to t and passing through i in the set ϕ . The expanding betweenness gives an estimate of the traffic handled by the vertex in the route set. Obviously, when the route set includes paths between any pair of nodes in the network, the expanding betweenness will degenerate to the conventional betweenness. On the basis of the information of expanding betweenness centrality of nodes, for any path from node i to node j such as P (i → j) := i ≡ x0 , x1 , . . . , xn−1 , xn ≡ j, we define L(ϕ) (P (i → j)) =

n−1 −

bαxi ,

(4)

i=0

where α is an adjustable parameter, and bxi is the expanding betweenness centrality of node xi for the current route set ϕ . The expected path between i and j for the route set ϕ corresponds to the route that makes the sum L(ϕ) (P (i → j)) minimum. If there are several expected paths between two nodes, one is chosen at random. The algorithm is given as follows: 1. Set the current route set ϕ = ϕ0 = φ , which means that there is no path in the current route set. The expanding betweenness of each node is initialized as 1. Number nodes of the network as 1, 2, . . . , N − 1, N, and initialize v = 1. (It is discussed later how the order of nodes influences the traffic capacity. The natural order is chosen for a BA network by default. In this order, a node will be marked with a high ID if it is added to the network late.) 2. Compute the expected paths from node v to others under the current router set ϕ . 3. Add the expected paths from v to (N − 1) other nodes to the route set ϕv−1 and name the new set as ϕv . Then alter the expanding betweenness of each node for the current route set, ϕ = ϕv . 4. If v < N, set v = v + 1, and go back to step 2. If v = N, the current route set ϕ = ϕN is the final route table. The key of the algorithm is the iterative processing of the weight parameter bi . By choosing the optimal paths under variable weights, the traffic can be routed around the nodes that are most likely to jam, comparatively, and the load distribution can be more uniform. Obviously, the new algorithm is equal to the traditional shortest path routing when α = 0. For various values of α , we are interested in addressing how the traffic changes and finding the optimal parameter. It is worth mentioning that the algorithm’s running time is O(N 3 ) (O(N 2 ) for one iteration, and requiring N iterations), which is the same as for the efficient routing strategy, while the optimal routing’s running time is O(N 4 ). 3. Simulation In this section, we give the simulation results for the new routing algorithm on BA scale-free networks. In order to describe the phase transition of the traffic flow in the network, we adopt the order parameter [39] C ⟨1W ⟩

, (5) 1t where 1W = W (t + 1t ) − W (t ), with ⟨· · ·⟩ indicating the average over time windows of width 1t, and W (t ) is the total number of packets in the network at time t. For R < Rc , H (R) remains at zero, indicating that the system is in the free-flow state. With increase in the packet generation rate R, there will be a value of Rc at which H (R) increases from zero, H (R) = lim

t →∞

R

indicating that the packets accumulate in the system, and the system becomes seriously congested. Therefore, Rc is the maximal generating rate under which the system can maintain its normal and efficient functioning. In Fig. 1, we report the simulation result for the critical value as a function of α on BA networks (N = 400) with different average degrees. It can be seen that Rc first increases promptly with α and then decreases slowly on networks with a certain average degree. And the optimal α decreases with the average degree (⟨k⟩ ≈ 2m) of the networks. In Fig. 2, the typical variation of H (R) against R is shown for the improved routing under optimal α for networks with different average degrees; it is consistent with the analysis. This result illustrates the effectiveness of the routing strategy based on the expanding betweenness centrality. Fig. 3 shows the variation of Rc on networks with different average degrees for four routing strategies, which are the shortest path routing (SP), the efficient routing (ER), the optimal routing (OR) and the improved routing (IR). Obviously, the capacity of the network in freely handling information is greatly enhanced by the improved routing. And the bigger the average degree is, the more the capacity can be enhanced. This can be explained easily because there are more paths between central nodes; the improved routing can distribute the load among more different paths to avoid nodes with too large a load. In Figs. 4–6, we compare the performances of the four routing strategies on networks with m = 5 (which means ⟨k⟩ ≈ 10), respectively showing Rc versus N, average actual path length versus N and running time versus N. It can be seen that the improved routing enhances the traffic capacity greatly, while it increases the average actual path length a little. Such a sacrifice is worthwhile when a system requires a large Rc . Compared with the optimal routing, the new routing

1134

Z.-H. Guan et al. / Physica A 390 (2011) 1131–1138

Fig. 1. The critical value Rc versus parameter α for different values of m: 2, 4, 5, 7, 10 on BA networks with N = 400, using the improved routing.

Fig. 2. Order parameter H versus rate R of generation of packets for different values of m: 2, 4, 5, 7, 10 on BA networks with N = 400, using the improved routing.

Fig. 3. The critical value Rc versus parameter m of BA networks with N = 400, for the shortest path routing (SP), the efficient routing (ER), the optimal routing (OR) and the improved routing (IR).

Z.-H. Guan et al. / Physica A 390 (2011) 1131–1138

1135

Fig. 4. The critical value Rc versus network scale N, for the shortest path routing (SP), the efficient routing (ER), the optimal routing (OR) and the improved routing (IR). m0 = m = 5.

Fig. 5. The actual average path length ⟨L⟩ versus the network scale N, for the shortest path routing (SP), the efficient routing (ER), the optimal routing (OR) and the improved routing (IR). m0 = m = 5.

needs much less running time (although it is a little bigger than for the traditional shortest path routing); therefore, it is easier to implement in actual cases. As the maximum of the betweenness plays an important role in traffic dynamics on complex networks, both the optimal routing and the improved routing aim to enhance the traffic capacity of networks based on the betweenness centrality of nodes. Fig. 7 shows the betweenness plotted against the vertex index under the shortest path routing, the efficient routing, the optimal routing and the improved routing. One can see that the routing protocol results in all node betweenness being confined to a narrow band. To check the influence of the orders of nodes on the improved routing, we show how the maximum of the expanding betweenness changes versus the number of iterations for the improved routing with different orders of nodes in a network with 800 nodes, in Fig. 8. It can be seen that the improved routing performs best when the nodes are in descending order of degree. As bmax increases with the number of computed nodes nearly linearly under our routing algorithm, the improved routing algorithm can be used effectively and conveniently in heterogeneous networks, where there are some nodes which do not generate information packets and only work as routers or receivers. We only need to compute the routes from nodes which work as information sources to other nodes. The computational complexity decreases and the traffic capacity increases simultaneously. 4. Conclusions In summary, we have proposed a collective routing protocol for complex networks based on the expanding betweenness centrality of nodes and then investigated the traffic dynamics on complex networks, in which the capabilities of processing

1136

Z.-H. Guan et al. / Physica A 390 (2011) 1131–1138

Fig. 6. The running time agreement network scale N, for the shortest path routing (SP), the efficient routing (ER), the optimal routing (OR) and the improved routing (IR). m0 = m = 5.

Fig. 7. Distribution of node betweenness for four different routing strategies, for network size N = 800, m0 = m = 5.

information are the same for all the nodes. As a large system can be divided into several autonomous subsystems in which every subsystem has its local topological knowledge, the hierarchical structure of the network will make possible the implementation of our routing strategy. Among the routing protocols using collective information on the topology, the improved routing protocol performs best with least computational complexity. This is a nontrivial improvement in the network traffic area. In this routing strategy, by using the information of the expanding betweenness centralities of nodes, the node where congestion is most likely can be rounded, and the traffic load distribution can be more uniform. The routing strategy can reach the largest traffic capacity with the fastest computed speed. Because of its features, the routing algorithm can be used effectively and conveniently not only in homogeneous networks but also in heterogeneous networks, where there are some

1137

bmax

degree k

Z.-H. Guan et al. / Physica A 390 (2011) 1131–1138

bmax

bmax

iterations for ascending order

iterations for natural order

iterations for descending order

Fig. 8. Maximum betweenness as a function of the number of iterations for different orders of nodes, with network size N = 800, m0 = m = 5.

nodes which only work as routers and receivers. The study can be useful for the design and optimization of routing strategies in some real traffic systems such as the urban transportation systems, peer-to-peer networks, wireless sensor networks, and so on. References [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35]

A.-L. Barabasi, R. Albert, Science 286 (1999) 509. D.J. Watts, S.H. Strogatz, Nature 393 (1998) 440. M. Anghel, Z. Toroczkai, K.E. Bassler, G. Korniss, Physical Review Letters 92 (2004) 058701. D.O. Cajueiro, R.S. DeCamargo, Physics Letters A 355 (2006) 280. B.A. Mello, L.H. Batistuta, R. Boueri, D.O. Cajueiro, Physics Letters A 28 (2009) 126. T. Ohira, R. Sawatari, Physical Review E 58 (1998) 193. L. Zhao, Y.C. Lai, K. Park, N. Ye, Physical Review E 71 (2005) 026125. D.D. Martino, L. Dall’Asta, G. Bianconi, M. Marsili, Physical Review E 79 (2009) 015101. R. Guimera, A. Diaz-Guilera, F. Vega-Redondo, A. Cabrales, A. Arenas, Physical Review Letters 89 (2002) 248701. L. Zhao, T.H. Cupertino, K. Park, Y.C. Lai, X.G. Jin, Chaos 17 (2007) 043103. M. Timme, F. Wolf, T. Geisel, Physical Review Letters 89 (2002) 258701. C.G. Li, G.R. Chen, Physica A 343 (2004) 263. Z.H. Guan, Z.W. Liu, G. Feng, Y.W. Wang, IEEE Transactions on Circuits and Systems I 57 (2010) 2182. M. Timme, F. Wolf, T. Geisel, Physical Review Letters 92 (2004) 074101. M. Chavez, D.U. Hwang, A. Amann, H.G.E. Hentschel, S. Boccaletti, Physical Review Letters 94 (2005) 218701. B. Tadic, European Physical Journal B 23 (2001) 221. J.D. Noh, H. Rieger, Physical Review Letters 92 (2004) 118701. K. Sneppen, A. Trusina, M. Rosvall, Europhysics Letters 69 (2005) 853. M. Rosvall, A. Trusina, P. Minnhagen, K. Sneppen, Physical Review Letters 94 (2005) 028701. M. Rosvall, P. Minnhagen, K. Sneppen, Physical Review E 71 (2005) 066111. A. Trusina, M. Rosvall, K. Sneppen, Physical Review Letters 94 (2005) 238701. D.O. Cajueiro, Physical Review E 79 (2009) 046103. S.J. Yang, Physical Review E 71 (2005) 016107. L.F. Costa, G. Travieso, Physical Review E 75 (2007) 016102. D.O. Cajueiro, Physica A 389 (2010) 1945. D.J. Watts, P.S. Dodds, M.E.J. Newman, Science 296 (2002) 1302. M. Rosvall, A. Gronlund, P. Minnhagen, K. Sneppen, Physical Review E 72 (2005) 046117. H.P. Thadakamalla, R. Albert, S.R.T. Kumara, Physical Review E 72 (2005) 066128. S. Carmi, R. Cohen, D. Dolev, Europhysics Letters 74 (2006) 1102. J.Z. Chen, W. Liu, J.Y. Zhu, Physical Review E 73 (2006) 056111. O. Simsek, D. Jensen, Proceedings of the National Academy of Sciences of the United States of America 105 (2008) 12759. R. Guimera, A. Diaz-Guilera, F. Vega-Redondo, A. Cabrales, A. Arenas, Physical Review Letters 89 (2002) 248701. T. Zhou, Physica A 387 (2008) 3025. D.O. Cajueiro, R.F.S. Andrade, Europhysics Letters 87 (2009) 58004. S. Boccaletti, V. Latora, Y. Moreno, M. Chavez, D.U. Hwang, Physics Reports 424 (2006) 175.

1138 [36] [37] [38] [39] [40] [41] [42] [43] [44] [45]

Z.-H. Guan et al. / Physica A 390 (2011) 1131–1138 A. Arenas, A. Diaz-Guilera, J. Kurths, Y. Moreno, C. Zhou, Physics Reports 469 (2008) 93. M. Newman, Physical Review E 64 (2001) 039906. T.N. Bui, C. Jones, Information Processing Letters 42 (1992) 153. G. Yan, T. Zhou, B. Hu, Z.Q. Fu, B.H. Wang, Physical Review E 73 (2006) 046108. W.X. Wang, B.H. Wang, C.Y. Yin, Y.B. Xie, T. Zhou, Physical Review E 73 (2006) 026111. P. Echenique, J. Gomez-Gardenes, Y. Moreno, Physical Review E 70 (2004) 056105. M. Tang, Z.H. Liu, X.M. Liang, P.M. Hui, Physical Review E 80 (2009) 026114. X. Ling, M.B. Hu, R. Jiang, R.L. Wang, X.B. Cao, Q.S. Wu, Physical Review E 80 (2009) 066110. B. Danila, Y. Yu, J.A. Marsh, K.E. Bassler, Physical Review E 74 (2006) 046106. B. Danila, Y.D. Sun, K.E. Bassler, Physical Review E 80 (2009) 066116.