On connectivity of interdependent networks

Arunabha Sen, Kaustav Basu

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Scopus citations


The studies in fault-tolerance in networks mostly focus on the connectivity of the graph as the metric of fault-tolerance. If the underlying graph is k-connected, it can tolerate up to k -1 failures. This metric in various forms, has been used extensively for robust design of communication networks, which may be viewed as a single layer network. In the last few years, there is an increasing awareness in the research community that critical infrastructure networks, such as the power grid and the communication network are highly interdependent. This inter-dependency has become critical in a {smart-grid} environment, where the electric power transmission/distribution network is highly integrated with the communication network. This dependency realization has led to a fairly large number of studies on robustness and resiliency of interdependent multi-layer networks. Unfortunately, many of the proposed models of inter-dependency that appeared in the literature in the last few years fail to capture the complex inter-dependency that exists between entities of power grid and communication networks, involving a complex combination of conjunctive and disjunctive relations. The Boolean logic based model of inter-dependency proposed in cite{sen2014identification} overcomes this limitation. Using this dependency model, in this paper we explore ''connectivity'' of a two-layer interdependent network and formally define a new metric, Two-Layered connectivity (TL-connectivity), that is a counterpart of the traditional connectivity metric for a single-layer network (SL-connectivity). We provide an algorithm for computation of TL-connectivity. The problem can be solved in polynomial time in some special cases, whereas for some others, the problem is NP-complete. Finally, we evaluate the technique with a specific case study.

Original languageEnglish (US)
Title of host publication2019 IEEE Global Communications Conference, GLOBECOM 2019 - Proceedings
PublisherInstitute of Electrical and Electronics Engineers Inc.
ISBN (Electronic)9781728109626
StatePublished - Dec 2019
Event2019 IEEE Global Communications Conference, GLOBECOM 2019 - Waikoloa, United States
Duration: Dec 9 2019Dec 13 2019

Publication series

Name2019 IEEE Global Communications Conference, GLOBECOM 2019 - Proceedings


Conference2019 IEEE Global Communications Conference, GLOBECOM 2019
Country/TerritoryUnited States

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Hardware and Architecture
  • Information Systems
  • Signal Processing
  • Information Systems and Management
  • Safety, Risk, Reliability and Quality
  • Media Technology
  • Health Informatics


Dive into the research topics of 'On connectivity of interdependent networks'. Together they form a unique fingerprint.

Cite this