Hierarchical construction of multi-star small-world networks for real-world applications

Abstract

We proposed a new Small-World network (called n-Star network in which average path-length L becomes absolutely small) inspired by ants’ collective behavior. As one of the real-world applications using this network, it is shown that reorganization of the world airline network is possible in the next generation. In addition, it not only has the characteristic that is more immune from random failure and resilient to targeted attacks than bimodal degree distribution network and scale-free network, but also it can maintain Small-World characteristics even when probability of failure is considerably large. Furthermore, the n-Star network can be extended to various types of hierarchical networks, and we performed theoretical analysis of each network structure and derived formulas using various network parameters such as average degree hki, average path-length L, clustering coefficient C and newly analyzed assortativity (degree correlation) r with the number of star nodes n, their peripheral nodes N0, the total number of nodes N and the level of hierarchy l. We newly discuss the merit and demerit on the current airline network and an airline network based on the n-Star network, and propose a hierarchical architecture of airline network more suitable for real world than both the current airline network and the basic (non-hierarchical) n-Star-based airline network.