Attack tolerance

This article includes a list of general references, but it lacks sufficient corresponding inline citations. Please help to improve this article by introducing more precise citations. (February 2015) (Learn how and when to remove this message)

|

In the study of complex networks, attack tolerance refers to a network's robustness, or its ability to preserve overall connectivity and network diameter (the longest shortest path between nodes) when nodes are removed due to failures or attacks. This concept is key to understanding how networks—such as the internet, social networks, or power grids—resist disruption. Several graph metrics have been developed to measure this resilience, with algebraic connectivity (the second-smallest eigenvalue of the Laplacian matrix) considered the most effective indicator of network robustness among them.[1]

## Attack types

[edit]

If an attack was to be mounted on a network, it would not be through random nodes but ones that were the most significant to the network. Different methods of ranking are utilized to determine the nodes priority in the network.

### Average node degree

[edit]

This form of attack prioritizes the most connected nodes as the most important ones. This takes into account the network (represented by graph  G {\displaystyle G} ) changing over time, by analyzing the network as a series of snapshots (indexed by  j {\displaystyle j} ); we denote the snapshot at time  t j {\displaystyle t_{j}} by  G ( t j ) {\displaystyle G(t_{j})} . The average of the degree of a node, labeled  i {\displaystyle i} , within a given snapshot  d e g G ( t j ) {\displaystyle deg_{G(t_{j})}} , throughout a time interval (a sequence of  T {\displaystyle T} snapshots)  { t 1 , . . . , t T } {\displaystyle \\{t_{1},...,t_{T}\\}} , is given by:

d e g G ( i ; t 1 , t n ) = 1 T ∑ j = 1 T d e g G ( t j ) ( i ) {\displaystyle deg_{G}(i;t_{1},t_{n})=\textstyle {\frac {1}{T}}\sum _{j=1}^{T}{deg_{G(t_{j})}(i)}}

### Node persistence

[edit]

This form of attack prioritizes nodes that occur most frequently over a period of time. The equation below calculates the frequency that a node (i) occurs in a time interval  { t 1 , . . . , t T } {\displaystyle \\{t_{1},...,t_{T}\\}} . When the node is present during the snapshot then equation is equal to 1, but if the node is not present then it is equal to 0.

N p G ( i ; t 1 , t n ) = 1 T ∑ j = 1 T δ t j ( i ) {\displaystyle Np_{G}(i;t_{1},t_{n})=\textstyle {\frac {1}{T}}\sum _{j=1}^{T}{\delta _{t_{j}}(i)}}

Where

δ t j ( i ) = { 1 , if i ∈ V t j at t j t h time step. 0 , otherwise. {\displaystyle \delta _{t_{j}}(i)={\begin{cases}1,&{\text{if }}i\in V_{t_{j}}{\text{at }}t_{j}^{th}{\text{ time step.}}\\\0,&{\text{otherwise.}}\end{cases}}}

### Temporal closeness

[edit]

This form of attack prioritizes nodes by the summation of temporal distances from one node to all other nodes over a period of time. The equation below calculates the temporal distance of a node (i) by averaging the sum of all the temporal distances for the interval [t1,tn].[2]

C G ( i ; t 1 , t n ) = 1 ( N − 1 ) ∑ j ; j ≠ i d j i ( t 1 , t n ) {\displaystyle C_{G}(i;t_{1},t_{n})={\frac {1}{(N-1)}}\sum _{j;j\neq i}{d_{ji}(t_{1},t_{n})}}

## Network model tolerances

[edit]

Not all networks are the same, so it is no surprise that an attack on different networks would have different results. The common method for measuring change in the network is through the average of the size of all the isolated clusters, <s>, and the fraction of the nodes contained in the largest cluster, S.[3] When no nodes have been attacked, both S and <s> equal 1.

### Erdős–Rényi model

[edit]

Main article: Erdős–Rényi model

In the ER model, the network generated is homogeneous, meaning each node has the same number of links. This is considered to be an exponential network. When comparing the connectivity of the ER model when it undergoes random failures vs directed attacks, we are shown that the exponential network reacts the same way to a random failure as it does to a directed attack. This is due to the homogeneity of the network, making it so that it does not matter whether a random node is selected or one is specifically targeted. All the nodes on average are the same in degree therefore attacking one shouldn't cause anymore damage than attacking another. As the number of attacks go up and more nodes are removed, we observe that S decreases non-linearly and acts as if a threshold exists when a fraction of the nodes (f) has been removed, (f≈.28). At this point, S goes to zero. The average size of the isolated clusters behaves opposite, increasing exponentially to <s>= 2, also approaching the threshold line f≈.28, except decreases back to 1 after. This model was tested for a large range of nodes and proven to maintain the same pattern.[3]

### Scale-free model

[edit]

Main article: Scale-free network

In the scale-free model, the network is defined by its degree distribution following the power law,[4] which means that each node has no set number of links, unlike the exponential network. This makes the scale-free model more vulnerable because there are nodes that are more important than others, and if these nodes were to be deliberately attacked the network would break down. However this inhomogeneous network has its strengths when it comes to random failures. Due to the power law there are many more nodes in the system that have very few links, and probability estimates that these are the nodes that will be targeted (because there are more of them). Severing these smaller nodes will not affect the network as a whole and therefore allows the structure of the network to stay approximately the same. When the scale-free model undergoes random failures, S slowly decreases with no threshold-like behavior and <s> remains approximately 1. This indicates that the network is being broken apart one by one and not by large clusters. However, when the scale-free model undergoes deliberate attack the system behaves similarly to an exponential system, except it breaks down much quicker. As the number of attacks increases, S decreases with a threshold close to f=0.05, and <s> increases to the same threshold and then decreases back to one. The speed at which this type of network breaks down shows the vulnerability of common networks that are used everyday, such as the Internet.[5]

## References

[edit]

1. ^ Alenazi, Mohammed; Sterbenz, James (2015). "Comprehensive comparison and accuracy of graph metrics in predicting network resilience". 2015 11th International Conference on the Design of Reliable Communication Networks (DRCN). pp. 157–164\. doi:10.1109/DRCN.2015.7149007. ISBN 978-1-4799-7795-6. S2CID 14060719.
2. ^ Sur, Souvik; Ganguly, Niloy; Mukherjee, Animesh (2015). "Attack tolerance of correlated time-varying social networks with well-defined communities". Physica A: Statistical Mechanics and Its Applications. 420: 98–107\. Bibcode:2015PhyA..420...98S. doi:10.1016/j.physa.2014.08.074.
3. ^ a b Albert, Réka; Jeong, Hawoong; Barabási, Albert-László (2000). "The Internet's Achilles' Heel: Error and attack tolerance of complex networks". Nature. 406 (6794): 378–382\. arXiv:cond-mat/0008064. doi:10.1038/35019019. PMID 10935628. S2CID 1545338.
4. ^ BARABÁSI, ALBERT-LÁSZLÓ (2014). NETWORK SCIENCE.
5. ^ Sorokin, Alexey; Murphey, Robert; Thai, My; Pardalos, Panos (2012). Dynamics of Information Systems: Mathematical Foundations. Springer New York. ISBN 978-1-4614-3905-9.