Real-time analysis of critical nodes in network cores

The articulation points and bridges of a connected network are, respectively, the vertices and the edges whose removal disconnects the network. However, not all the articulation points (resp. bridges) are equal: from the graph theoretic perspective, there is no difference whether the removal of a vertex (resp. bridge) disconnects only one vertex from the rest of the network, or it cuts the network in two pieces. But in the monitoring of a huge network, it makes a difference. We present a real-time algorithm, analyzed in the (semi-)streaming model of computation, that is able to identify a core subset of the articulation points (resp. bridges), i.e. the ones whose removal has a big impact on the network: these are the critical nodes (resp. edges) of the network. We complement our work with an experimental evaluation of the algorithm against ten years of samples of the Autonomous System network, that confirms the effectiveness of our approach. © 2012 IEEE.