Hierarchy measurement for modeling network dynamics under directed attacks

A fundamental issue in the dynamics of complex systems is the resilience of the network in response to targeted attacks. This paper explores the local dynamics of the network attack process by investigating the order of removal of the nodes that have maximal degree, and shows that this dynamic network response can be predicted from the graph's initial connectivity. We demonstrate numerically that the maximal degree M(τ) of the network at time step τ decays exponentially with τ via a topology-dependent exponent. Moreover, the order in which sites are removed can be approximated by considering the network's “hierarchy” function $h$, which measures for each node $V_i$ how many of its initial nearest neighbors have lower degree versus those that have a higher one. Finally, we show that the exponents we identified for the attack dynamics are related to the exponential behavior of spreading activation dynamics. The results suggest that the function $h$, which has both local and global properties, is a novel nodal measurement for network dynamics and structure.

Figure 1

Example of the attack process, displayed from left to right. The node with the maximal degree ($k=6$) is marked in black and removed from the network. Then the next node with the maximal degree ($k=4$) is marked and removed. After two steps, the network breaks into two connected components.

Figure 2

An illustration of spreading activation, displayed from left to right. A node is randomly activated and then spreads the activation to its neighbors. The shading indicates the level of activation according to the activation scale shown at left.

Figure 3

Examples of exponential fits for normalized maximal degree $\tilde{M}$, normalized initial degree $\tilde{k}$, and normalized $\tilde{h}$ function, all plotted with respect to the removal order τ for (a)–(c) ER-random networks ($N=100$ and $\langle k\rangle =10$), (d)–(f) scale-free networks ($N=100$ and $\langle k\rangle =10$), and (g)–(i) EEG networks ($N=139$, $\langle k\rangle =20$).

Figure 4

Spearman ranked correlation between the removal order τ and the initial degree k (blue line) or the function $h$ (red dashed line), plotted with respect to percentage of nodes removed: (a) ER-random networks (averaged over 100 realizations with $N=400$ and $\langle k\rangle =10$), (b) scale-free networks (averaged over 100 realizations with $N=400$ and $\langle k\rangle =10$), and (c) EEG networks. Shaded errors indicate standard deviation.

Figure 5

Spearman ranked correlations between the removal time $\tau$ and the initial degree $k\left(r_k\right)$ or the function $h\left(r_h\right)$ at the end of the process (all nodes removed), plotted with respect to $p$ (percent of edges randomized) and averaged over 100 realizations with $N=400$ and $\langle k\rangle =10$. Error bars indicate standard deviation.

Figure 6

Activation exponents ${\mu }_s$ vs attack exponents ${\mu }_k$ for a graph of $N=400$ and $\langle k\rangle =10$, plotted for different values of randomization level $p$. The exponents for scale-free and ER-random graphs of same size and mean degree are plotted as well (blue asterisks). Error bars indicate standard deviation. The Spearman ranked correlation between ${\mu }_s$ and ${\mu }_k$ is $r_s=0.99$.

Figure 7

Behavior of attack exponents ${\mu }_k$ (a) and activation exponents ${\mu }_s$ (b) with respect to $p$ (percent of edges randomized) for graph sizes $N=\left(200,400,600\right)$. With our normalizations, the exponent ${\mu }_k$ depends on N for BA scale-free graphs (c), but not for ER-random graphs (d). Results are averaged over 100 network realizations. Error bars indicate standard deviation.