期刊名称：International Journal of Networking and Computing
印刷版ISSN：2185-2847
出版年度：2019
卷号：9
期号：2
页码：201-216
出版社：International Journal of Networking and Computing
摘要：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.
关键词：Critical node; Articulation point detection; Uncertain graphs; Network analysis
其他关键词：Critical node;Articulation point detection;Uncertain graphs;Network analysis
