Network Pruning and Growth - Probabilistic Optimization

Yi-Zhi Xu; David Saad

doi:https://doi.org/10.1103/PhysRevResearch.5.033087

Network Pruning and Growth - Probabilistic Optimization

Research output: Contribution to journal › Article › peer-review

Abstract

Being the backbone of many human-made systems, networks require both pruning and growth to adapt to changing demand. We develop a message passing-based framework for analyzing and addressing the two-level optimization problem of edge removal/addition for indirectly-dependent
objectives. As exemplar problem we use routing in optical communication networks to minimize capability loss (removal) or maximize capacity (addition). The methods developed result in lower path-lengths and higher capacity topologies with respect to existing ones and are suitable for a broad range of network design tasks.

Original language	English
Article number	033087
Number of pages	12
Journal	Physical Review Research
Volume	5
Issue number	3
Early online date	8 Aug 2023
DOIs	https://doi.org/10.1103/PhysRevResearch.5.033087
Publication status	E-pub ahead of print - 8 Aug 2023

Bibliographical note

Acknowledgements: DS and YZX acknowledge support from the EPSRC Programme Grant TRANSNET (EP/R035342/1).
Copyright: Published by the American Physical Society under the terms of the Creative Commons Attribution 4.0 International license. Further distribution of this work must maintain attribution to the author(s) and the published article's title, journal citation, and DOI.

Keywords

complex systems
computational complexity
network flow optimization
network formation and growth
Network Optimisation

Access to Document

https://doi.org/10.1103/PhysRevResearch.5.033087Licence: CC BY 4.0

network pruning and growth
Published by the American Physical Society under the terms of the Creative Commons Attribution 4.0 International license. Further distribution of this work must maintain attribution to the author(s) and the published article’s title, journal citation, and DOI
Final published version, 1 MBLicence: CC BY 4.0

Cite this

@article{7024f668ef8d488083af706b532dd641,

title = "Network Pruning and Growth - Probabilistic Optimization",

abstract = "Being the backbone of many human-made systems, networks require both pruning and growth to adapt to changing demand. We develop a message passing-based framework for analyzing and addressing the two-level optimization problem of edge removal/addition for indirectly-dependentobjectives. As exemplar problem we use routing in optical communication networks to minimize capability loss (removal) or maximize capacity (addition). The methods developed result in lower path-lengths and higher capacity topologies with respect to existing ones and are suitable for a broad range of network design tasks.",

keywords = "complex systems, computational complexity, network flow optimization, network formation and growth, Network Optimisation",

author = "Yi-Zhi Xu and David Saad",

note = "Acknowledgements: DS and YZX acknowledge support from the EPSRC Programme Grant TRANSNET (EP/R035342/1). Copyright: Published by the American Physical Society under the terms of the Creative Commons Attribution 4.0 International license. Further distribution of this work must maintain attribution to the author(s) and the published article's title, journal citation, and DOI.",

year = "2023",

month = aug,

day = "8",

doi = "https://doi.org/10.1103/PhysRevResearch.5.033087",

language = "English",

volume = "5",

journal = "Physical Review Research",

issn = "2643-1564",

publisher = "American Physical Society",

number = "3",

}

TY - JOUR

T1 - Network Pruning and Growth - Probabilistic Optimization

AU - Xu, Yi-Zhi

AU - Saad, David

N1 - Acknowledgements: DS and YZX acknowledge support from the EPSRC Programme Grant TRANSNET (EP/R035342/1). Copyright: Published by the American Physical Society under the terms of the Creative Commons Attribution 4.0 International license. Further distribution of this work must maintain attribution to the author(s) and the published article's title, journal citation, and DOI.

PY - 2023/8/8

Y1 - 2023/8/8

N2 - Being the backbone of many human-made systems, networks require both pruning and growth to adapt to changing demand. We develop a message passing-based framework for analyzing and addressing the two-level optimization problem of edge removal/addition for indirectly-dependentobjectives. As exemplar problem we use routing in optical communication networks to minimize capability loss (removal) or maximize capacity (addition). The methods developed result in lower path-lengths and higher capacity topologies with respect to existing ones and are suitable for a broad range of network design tasks.

AB - Being the backbone of many human-made systems, networks require both pruning and growth to adapt to changing demand. We develop a message passing-based framework for analyzing and addressing the two-level optimization problem of edge removal/addition for indirectly-dependentobjectives. As exemplar problem we use routing in optical communication networks to minimize capability loss (removal) or maximize capacity (addition). The methods developed result in lower path-lengths and higher capacity topologies with respect to existing ones and are suitable for a broad range of network design tasks.

KW - complex systems

KW - computational complexity

KW - network flow optimization

KW - network formation and growth

KW - Network Optimisation

UR - https://journals.aps.org/prresearch/abstract/10.1103/PhysRevResearch.5.033087

U2 - https://doi.org/10.1103/PhysRevResearch.5.033087

DO - https://doi.org/10.1103/PhysRevResearch.5.033087

M3 - Article

SN - 2643-1564

VL - 5

JO - Physical Review Research

JF - Physical Review Research

IS - 3

M1 - 033087

ER -

Network Pruning and Growth - Probabilistic Optimization

Abstract

Bibliographical note

Keywords

Access to Document

Other files and links

Fingerprint

Cite this