Zhang Xiaohang, Zhang Zecong, Zhao Han, Wang Qi, Zhu Ji
School of Economics and Management, Beijing University of Posts and Telecommunications, Beijing, China.
Department of Statistics, University of Michigan, Ann Arbor, Michigan, United States of America.
PLoS One. 2014 Jun 17;9(6):e100428. doi: 10.1371/journal.pone.0100428. eCollection 2014.
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. In this study, 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. 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.
复杂网络是表示和分析复杂系统的有用工具，如万维网和交通系统。然而，复杂网络规模的不断扩大正成为理解其拓扑结构及其特征的障碍。在本研究中，提出了一种全局和局部自适应网络骨干（GLANB）提取方法。GLANB方法利用最短路径中链路的参与度和统计假设来评估链路的统计重要性；然后，基于统计重要性，通过过滤不太重要的链路并保留更重要的链路，从网络中提取骨干；结果是一个具有较少链路和节点的提取子网。GLANB通过综合考虑拓扑结构、链路权重和节点度来确定链路的重要性。权重小但从拓扑结构角度来看很重要的链路不会被轻视。GLANB方法可应用于所有类型的网络，无论它们是加权的还是未加权的，也无论它们是有向的还是无向的。对四个真实网络的实验表明，GLANB方法给出的链路重要性分布呈双峰形状，这对链路进行了稳健的分类；此外，GLANB方法倾向于将通过k壳算法确定为网络核心的节点放入骨干中。该方法可以帮助我们更好地理解网络结构，确定哪些链路对于信息传输很重要，并轻松地用骨干来表示网络。
