The (betweenness) centrality of critical nodes and network cores

The betweenness centrality of a node is a measure related to the number of shortest path the node is involved with. It is, indeed, a measure of the importance of the node in the network, and in the recent years has been used intensively for network analysis. The major drawback of this measure is its high computational cost, and thus in the literature several works appeared providing ways of approximating it, thus presenting a trade off between accuracy and speed. The articulation points of a connected network are the nodes whose removal disconnects the network, and the critical nodes are the articulation points of the network core, i.e. the subset of the network obtained by repeatedly pruning the nodes of low (fixed) degree. In [1] Ausiello et al. showed that, in ten years of samples of the Autonomous System (AS) Network, the removal of a single critical node from the network was able to affect hundreds of nodes, that were no longer connected to the main part of the AS Network. From the above definitions it seems that there should be a correlation between articulation points, critical nodes, and central nodes, i.e. the ones who exhibit a high value of betweenness centrality. In this paper we show that this intuition is empirically confirmed in the monitoring of the Autonomous System Network, where articulation points and critical nodes have a betweenness centrality that is orders of magnitude larger than the one of generic nodes. This fact, coupled with the fast algorithms for real time monitoring of articulation points [2] and critical nodes [1], confirms on one side the importance of these subsets of nodes, and on the other that this monitoring provides a stable insight about the state of the network. © 2013 IEEE.