University of Tasmania
Browse
118100 - detecting critical links in complex network.pdf (497.13 kB)

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

Download (497.13 kB)
conference contribution
posted on 2023-05-23, 12:13 authored by Saito, K, Kimura, M, Ohara, K, Motoda, H
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.

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 Zhang

Pagination

419-432

ISBN

978-3-319-42911-3

Department/School

School of Engineering

Publisher

Springer International Publishing

Place of publication

Switzerland

Event title

14th Pacific Rim Conference on Artificial Intelligence (PRICAI 2016)

Event Venue

Phuket, Thailand

Date of Event (Start Date)

2016-08-22

Date of Event (End Date)

2016-08-26

Rights 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_35

Repository Status

  • Open

Socio-economic Objectives

Information systems, technologies and services not elsewhere classified

Usage metrics

    University Of Tasmania

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC