eCite Digital Repository

Detecting critical links in complex network to maintain information flow/reachability


Saito, K and Kimura, M and Ohara, K and Motoda, H, Detecting critical links in complex network to maintain information flow/reachability, Lecture Notes in Computer Science 9810: Proceedings of the 14th Pacific Rim International Conference on Artificial Intelligence (PRICAI 2016) - Trends in Artificial Intelligence), 22-26 August 2016, Phuket, Thailand, pp. 419-432. ISBN 978-3-319-42911-3 (2016) [Refereed Conference Paper]


Copyright Statement

Copyright 2016 Springer International Publishing Switzerland. This is an author-created version of a paper originally published in: Booth R., Zhang ML. (eds) PRICAI 2016: Trends in Artificial Intelligence. PRICAI 2016. Lecture Notes in Computer Science, vol 9810. Springer, Cham. The final publication is available at Springer via

Official URL:


We address the problem of efficiently detecting critical links in a large network. Critical links are such links that their deletion exerts substantial effects on the network performance. Here in this paper, we define the performance as being the average node reachability. This problem is computationally very expensive because the number of links is an order of magnitude larger even for a sparse network. We tackle this problem by using bottom-k sketch algorithm and further by employing two new acceleration techniques: marginal-link updating (MLU) and redundant-link skipping (RLS). We tested the effectiveness of the proposed method using two real-world large networks and two synthetic large networks and showed that the new method can compute the performance degradation by link removal about an order of magnitude faster than the baseline method in which bottom-k sketch algorithm is applied directly. Further, we confirmed that the measures easily composed by well known existing centralities, e.g. in/out-degree, betweenness, PageRank, authority/hub, are not able to detect critical links. Those links detected by these measures do not reduce the average reachability at all, i.e. not critical at all.

Item Details

Item Type:Refereed Conference Paper
Keywords:social networks, link deletion, critical links, node reachability
Research Division:Information and Computing Sciences
Research Group:Information systems
Research Field:Information systems organisation and management
Objective Division:Information and Communication Services
Objective Group:Information systems, technologies and services
Objective Field:Information systems, technologies and services not elsewhere classified
UTAS Author:Motoda, H (Dr Hiroshi Motoda)
ID Code:118100
Year Published:2016
Deposited By:Information and Communication Technology
Deposited On:2017-07-04
Last Modified:2018-03-28
Downloads:147 View Download Statistics

Repository Staff Only: item control page