TY - JOUR

T1 - A Novel Measurement for Network Reliability

AU - Lin, Limei

AU - Huang, Yanze

AU - Wang, Dajin

AU - Hsieh, Sun Yuan

AU - Xu, Li

N1 - Publisher Copyright:
IEEE
Copyright:
Copyright 2020 Elsevier B.V., All rights reserved.

PY - 2020

Y1 - 2020

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85091683203&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85091683203&partnerID=8YFLogxK

U2 - 10.1109/TC.2020.3023120

DO - 10.1109/TC.2020.3023120

M3 - Article

AN - SCOPUS:85091683203

JO - IEEE Transactions on Computers

JF - IEEE Transactions on Computers

SN - 0018-9340

ER -