Analysis of Hubs and Its Application to Complex Networks - from a Leveled Structure Perspective


Student thesis: Doctoral Thesis

View graph of relations


Related Research Unit(s)


Awarding Institution
Award date30 Oct 2018


According to the recent findings in complex network science, many real-world networks such as the World Wide Web (WWW), the Internet, social networks, etc, possess scale-free characteristics. In these networks, some hubs have relatively high centrality and therefore play more important roles than the other nodes.

The focus of this thesis is to study the role of hubs in complex networks, particularly regarding their nodal properties, performances, and applications. To carry out the study, a leveled structure framework (LSF) is introduced. The LSF consists of a hub level and other node level(s). It not only well represents the structure of a network from a hub-centered view, but also provides a good way to quantify the performance of hubs. What is more, LSF can enlighten innovative applications of real-world complex networks.

Based on LSF, studies in this thesis primarily concentrates on the Internet (both inter-domain and intra-domain), social networks, and transportation networks. Studies on the Internet firstly fairly demonstrates the benefits of scale-free properties of the Internet by comparing it with dk-random networks. Then, LSF reveals the notable contributions of Internet eXchange Points (IXPs), which are deemed as hubs in the inter-domain Internet.

For the intra-domain Internet, an innovative broadcast mechanism, namely relay-based broadcast (RB) is designed by utilizing hubs. Under RB, information is forwarded to one of the relays and then re-disseminated to others through a spanning tree whose root is the relay. RB can significantly reduce the amount of transmission overhead by sacrificing little convergence speed.

Studies of hubs on social networks is based on a newly proposed naming game, called likelihood category game model (LCGM). In the LCGM, self-organized agents can define categories based on acquired knowledge through learning from each other and use likelihood estimation to distinguish objects. The information communicated among agents is no longer simply in some form of absolute answer, but involves one’s perception. Based on LCGM, the performances of agents during the consensus process are quantified. It reveals that hubs do not outperform other agents although they have some advantages from certain perspectives. In addition, LSF demonstrates that the overall information flow is from hubs to leaves on a network.

Lastly, the thesis investigates how hubs can facilitate the operation for express delivery. Under the framework of hub and spoke (HaS), a variant of LSF, the delivery cost in hub level is supposed to be discounted due to the reduction of marginal cost. In addition, a modified NSGA-II algorithm is designed to solve the hub location problem (HLP), which is critical to express delivery. The effectiveness of the algorithm is verified by simulations based on a China transportation network.