抽取复杂网络中的骨干结构的方法研究
发布时间：2019-01-13 07:12
【摘要】：复杂网络是代表和分析复杂系统(例如万维网和交通运输系统)的一种有用的工具。但是,随着复杂网络体量的增长,理解网络的拓扑结构和它们的特征变得越来越困难。 在本文中,我们首先回顾了8种用于检测并且可以排序网络中关键边的方法,并分析这些方法的适用性与局限性。接着,我们将这些方法应用于4个真实世界的网络,我们比较各个方法得出的边重要性的分布、抽取的骨干结构的大小,揭示方法之间的相关性。在比较了8种方法之后,我们提出了一种全局和局部自适应的骨干结构抽取方法(GLANB)。GLANB方法利用基于最短路径的边参与度和统计假设来评估边的统计重要性；然后GLANB方法利用边的统计重要性来保留更重要的边,以此抽取骨干结构,骨干结构是抽取后的有更少的节点和边的子网络。GLANB方法通过综合的考虑网络的拓扑结构、边的权重和节点度来决定边的重要性,那些权重较小但在拓扑结构中起到重要作用的边不会被轻视。GLANB方法可以被应用到所有类型的网络,包括加权/无权和有向/无向网络。四个真实网络的实证研究表明GLANB方法提出的边重要性分布是双峰的,因此可以得到边的鲁棒性分类。进一步地,GLANB方法倾向于将k-壳分解中网络中心的节点保留在骨干结构中。 综上所述,GLANB方法可以帮助我们更好的理解网络的结构,决定在信息传递中起关键作用的边,并且通过骨干结构的方式更方便的传递网络所表达的信息。
[Abstract]:Complex networks are a useful tool for representing and analyzing complex systems, such as the World wide Web and transport systems. However, as the volume of complex networks increases, it becomes more and more difficult to understand the topology and their characteristics of networks. In this paper, we first review eight methods used to detect and sort critical edges in a network, and analyze their applicability and limitations. Then we apply these methods to four real-world networks. We compare the distribution of edge importance and the size of the extracted backbone structure to reveal the correlation between the methods. After comparing the eight methods, we propose a global and local adaptive backbone structure extraction method (GLANB). GLANB) to evaluate the statistical importance of edges by using the shortest path based edge participation and statistical assumptions. Then the GLANB method uses the statistical importance of edges to retain more important edges to extract the backbone structure, which is the extracted sub-network with fewer nodes and edges. The GLANB method considers the topological structure of the network synthetically. The importance of edges is determined by the weight of edges and the degree of nodes. The edges with small weights but which play an important role in topology can not be ignored. The GLANB method can be applied to all types of networks, including weighted / unauthorized and directed / undirected networks. Empirical studies on four real networks show that the edge importance distribution proposed by GLANB method is bimodal, so the robust classification of edges can be obtained. Furthermore, the GLANB method tends to retain the nodes of the network center in the k- shell decomposition in the backbone structure. To sum up, GLANB method can help us understand the structure of the network better, determine the edge that plays a key role in the transmission of information, and transfer the information expressed by the network more conveniently through the backbone structure.
【学位授予单位】：北京邮电大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：O157.5
本文编号：2408218
[Abstract]:Complex networks are a useful tool for representing and analyzing complex systems, such as the World wide Web and transport systems. However, as the volume of complex networks increases, it becomes more and more difficult to understand the topology and their characteristics of networks. In this paper, we first review eight methods used to detect and sort critical edges in a network, and analyze their applicability and limitations. Then we apply these methods to four real-world networks. We compare the distribution of edge importance and the size of the extracted backbone structure to reveal the correlation between the methods. After comparing the eight methods, we propose a global and local adaptive backbone structure extraction method (GLANB). GLANB) to evaluate the statistical importance of edges by using the shortest path based edge participation and statistical assumptions. Then the GLANB method uses the statistical importance of edges to retain more important edges to extract the backbone structure, which is the extracted sub-network with fewer nodes and edges. The GLANB method considers the topological structure of the network synthetically. The importance of edges is determined by the weight of edges and the degree of nodes. The edges with small weights but which play an important role in topology can not be ignored. The GLANB method can be applied to all types of networks, including weighted / unauthorized and directed / undirected networks. Empirical studies on four real networks show that the edge importance distribution proposed by GLANB method is bimodal, so the robust classification of edges can be obtained. Furthermore, the GLANB method tends to retain the nodes of the network center in the k- shell decomposition in the backbone structure. To sum up, GLANB method can help us understand the structure of the network better, determine the edge that plays a key role in the transmission of information, and transfer the information expressed by the network more conveniently through the backbone structure.
【学位授予单位】：北京邮电大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：O157.5
【参考文献】
相关期刊论文 前1条
1 陈泉;杨建梅;曾进群;;零模型及其在复杂网络研究中的应用[J];复杂系统与复杂性科学;2013年01期
相关博士学位论文 前1条
1 杜楠;复杂网络中社区结构发现算法研究及建模[D];北京邮电大学;2009年
，本文编号：2408218
本文链接：https://www.wllwen.com/kejilunwen/yysx/2408218.html
