As an increasing number of countries liberalize their skies, some airlines, notably carriers in the Middle East, have been able to extend their hub-and-spoke networks beyond domestic borders. This allows them to serve international destinations without going through traditional gateway hubs, so that they can compete with airline alliances relying on the traditional dual-gateway, or the so-called “dog-bone” networks. This paper proposes a stochastic model to investigate the competition between airlines running traditional dog-bone and hub-and-spoke networks in a liberalizing inter-continental market. The proposed model considers the interactions among three types of stakeholders, namely a regulator that aims to maximize the expected social welfare by designating the locations of new gateways; airlines that maximize profits by optimizing the service offerings and airfares; passengers that minimize their own travel disutility. Such a model is applied to analyze the Europe - China aviation market, so that the comparative advantages of different networks can be examined and quantified. The modeling results provide evidence-based recommendations on airline competition and airport development, and infrastructure investment needs in markets being liberlized.