Easily repairable networks: reconnecting nodes after damage.

Journal Article (Journal Article)

We introduce a simple class of distribution networks that withstand damage by being repairable instead of redundant. Instead of asking how hard it is to disconnect nodes through damage, we ask how easy it is to reconnect nodes after damage. We prove that optimal networks on regular lattices have an expected cost of reconnection proportional to the lattice length, and that such networks have exactly three levels of structural hierarchy. We extend our results to networks subject to repeated attacks, in which the repairs themselves must be repairable. We find that, in exchange for a modest increase in repair cost, such networks are able to withstand any number of attacks.

Full Text

Duke Authors

Cited Authors

  • Farr, RS; Harer, JL; Fink, TMA

Published Date

  • September 26, 2014

Published In

Volume / Issue

  • 113 / 13

Start / End Page

  • 138701 -

PubMed ID

  • 25302922

Electronic International Standard Serial Number (EISSN)

  • 1079-7114

International Standard Serial Number (ISSN)

  • 0031-9007

Digital Object Identifier (DOI)

  • 10.1103/physrevlett.113.138701


  • eng