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

摘要

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