Avalanche-size distribution of Cayley tree

Abstract

Attacks on networks is a very important issue in developing strategies of eradicating spreads of malicious phenomena in networks, such as epidemics and fake information. This field of research is referred to as networks immunization. The traditional approach to evaluating the effectiveness of attacks on networks focuses on measuring macro parameters related to the entire attack, such as the critical probability of a percolation occurrence in the network [Formula: see text] and the relative size of the largest component in the network, known as the giant component, but not considering the attack on a micro perspective, which is the analysis of node removals, during an attack, themselves, their characteristics and results. In this paper we present and apply the last method of focusing on the micro scale of an attack. Based on the theory of percolation in networks, we analyze the phenomenon of an avalanche which results due to a single node removal from a network. An avalanche is a state in which a removal of a single node from the giant component of a network leads to the disconnection of additional nodes. This process significantly contributes to the fragmentation (immunization) of the network, comparing to the impact of the initial node removal alone. Specifically, we focus on the size parameter of an avalanche, which is the number of nodes that are disconnected from the giant component due to a single node removal. Relating to a random attack on a network of the type of Cayley tree, we derive analytically the distribution of the sizes of avalanches that occur during the entire attack on it, until the network is dismantled (immunized) and the attack is terminated.

Figure 1

Illustration of the model on a Cayley tree with $Z=3$ neighbors and $L=3$ layers: (a) CT before an attack begins. All the nodes are in white mode. The root of the tree and the three branches emanating from the root are marked in the sketch. For clarity, only the nodes belonging to the bottom branch are depicted. (b) Stage one of an attack—Node A is attacked. As a result, node A switches to the black mode, and its six descendants switch to the grey mode. Prior to this stage, all descendants of node A were in the white mode, so the attack on node A causes a complete avalanche of size 7 (node A and its six descendants). (c) Stage two of an attack—Node B is attacked. As a result, it is switches to the black mode. Since node B was in the grey mode, indicating disconnection from the root before this stage, the attack on node B leads to a null avalanche. (d) Stage three of an attack—Node C is attacked. Consequently, it is switches to the black mode. Since node A which is a son of node C was already attacked prior to this stage, the current stage has no impact on that sub-branch containing node A and its descendants. On the other hand, the nodes in the other sub-branch of node C, including node D and its descendants, which were in the white mode before this stage, all switch to the grey mode. As not all descendants of node C were in the white mode before this stage, the current stage results in an incomplete avalanche of size 8 (node C, node D and node D’s six descendants).

Figure 2

(a,b) Presentation of the avalanche-size distribution for a CT with $Z=3$ neighbors. (a) Presentation of $P\left(S_0\right)$ as predicted by theory and obtained by simulations, versus $\frac{2}{L}$. The x-axis scale marks correspond to $\frac{2}{26},\frac{2}{25},\frac{2}{24}\dots ,\frac{2}{12}$ representing CTs with $L=26,25,24\dots ,12$ layers, respectively. At the top of each vertical dashed line, which corresponds to a specific scale mark of $\frac{2}{L}$, a red dot represents the value of $1-\frac{2}{L}$ as predicted by theory, and a blue circle represents the value of $P\left(S_0\right)$ as was obtained from simulations. The red line represents the graph of the line $1-\frac{2}{L}$. (b) Presentation of $P\left(S_C\right)$ as predicted by theory and obtained by simulations, versus $\frac{2}{L}$. At the top of each vertical dashed line, which corresponds to a specific scale mark of $\frac{2}{L}$, a red dot represents the value of $\frac{2}{L}$ as predicted by the theory, and a blue circle represents the value of $P\left(S_C\right)$ as was obtained from simulations. The red line represents the graph of the line $\frac{2}{L}$. Inset in panel (b) Bar graph showing the mean value of the ratio between $P\left(S_C\right)$ and $\frac{2}{L}$ for five subsets of L values: 12–14, 15–17, 18–20, 21–23 and 24–26. The averages were calculated over 1000 realizations.

Figure 3

(a,b) Presentation of the avalanche-size distribution for a CT with $Z=4$ neighbors. (a) Presentation of $P\left(S_0\right)$ as predicted by theory and observed in simulations, versus $\frac{3/2}{L}$. The x-axis scale marks correspond to $\frac{3/2}{16},\frac{3/2}{15},\frac{3/2}{14}\dots ,\frac{3/2}{10}$ representing CTs with $L=16,15,14\dots ,10$ layers, respectively. At the top of each vertical dashed line, which corresponds to a specific scale mark of $\frac{3/2}{L}$, a red dot represents the value of $1-\frac{3/2}{L}$ as predicted by theory, and a blue circle represents the value of $P\left(S_0\right)$ obtained from simulations. The red line represents the graph of the line $1-\frac{3/2}{L}$. (b) Presentation of $P\left(S_C\right)$ as predicted by theory and observed in simulations, versus $\frac{3/2}{L}$. At the top of each vertical dashed line, which corresponds to a specific scale mark of $\frac{3/2}{L}$, a red dot represents the value of $\frac{3/2}{L}$ as predicted by theory, and a blue circle represents the value of $P\left(S_C\right)$ obtained from simulations. The red line represents the graph of the line $\frac{3/2}{L}$. Inset in panel (b) Bar graph showing the mean value of the ratio between $P\left(S_C\right)$ and $\frac{3/2}{L}$ for three subsets of L values: 10–11, 12–14 and 15–16. The averages were calculated over 1000 realizations.