COMPARING RANDOM AND REGULAR NETWORK RESILIANCE AGAINST RANDOM ATTACK ON THEIR NODES

  • Ilya B. Gertsbakh Department of Mathematics, Ben-Gurion University, P.O.Box 653, Beer-Sheva 84105, Israel
  • Yoseph Shpungin 2Software Engineering Department, Sami Shamoon College of Engineering, Beer-Sheva 84100, Israel
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

Download data is not yet available.
Published
2013-04-09
Section
Articles