An Algorithm for Internet AS Graph Betweenness Centrality Based on Backtrack

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(n\+3) 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.