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

被引：8

作者：

张国强

张国清

机构：

[1] 中国科学院计算技术研究所

来源：

计算机研究与发展 | 2006年 / 10期

关键词：

Betweenness; 自治系统; 网络拓扑; 路由策略;

D O I：

暂无

中图分类号：

TP393.01 [];

学科分类号：

摘要：

Betweenness能够刻画节点或边在网络中的重要程度.在Internet中,Betweenness直接反应了特定网络拓扑结构下节点或链路可能承载的网络流量,能够对网络的动态行为进行预测.但传统的Be-tweenness计算复杂度较高,为O(n3),但这些算法是为加权网络设计的,而很多实际的网络模型并没有考虑权重.另一方面,目前的算法都没有考虑边的语义,而互联网AS(autonomoussystem)拓扑中的边具有语义.针对简单无权网络提出一种基于回溯的时间复杂度为O(nm)的Betweenness计算方法.在进一步考虑InternetAS拓扑的特殊性,即任意两个相连的AS都具有某种商业关系的基础上提出了互联网AS层拓扑的Betweenness计算方法.

引用

页码：1790 / 1796

页数：7