TY - JOUR

T1 - Distributed Link Removal Using Local Estimation of Network Topology

AU - Gusrialdi, Azwirman

AU - Qu, Zhihua

AU - Hirche, Sandra

N1 - Publisher Copyright:
© 2013 IEEE.

PY - 2019/7/1

Y1 - 2019/7/1

N2 - 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.

AB - 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.

KW - Link removal

KW - distributed algorithm

KW - largest eigenvalue minimization

KW - matrix perturbation

UR - http://www.scopus.com/inward/record.url?scp=85043461808&partnerID=8YFLogxK

U2 - 10.1109/TNSE.2018.2813426

DO - 10.1109/TNSE.2018.2813426

M3 - Article

AN - SCOPUS:85043461808

SN - 2327-4697

VL - 6

SP - 280

EP - 292

JO - IEEE Transactions on Network Science and Engineering

JF - IEEE Transactions on Network Science and Engineering

IS - 3

M1 - 8314114

ER -