Algebraic Connectivity Maximization for Air Transportation Networks

Abstract

It is necessary to design a robust air transportation network. An experiment based on the real air transportation network is performed to show that algebraic connectivity is a fair measure for network robustness under random failures. Therefor, the goal of this paper is to maximize algebraic connectivity. Some researchers solve the maximization of the algebraic connectivity by choosing the weights for the edges in the graph. Others focus on the best way to add edges in a network in order to optimize the connectivity. In this paper, the authors formulate a new air transportation network model and show that the corresponding algebraic connectivity optimization problem is interesting because the two subproblems of adding edges and choosing edge weights cannot be treated separately. The new problem is formulated and exactly solved in a small air transportation network case. The authors also propose the approximation algorithm in order to achieve better efficiency. For large networks, the semidefinite programming with cluster decomposition is first presented. Moreover, the algebraic connectivity maximization for directed networks is discussed. Simulations are performed for a small-scale case, large-scale problem, and directed network problem.