Critical Node Identification based on Articulation Point Detection for Uncertain Network

Abstract

The problem of efficiently identifying critical nodes that substantially degrade network performance if they do not function is crucial and essential in analyzing a large complex network such as social networks on the Web and road network in the real world, and it is still challenging. In this paper, we tackle this problem under a realistic situation where each link is probabilistically disconnected as assumed in studies in uncertain graphs. This reflects that in case of a social network an information path between two persons is not always open and may not pass on any information from one to the other and in case of a road network a road between two intersections is not always travelable and may be blocked by a traffic accident, a road repair, a nearby construction, etc. To solve this problem, we focus on the articulation point and utilize the bridge detection technique in graph theory to efficiently identify critical nodes when the node reachability is taken as the performance measure. In case of a social network disfunction of a node causes loss of the total number of people receiving information and in case of a road network it causes loss of the total number of people movable to other places. Using two real-world social networks and one road network, we empirically show that the proposed method has a good scalability with respect to the network size and the nodes our method identified possesses unique properties and they are difficult to be identified by using conventional centrality measures.