Connectivity-preserving distributed algorithms for removing links in directed networks

Research output: Contribution to journalArticleScientificpeer-review

4 Downloads (Pure)


This article considers the link removal problem in a strongly connected directed network with the goal of minimizing the dominant eigenvalue of the network’s adjacency matrix while maintaining its strong connectivity. Due to the complexity of the problem, this article focuses on computing a suboptimal solution. Furthermore, it is assumed that the knowledge of the overall network topology is not available. This calls for distributed algorithms which rely solely on the local information available to each individual node and information exchange between each node and its neighbors. Two different strategies based on matrix perturbation analysis are presented, namely simultaneous and iterative link removal strategies. Key ingredients in implementing both strategies include novel distributed algorithms for estimating the dominant eigenvectors of an adjacency matrix and for verifying strong connectivity of a directed network under link removal. It is shown via numerical simulations on different type of networks that in general the iterative link removal strategy yields a better suboptimal solution. However, it comes at a price of higher communication cost in comparison to the simultaneous link removal strategy.
Original languageEnglish
Pages (from-to)215-233
Number of pages19
JournalNetwork Science
Issue number3
Publication statusPublished - 6 Sept 2022
Publication typeA1 Journal article-refereed

Publication forum classification

  • Publication forum level 1


Dive into the research topics of 'Connectivity-preserving distributed algorithms for removing links in directed networks'. Together they form a unique fingerprint.

Cite this