A study on traffic dynamics on complex networks

Abstract

The traffic dynamic problem on complex networks is intriguing in recent years because of their significant importance on practical communication network systems. This thesis focuses on some improvement of high transport efficiency in different ways such as designing routing strategies and changing network topologies. In this thesis, we first perform parallel optimization for the traffic capacity and the average number of overall packets. Results indicate that homogeneous networks can support a large traffic capacity under the congestion-free state, but the networks must be able to sustain relatively heavy packet load pressure compared to the case that the same packet generation rate is assigned to a more heterogeneous network. At the same time, we also found that heterogeneous networks can relieve packet load pressure, but the networks are likely to become congested due to abrupt increases of packet loads. We found that when the network size is large, lowering the average number of packets and raising the traffic capacity need not to be compromised too much. We furthermore point out that networks can be more robust to abrupt increase of packet loads if networks are structured more homogeneously in the process of network size increment. We also investigate the combined effect of local and global topological ingredients for routing packets on transport efficiency in scale-free networks with different degree-distribution exponents. We propose an improved routing strategy with memory information, which is able to further enhance the traffic capacity, especially when packets are showing strong inclination of being forwarded to low-degree or high-degree nodes in scale-free networks with small degree-distribution exponents. We then propose an efficient link-removal strategy, called the variance-of-neighbor-degree-reduction (VNDR) strategy, for enhancing the traffic capacity of Barabási-Albert (BA) scale-free networks. The VNDR strategy is able to balance the amounts of packets routed from each node to the node’s neighbors in BA scale-free networks. Compared against the outcomes of strategies that remove links among hub nodes, our results show that the traffic capacity can be greatly enhanced, especially under the shortest path routing strategy. We also found that the average transport time is effectively reduced by using the VNDR strategy only under the shortest path routing strategy in BA scale-free networks. We moreover propose an efficient strategy to enhance traffic capacity via the process of nodes and links increment for BA scale-free networks. We show that by adding shortcut links to the existing networks, packets are avoided flowing through hub nodes. Our results show that using the proposed strategy, the traffic capacity can be effectively enhanced under the shortest path routing strategy. Under the local routing strategy, our results show that the proposed scheme is efficient only when packets are more likely to be forwarded to low-degree nodes in their routing paths. We finally propose a model incorporating both the traffic routing dynamics and the virus prevalence dynamics in BA scale-free networks. In this model, a packet may be isolated and removed from the network on its transporting paths. A successful transport means that a packet can be delivered from source to destination without being isolated. Effects of model parameters on the number of successful transports and the number of unsuccessful transports are intensely simulated and analyzed. Compared to some other routing strategies, the shortest path routing strategy is the most effective for increasing the number of successful transports, especially when packets are only delivered to neighbors with the lowest degrees along the shortest paths in BA scale-free networks.

Date of Award	15 Feb 2011
Original language	English
Awarding Institution	City University of Hong Kong
Supervisor	Wai Shing Tommy CHOW (Supervisor)