Connectivity in Interdependent Networks
We propose and analyze a graph model to study the connectivity of interdependent networks. Two interdependent networks of arbitrary topologies are modeled as two graphs, where every node in one graph is supported by supply nodes in the other graph, and a node fails if all of its supply nodes fail. S...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Institute of Electrical and Electronics Engineers (IEEE)
2020
|
| Online Access: | https://hdl.handle.net/1721.1/125138 |
| _version_ | 1826215221740437504 |
|---|---|
| author | Zhang, Jianan Modiano, Eytan H. |
| author2 | Massachusetts Institute of Technology. Laboratory for Information and Decision Systems |
| author_facet | Massachusetts Institute of Technology. Laboratory for Information and Decision Systems Zhang, Jianan Modiano, Eytan H. |
| author_sort | Zhang, Jianan |
| collection | MIT |
| description | We propose and analyze a graph model to study the connectivity of interdependent networks. Two interdependent networks of arbitrary topologies are modeled as two graphs, where every node in one graph is supported by supply nodes in the other graph, and a node fails if all of its supply nodes fail. Such interdependence arises in cyber-physical systems and layered network architectures. We study the supply node connectivity of a network: namely, the minimum number of supply node removals that would disconnect the network. We develop algorithms to evaluate the supply node connectivity given arbitrary network topologies and interdependence between two networks. Moreover, we develop interdependence assignment algorithms that maximize the supply node connectivity. We prove that a random assignment algorithm yields a supply node connectivity within a constant factor from the optimal for most networks. Keywords: Robustness; cyber-physical systems; communication networks; analytical models. |
| first_indexed | 2024-09-23T16:19:21Z |
| format | Article |
| id | mit-1721.1/125138 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T16:19:21Z |
| publishDate | 2020 |
| publisher | Institute of Electrical and Electronics Engineers (IEEE) |
| record_format | dspace |
| spelling | mit-1721.1/1251382022-09-29T19:34:59Z Connectivity in Interdependent Networks Zhang, Jianan Modiano, Eytan H. Massachusetts Institute of Technology. Laboratory for Information and Decision Systems Massachusetts Institute of Technology. Department of Aeronautics and Astronautics We propose and analyze a graph model to study the connectivity of interdependent networks. Two interdependent networks of arbitrary topologies are modeled as two graphs, where every node in one graph is supported by supply nodes in the other graph, and a node fails if all of its supply nodes fail. Such interdependence arises in cyber-physical systems and layered network architectures. We study the supply node connectivity of a network: namely, the minimum number of supply node removals that would disconnect the network. We develop algorithms to evaluate the supply node connectivity given arbitrary network topologies and interdependence between two networks. Moreover, we develop interdependence assignment algorithms that maximize the supply node connectivity. We prove that a random assignment algorithm yields a supply node connectivity within a constant factor from the optimal for most networks. Keywords: Robustness; cyber-physical systems; communication networks; analytical models. United States. Defense Threat Reduction Agency (Grant HDTRA1-13-1-0021) United States. Defense Threat Reduction Agency (Grant DTRA1-14-1-0058) 2020-05-08T15:21:50Z 2020-05-08T15:21:50Z 2018-09 2019-10-30T14:36:40Z Article http://purl.org/eprint/type/JournalArticle 1063-6692 1558-2566 https://hdl.handle.net/1721.1/125138 Zhang, Jianan and Modiano, Eytan. "Connectivity in Interdependent Networks." IEEE/ACM Transactions on Networking 26, 5 (October 2018): 2090 - 2103 © 1993-2012 IEEE. en http://dx.doi.org/10.1109/tnet.2018.2863715 IEEE/ACM Transactions on Networking Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Institute of Electrical and Electronics Engineers (IEEE) arXiv |
| spellingShingle | Zhang, Jianan Modiano, Eytan H. Connectivity in Interdependent Networks |
| title | Connectivity in Interdependent Networks |
| title_full | Connectivity in Interdependent Networks |
| title_fullStr | Connectivity in Interdependent Networks |
| title_full_unstemmed | Connectivity in Interdependent Networks |
| title_short | Connectivity in Interdependent Networks |
| title_sort | connectivity in interdependent networks |
| url | https://hdl.handle.net/1721.1/125138 |
| work_keys_str_mv | AT zhangjianan connectivityininterdependentnetworks AT modianoeytanh connectivityininterdependentnetworks |