基于回溯机制的互联网AS拓扑的Betweenness算法  

An Algorithm for Internet AS Graph Betweenness Centrality Based on Backtrack

作　　者：张国强[1,2] 张国清[1] 

机构地区：[1]中国科学院计算技术研究所 [2]中国科学院研究生院北京100049

出　　处：《计算机研究与发展》2006年第10期1790-1796,共7页Journal of Computer Research and Development

基　　金：下一代互联网中日IPv6合作项目子项目(20032050);中国科学院计算技术研究所创新基金项目(20066033)~~

摘　　要：Betweenness能够刻画节点或边在网络中的重要程度.在Internet中,Betweenness直接反应了特定网络拓扑结构下节点或链路可能承载的网络流量,能够对网络的动态行为进行预测.但传统的Be-tweenness计算复杂度较高,为O(n3),但这些算法是为加权网络设计的,而很多实际的网络模型并没有考虑权重.另一方面,目前的算法都没有考虑边的语义,而互联网AS(autonomoussystem)拓扑中的边具有语义.针对简单无权网络提出一种基于回溯的时间复杂度为O(nm)的Betweenness计算方法.在进一步考虑InternetAS拓扑的特殊性,即任意两个相连的AS都具有某种商业关系的基础上提出了互联网AS层拓扑的Betweenness计算方法.Betweenness plays a key role in the characterization of complex networks, which can be used to quantify a node or edge＇s importance. For Internet, betweenness directly reflects the possible load needed to carry by the node or edge, thus it can be used to predict the network＇s dynamic behavior. However, O（n3） run time is required to compute the betweenness by conventional algorithms, which becomes a bottleneck for large-scale network analysis. These algorithms are devised for weighted networks, but a lot of real network models don＇t take weight into account. On the other hand, neither of these algorithms take the semantics of edges into account. In this paper, an algorithm based on backtrack which calculates the betweenness for simple un-weighted network with O （ nm ） run time complexity is proposed, after which the unique feature of Internet AS graph, i.e, edges between two ASes are associated with some kind of commercial relationships, is considered. Grounded on the simple backtrack algorithm, an algorithm for calculating betweenness of Internet AS graph is proposed. Since routing policies and routing behaviors are also considered in this algorithm, it has great significance to apply this betweenness computation to the analysis of Internet behavior.

关 键 词：BETWEENNESS 自治系统 网络拓扑 路由策略 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]