论文部分内容阅读
Betweenness能够刻画节点或边在网络中的重要程度．在Internet中，Betweenness直接反应了特定网络拓扑结构下节点或链路可能承载的网络流量，能够对网络的动态行为进行预测．但传统的Betweenness计算复杂度较高，为O（n^3），但这些算法是为加权网络设计的，而很多实际的网络模型并没有考虑权重．另一方面，目前的算法都没有考虑边的语义，而互联网AS（autonomous system）拓扑中的边具有语义．针对简单无权网络提出一种基于回溯的时间复杂度为O（nm）的Betweenness计