Network Pruning and Growth - Probabilistic Optimization

Yi-Zhi Xu, David Saad

Research output: Contribution to journalArticlepeer-review


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 languageEnglish
Article number033087
Number of pages12
JournalPhysical Review Research
Issue number3
Early online date8 Aug 2023
Publication statusE-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.


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


Dive into the research topics of 'Network Pruning and Growth - Probabilistic Optimization'. Together they form a unique fingerprint.

Cite this