A Novel Measurement for Network Reliability

Limei Lin, Yanze Huang, Dajin Wang, Sun Yuan Hsieh, Li Xu

Research output: Contribution to journalArticlepeer-review


The attackers in a network may have a tendency of targeting on a group of clustered nodes, and they hope to avoid the existence of significant large communication groups in the remaining network. This observation inspires a new measure for network reliability to resist the block attack by taking into account of the dispersity of the remaining nodes. Let G be a network, CV (G) and G[C] be a connected subgraph. Then C is called an h-faulty-block of G if G-C is disconnected, and every component of G-C has at least h+1 nodes. The minimum cardinality over all h-faulty-blocks of G is called h-faulty-block connectivity of G, denoted by FB h(G). In this paper, we determine FBh(Qn) for Qn, a classic interconnection network. We establish that FBh(Qn) = (h+2)n3h1 for 0h1, and FBh(Qn)=(h+2)n-4h+1 for 2hn-2. Larger h-faulty-block connectivity implies that an attacker need to attack a bigger block of connected nodes, so that there will not be great disparity in sizes between any two remaining components, and hence there will less likely be a significantly large remaining communication group. Our experiments also show that as h increases, the size of the largest remaining communication group becomes smaller.

Original languageEnglish
JournalIEEE Transactions on Computers
StateAccepted/In press - 2020


  • Block attack
  • Botnet
  • Computer network reliability
  • Fault tolerance
  • Fault tolerant systems
  • Fault-tolerance
  • Faulty-block connectivity
  • Hypercube
  • Hypercubes
  • Network reliability
  • Resists


Dive into the research topics of 'A Novel Measurement for Network Reliability'. Together they form a unique fingerprint.

Cite this