Park Junsang, Hahn Sang Geun
Graduate School of Information Security, Korea Advanced Institute of Science and Technology, 291 Daehak-ro, Yuseong-gu, Daejeon 34141, Republic of Korea.
Department of Mathematical Sciences, Korea Advanced Institute of Science and Technology, 291 Daehak-ro, Yuseong-gu, Daejeon 34141, Republic of Korea.
Phys Rev E. 2016 Aug;94(2-1):022310. doi: 10.1103/PhysRevE.94.022310. Epub 2016 Aug 22.
A concept of bypass rewiring is introduced, and random bypass rewiring is analytically and numerically investigated with simulations. Our results show that bypass rewiring makes networks robust against removal of nodes including random failures and attacks. In particular, random bypass rewiring connects all nodes except the removed nodes on an even degree infinite network and makes the percolation threshold 0 for arbitrary occupation probabilities. In our example, the even degree network is more robust than the original network with random bypass rewiring, while the original network is more robust than the even degree networks without random bypass. We propose a greedy bypass rewiring algorithm which guarantees the maximum size of the largest component at each step, assuming which node will be removed next is unknown. The simulation result shows that the greedy bypass rewiring algorithm improves the robustness of the autonomous system of the Internet under attacks more than random bypass rewiring.
引入了旁路重新布线的概念，并通过模拟对随机旁路重新布线进行了分析和数值研究。我们的结果表明，旁路重新布线使网络对包括随机故障和攻击在内的节点移除具有鲁棒性。特别是，随机旁路重新布线在偶数度无限网络上连接除移除节点之外的所有节点，并使任意占据概率下的渗流阈值为0。在我们的示例中，具有随机旁路重新布线的偶数度网络比原始网络更鲁棒，而原始网络比没有随机旁路的偶数度网络更鲁棒。我们提出了一种贪婪旁路重新布线算法，该算法在假设接下来哪个节点将被移除未知的情况下，保证每一步最大组件的最大规模。模拟结果表明，贪婪旁路重新布线算法在攻击下比随机旁路重新布线更能提高互联网自治系统的鲁棒性。
