Acta Geographica Sinica ›› 2014, Vol. 69 ›› Issue (12): 1847-1857.doi: 10.11821/dlxb201412010

• Orginal Article • Previous Articles     Next Articles

Construction of Chinese aviation hub-spoke structure based on maximum leaf spanning tree

Minzheng XU1,2, Jun XU1(), Yu CHEN1   

  1. 1. Institute of Geographic Sciences and Natural Resources Research, CAS, Beijing 100101, China
    2. College of Resources and Environment, University of Chinese Academy of Sciences, Beijing 100049, China
  • Received:2013-09-06 Revised:2014-07-28 Online:2014-12-25 Published:2014-12-25
  • Supported by:
    National High Technology Research and Development Program of China, No.2012AA12A211, No.2012AA12A403;National Natural Science Foundation of China, No.41371380, No.41171296


Aviation hub-spoke structure is an important transportation network to achieve economies of scale development. As regards to its construction, most of methods are proposed by human geography scientists, whose efficiencies are affected by the authors' experience. In this paper, we present a novel graph method to extract hub-spoke structure from aviation network directly, which is more objective and efficient. Taking Chinese aviation network as a case study, we integrate a constraint distance into the conventional maximum leaf spanning tree algorithm to extract tree-shaped hub-spoke structure. The tree-shaped hub-spoke structure forms the branch airlines, and the top 10 degree nodes selected as aviation hubs are Beijing, Shanghai, Guangzhou, Chengdu, Urumqi, Kunming, Xi'an, Changsha, Harbin and Guiyang. The ten hubs dominate other non-hubs in different regions of China. For example, Urumqi dominates Northwest China and Shanghai dominates eastern China. The airlines among the hubs form the trunk airline network, which covers most of China's territory except the southwestern part because of lacking of a powerful hub. The aviation hub-spoke structure is generated by merging the branch airlines and the trunk airline network. Compared with the result of previous research, the hub selection of our method is more reasonable in some cases, such as selecting Harbin instead of Shenyang in Northeast China; the branch airlines and trunk airlines generated by our method have broader coverage; the division of branch and trunk airlines is more objective due to the use of constraint distance. In addition, our hub-spoke structure fits the real geographical situation better than the previous results. To sum up, the contributions of this paper are: (1) developing a novel maximum leaf spanning tree algorithm with distance constraint; (2) proposing a novel aviation hub-spoke structure construction method based on the algorithm; (3) applying the method to extract the hub-spoke structure of Chinese aviation in 2012, and it performs quite well.

Key words: Key works: hub-spoke, Chinese aviation network, maximum leaf spanning tree, distance constraint, graph theory