COMPARING RANDOM AND REGULAR NETWORK RESILIANCE AGAINST RANDOM ATTACK ON THEIR NODES
Keywords:
Cumulative D-spectrum, Dodecahedron, Five-dimensional cube, Maximal connected component, Network resilience, Node degree, Node failures, Preferential assignment, Regular grid.Abstract
We consider a family of connected networks whose nodes are subject to random failures ("attacks"). Node failure means elimination of all links incident to the attacked node. Each node, independently of others, fails with probability q . Network failure (DOWN) state is defined as the situation when the largest connected component has "critical" size <= L . We compare the probabilistic resilience of a simulated network (obtained by a preferential assignment-type algorithm) versus a regular network having the same number of nodes and links. This comparison is carried out for three types of regular networks: the dodecahedron (20 nodes, 30 links), square torus-type grid (25 nodes, 50 links) and five-dimensional cubic network (32 nodes, 80 links). For all three types of networks the critical value of L was approximately equal one third of the nodes. It turns out that the network with regular structure and node degree d=5 has higher resilience than a network with random structure, i.e. a regular network has smaller DOWN probability than a random network for the same q value and for the same number of failed nodes x It turns out, however, that the advantage of a regular network over a random network vanishes with the decrease of the average node degree. So, for d=3 random network and its regular counterpart (so-called dodecahedron) have approximately the same resilience. Our investigation is based on comparing the so-called cumulative D-spectra and the network DOWN probabilities as a function of node failure probability q.
Downloads
References
Barabasi, A. and Albert, R. (1999). Emergence of scaling in random networks,
Science, V. 286, No. 5439, p. 509-512.
Cormen, T. (2001). Introduction to Algorithms, MIT Press.
Elperin,T., Gertsbakh, I. and Lomonosov, M. (1991). Estimation of network
reliability using graph evolution models, IEEE Transactions on Reliability,
TR-40, p. 572-581.
Gertsbakh, I. and Shpungin, Y. (2009). Models of Network Reliability:
Analysis, Combinatorics and Monte Carlo. CRC Press.
Gertsbakh, I and Y. Shpungin (2011). Probabilistic description of network
behavior under random attack on its nodes, Proc. of the International
Conference on Risk Analysis, ICRA4, p. 105-112.
Gertsbakh, I and Y. Shpungin (2011). Network Reliability and Resilience,
Springer Briefs in Electrical and Computer Engineering, Springer.
Mitzenmacher, M. and Upfal, E. (2005). Probability and Computing,
Cambridge University Press.
Samaniego F. (1985). On closure of the IFR class under formation of coherent
systems, IEEE Transactions on Reliability Theory, TR-34, p. 69-72.
Samaniego, F. (2007). System Signatures and Their Application in
Engineering Reliability, Springer.
