Efficient Network Dismantling via Node Explosive Percolation *

Shao-Meng Qin,Xiao-Long Ren,Lin-Yuan Lü

Table 1 Comparative results of the BPD algorithm, the fast ${\rm{NBA}^1}$ and fast ${\rm{NBA}^2}$ on twelve real-world networks. The number of nodes and edges of these networks are listed in the 2nd and 3rd column. The 4th column is the average degree of these networks. The general efficiency $R$ of the BPD algorithm, the fast ${\rm{NBA}^1}$ and fast ${\rm{NBA}^2}$ are listed in the 5th, 6th, and 7th column, correspondingly. We use boldface to highlight the minimum $R$ in the three algorithms. The relative improvement of the fast ${\rm{NBA}^1}$ and fast ${\rm{NBA}^2}$, denoted as $r^1$ and $r^2$ in the table, are listed in the 8th and 9th column, respectively.

Networks BPD fast NBA1 fast NBA2 r1 r2 RoadEU[32] * 0.0455 0.0195 0.0418 0.57 0.08 PPI[33] 0.0923 0.0789 0.0809 0.14 0.12 Grid[34] 0.0355 0.0097 0.0298 0.73 0.16 IntNet1[35] 0.0123 0.0092 0.0104 0.25 0.15 Authors[36] 0.0877 0.0763 0.0755 0.13 0.14 Citation[35] 0.293 0.2695 0.2601 0.08 0.11 P2P[35] 0.1155 0.1047 0.1038 0.08 0.11 Friend[35] 0.1028 0.0918 0.0893 0.11 0.13 Email[36] 0.0013 0.0008 0.0008 0.35 0.36 WebPage[37] 0.0494 0.0410 0.0433 0.17 0.13 RoadTX[37] 0.0127 0.0023 0.0070 0.82 0.45 intNet2[35] 0.0372 0.0308 0.0321 0.17 0.14