A Novel Measurement for Network Reliability

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.