Distributed algorithm for link removal in directed networks

Azwirman Gusrialdi

doi:10.1007/978-3-030-65347-7_42

Distributed algorithm for link removal in directed networks

Azwirman Gusrialdi

Automation Technology and Mechanical Engineering

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Scientific › peer-review

5 Citations (Scopus)

14 Downloads (Pure)

Abstract

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.

Original language	English
Title of host publication	Complex Networks & Their Applications IX
Subtitle of host publication	Volume 1, Proceedings of the Ninth International Conference on Complex Networks and Their Applications COMPLEX NETWORKS 2020
Editors	Rosa M. Benito, Chantal Cherifi, Hocine Cherifi, Esteban Moro, Luis Mateus Rocha, Marta Sales-Pardo
Publisher	Springer
Pages	509-521
Number of pages	12
Volume	1
ISBN (Electronic)	9783030653477
ISBN (Print)	9783030653460
DOIs	https://doi.org/10.1007/978-3-030-65347-7_42
Publication status	Published - 2021
Publication type	A4 Article in conference proceedings
Event	International Conference on Complex Networks and their Applications - Madrid, Spain Duration: 1 Dec 2020 → 3 Dec 2020

Publication series

Name	Studies in Computational Intelligence
Number	943
ISSN (Print)	1860-949X
ISSN (Electronic)	1860-9503

Conference

Conference	International Conference on Complex Networks and their Applications
Country/Territory	Spain
City	Madrid
Period	1/12/20 → 3/12/20

Publication forum classification

Publication forum level 2

Access to Document

10.1007/978-3-030-65347-7_42

Distributed_Algorithm_for_Link_Removal
This publication is copyrighted. You may download, display and print it for Your own personal use. Commercial use is prohibited.
Accepted author manuscript, 1.27 MBLicence: Unspecified

https://urn.fi/URN:NBN:fi:tuni-202111258655Licence: Unspecified

Cite this

Gusrialdi, A. (2021). Distributed algorithm for link removal in directed networks. In R. M. Benito, C. Cherifi, H. Cherifi, E. Moro, L. M. Rocha, & M. Sales-Pardo (Eds.), Complex Networks & Their Applications IX: Volume 1, Proceedings of the Ninth International Conference on Complex Networks and Their Applications COMPLEX NETWORKS 2020 (Vol. 1, pp. 509-521). (Studies in Computational Intelligence; No. 943). Springer. https://doi.org/10.1007/978-3-030-65347-7_42

Gusrialdi, Azwirman. / Distributed algorithm for link removal in directed networks. Complex Networks & Their Applications IX: Volume 1, Proceedings of the Ninth International Conference on Complex Networks and Their Applications COMPLEX NETWORKS 2020. editor / Rosa M. Benito ; Chantal Cherifi ; Hocine Cherifi ; Esteban Moro ; Luis Mateus Rocha ; Marta Sales-Pardo. Vol. 1 Springer, 2021. pp. 509-521 (Studies in Computational Intelligence; 943).

@inproceedings{fc488161671f412f984988a562ca7e65,

title = "Distributed algorithm for link removal in directed networks",

abstract = "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.",

author = "Azwirman Gusrialdi",

year = "2021",

doi = "10.1007/978-3-030-65347-7_42",

language = "English",

isbn = "9783030653460",

volume = "1",

series = "Studies in Computational Intelligence",

publisher = "Springer",

number = "943",

pages = "509--521",

editor = "{M. Benito}, Rosa and Chantal Cherifi and Hocine Cherifi and Esteban Moro and Rocha, {Luis Mateus} and Marta Sales-Pardo",

booktitle = "Complex Networks & Their Applications IX",

note = "International Conference on Complex Networks and their Applications ; Conference date: 01-12-2020 Through 03-12-2020",

}

Gusrialdi, A 2021, Distributed algorithm for link removal in directed networks. in R M. Benito, C Cherifi, H Cherifi, E Moro, LM Rocha & M Sales-Pardo (eds), Complex Networks & Their Applications IX: Volume 1, Proceedings of the Ninth International Conference on Complex Networks and Their Applications COMPLEX NETWORKS 2020. vol. 1, Studies in Computational Intelligence, no. 943, Springer, pp. 509-521, International Conference on Complex Networks and their Applications, Madrid, Spain, 1/12/20. https://doi.org/10.1007/978-3-030-65347-7_42

Distributed algorithm for link removal in directed networks. / Gusrialdi, Azwirman.
Complex Networks & Their Applications IX: Volume 1, Proceedings of the Ninth International Conference on Complex Networks and Their Applications COMPLEX NETWORKS 2020. ed. / Rosa M. Benito; Chantal Cherifi; Hocine Cherifi; Esteban Moro; Luis Mateus Rocha; Marta Sales-Pardo. Vol. 1 Springer, 2021. p. 509-521 (Studies in Computational Intelligence; No. 943).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Scientific › peer-review

TY - GEN

T1 - Distributed algorithm for link removal in directed networks

AU - Gusrialdi, Azwirman

PY - 2021

Y1 - 2021

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

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

U2 - 10.1007/978-3-030-65347-7_42

DO - 10.1007/978-3-030-65347-7_42

M3 - Conference contribution

SN - 9783030653460

VL - 1

T3 - Studies in Computational Intelligence

SP - 509

EP - 521

BT - Complex Networks & Their Applications IX

A2 - M. Benito, Rosa

A2 - Cherifi, Chantal

A2 - Cherifi, Hocine

A2 - Moro, Esteban

A2 - Rocha, Luis Mateus

A2 - Sales-Pardo, Marta

PB - Springer

T2 - International Conference on Complex Networks and their Applications

Y2 - 1 December 2020 through 3 December 2020

ER -

Gusrialdi A. Distributed algorithm for link removal in directed networks. In M. Benito R, Cherifi C, Cherifi H, Moro E, Rocha LM, Sales-Pardo M, editors, Complex Networks & Their Applications IX: Volume 1, Proceedings of the Ninth International Conference on Complex Networks and Their Applications COMPLEX NETWORKS 2020. Vol. 1. Springer. 2021. p. 509-521. (Studies in Computational Intelligence; 943). Epub 2020. doi: 10.1007/978-3-030-65347-7_42

Distributed algorithm for link removal in directed networks

Abstract

Publication series

Conference

Publication forum classification

Access to Document

Fingerprint

Cite this