Robust Network Connectivity: a Percolation Study

Abstract Communication networks, power grids, and transportation networks are all examples of networks whose performance depends on reliable connectivity of their underlying network components even in the presence of usual network dynamics due to mobility, node or edge failures, and varying traffic loads. Percolation theory quantifies the threshold value of a local control parameter—such as a node occupation (resp., deletion) probability or an edge activation (resp., removal) probability —above (resp., below) which there exists a giant connected component (GCC), a connected component comprising of occupied nodes and active edges whose size is proportional to the size of the network itself. Any pair of nodes in the GCC is connected via at least one path. The mere existence of the GCC itself does not guarantee robustness, e.g., to network dynamics. In this paper, we explore new percolation thresholds that guarantee not only spanning network connectivity, but also robustness to failures.
  • Arman Kabir (UMass)
  • Mihir Pant
  • Don Towsley (UMass)
  • Saikat Guha
  • Paul Yu (ARL)
  • Ananthram Swami (ARL)
Date Sep-2017
Venue 1st Annual Fall Meeting of the DAIS ITA, 2017