Distributed Algorithm for Link Removal in Directed Networks

摘要

This paper considers the problem of removing a fraction of links from a strongly connected directed network such that the largest (in module) eigenvalue of the adjacency matrix corresponding to the network structure is minimized. Due to the complexity of the problem, an effective and scalable algorithm based on eigenvalue sensitivity analysis is proposed in the literature to compute the suboptimal solution to the problem. However, the algorithm requires knowledge of the global network structure and does not preserve strong connectivity of the resulting network. This paper proposes distributed algorithms which allow distributed implementation of the previously mentioned algorithm by relying solely on local information on the network topology while guaranteeing strong connectivity of the resulting network. A numerical example is provided to demonstrate the proposed distributed algorithm.