Efficient computation of target-oriented link criticalness centrality in uncertain graphs
Efficient computation of target-oriented link criticalness centrality in uncertain graphs
复制标题
DOI：
10.3233/ida-205539
复制
发表时间：
2021-09
期刊：
影响因子：
--
通讯作者：
Kazumi Saito;Takayasu Fushimi;K. Ohara;M. Kimura;H. Motoda
中科院分区：
文献类型：
--
作者：
Kazumi Saito;Takayasu Fushimi;K. Ohara;M. Kimura;H. Motoda
我们挑战了有效识别关键链路的问题，如果它们在每个链路可能断开的现实情况下不起作用，例如，道路网络中的意外交通事故和通信网络中的意外服务器停机，则会大大降低网络性能。为了解决这一问题，我们利用图论中的桥检测技术，在以节点可达性作为性能指标的情况下，有效地识别出关键链路。更精确地说，我们定义了一组目标节点和与之相关的新度量，目标导向的潜在链接临界中心性（TCC），它被定义为网络中可以到达或等价地可以从一个目标节点到达的节点数量的边际损失，并通过使用检测桥计算每个链路的TCC。我们将所提出的方法应用于两个现实网络，一个来自社交网络，另一个来自空间网络，经验表明，所提出的方法在网络规模方面具有良好的可扩展性，并且我们的方法识别的链接具有独特的性质。它们比其他方法获得的结果更为重要，并且没有已知的方法可以取代TCC方法。
We challenge the problem of efficiently identifying critical links that substantially degrade network performance if they do not function under a realistic situation where each link is probabilistically disconnected, e.g., unexpected traffic accident in a road network and unexpected server down in a communication network. To solve this problem, we utilize the bridge detection technique in graph theory and efficiently identify critical links in case the node reachability is taken as the performance measure.To be more precise, we define a set of target nodes and a new measure associated with it, Target-oriented latent link Criticalness Centrality (TCC), which is defined as the marginal loss of the expected number of nodes in the network that can reach, or equivalently can be reached from, one of the target nodes, and compute TCC for each link by use of detected bridges. We apply the proposed method to two real-world networks, one from social network and the other from spatial network, and empirically show that the proposed method has a good scalability with respect to the network size and the links our method identified possess unique properties. They are substantially more critical than those obtained by the others, and no known measures can replace the TCC measure.