A Study Of Methods Of Extracting The Backbone In Complex Networks

A complex network is a useful tool for representing and analyzing complex systems, such as the world-wide web and transportation systems. However, the growing size of complex networks is becoming an obstacle to the understanding of the topological structure and their characteristics.First of all, we review eight methods that can detect and rank critical links in complex networks, and analyze the applicability and limitations of these methods. Furthermore, we apply these methods to four real-world networks of different domains; then we compare the distributions of these link importance measures, analyze the size of the backbones extracted by the methods, and reveal the correlative relationships between the methods.After reviewing eight methods, a globally and locally adaptive network backbone (GLANB) extraction method is proposed. The GLANB method uses the involvement of links in shortest paths and a statistical hypothesis to evaluate the statistical importance of the links; then it extracts the backbone, based on the statistical importance, from the network by filtering the less important links and preserving the more important links; the result is an extracted subnetwork with fewer links and nodes. The GLANB determines the importance of the links by synthetically considering the topological structure, the weights of the links and the degrees of the nodes. The links that have a small weight but are important from the view of topological structure are not belittled. The GLANB method can be applied to all types of networks regardless of whether they are weighted or unweighted and regardless of whether they are directed or undirected. The experiments on four real networks show that the link importance distribution given by the GLANB method has a bimodal shape, which gives a robust classification of the links; moreover, the GLANB method tends to put the nodes that are identified as the core of the network by the k-shell algorithm into the backbone.In conclusion, this method can help us to understand the structure of the networks better, to determine what links are important for transferring information, and to express the network by a backbone easily.