118100 - detecting critical links in complex network.pdf (497.13 kB)
Detecting critical links in complex network to maintain information flow/reachability
conference contribution
posted on 2023-05-23, 12:13 authored by Saito, K, Kimura, M, Ohara, K, Motoda, HWe 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.
History
Publication title
Lecture Notes in Computer Science 9810: Proceedings of the 14th Pacific Rim International Conference on Artificial Intelligence (PRICAI 2016) - Trends in Artificial Intelligence)Editors
R Booth, M-L ZhangPagination
419-432ISBN
978-3-319-42911-3Department/School
School of EngineeringPublisher
Springer International PublishingPlace of publication
SwitzerlandEvent title
14th Pacific Rim Conference on Artificial Intelligence (PRICAI 2016)Event Venue
Phuket, ThailandDate of Event (Start Date)
2016-08-22Date of Event (End Date)
2016-08-26Rights 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 http://dx.doi.org/10.1007/978-3-319-42911-3_35Repository Status
- Open