Assessing Network Reliability Through Perspectives of Neighbor Connectivity and Subversion

Abstract

Neighbor connectivity has been a crucial metric in assessing espionage networks' subversion and measuring network disruption caused by failures through neighbor sets. For a network <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$G$</tex-math></inline-formula>, the neighbor connectivity <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\kappa _{\text{NB}}(G)$</tex-math></inline-formula> (resp. edge neighbor connectivity <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\lambda _{\text{NB}}(G)$</tex-math></inline-formula>) is the minimum number of vertices (resp. edges) that must be removed from the network, along with their neighbors, to make the network disconnected, empty, or complete (resp. trivial). Both metrics help evaluate networks' reliability and fault tolerance as they consider the worst-case scenario compared to general failure, making them more objective and meaningful. This paper explores (edge) neighbor connectivity of two networks: dual-cube-like networks (including dual cubes) and generalized exchanged hypercubes (including exchanged hypercubes). These networks extend hypercubes, one of the most significant interconnection networks in parallel computing systems. Additionally, we conduct experiments to evaluate the effect of subversion under different choices of subverted vertices in these networks at various scales. These findings from simulation provide valuable insights into network reliability and fault tolerance and can enhance our understanding of neighbor connectivity and subversion.

Topics & Concepts