Distributed Link Removal Using Local Estimation of Network Topology

Azwirman Gusrialdi, Zhihua Qu, Sandra Hirche

Research output: Contribution to journalArticlepeer-review

15 Scopus citations

Abstract

This paper considers the problem of network structure manipulation in the absence of information on the global network topology. In particular, the problem of removing some of links is investigated in order to slow or stop the spread of disease in a network while preserving its connectivity. Existing methods solve this combinatorial problem in a centralized manner and they require the global information of network structure. In this paper, we propose a distributed design algorithm to compute a suboptimal solution to this problem efficiently by mimicking gradient based method, namely by iteratively removing one or multiple links at a time from the network. Specifically, using matrix perturbation analysis we formulate an optimization problem involving the eigenvector associated with the largest eigenvalue of the adjacency matrix and whose solution is equal to a suboptimal solution to the original problem. This strategy also enables us to overcome the combinatorial issue of the problem. Distributed algorithms to estimate the eigenvector and to verify network's connectivity are then proposed which facilitate us to solve the new optimization problem. In addition, topological insights into the proposed algorithm and optimality of its solution are also discussed. Finally, the proposed distributed design method is demonstrated and evaluated via several numerical examples.

Original languageEnglish
Article number8314114
Pages (from-to)280-292
Number of pages13
JournalIEEE Transactions on Network Science and Engineering
Volume6
Issue number3
DOIs
StatePublished - 1 Jul 2019

Keywords

  • Link removal
  • distributed algorithm
  • largest eigenvalue minimization
  • matrix perturbation

Fingerprint

Dive into the research topics of 'Distributed Link Removal Using Local Estimation of Network Topology'. Together they form a unique fingerprint.

Cite this