Bypass rewiring and extreme robustness of Eulerian networks

Abstract

A concept of bypass rewiring on directed networks is proposed, and random bypass rewiring on infinite directed random networks is analytically and numerically investigated with double generating function formalisms and simulations. As a result, it is derived that random bypass rewiring makes infinite directed (undirected) random networks extremely robust for arbitrary occupation probabilities if and only if in-degree of every node except a fixed number of nodes is equal to the out-degree (every node except a finite number of nodes has even degree); random bypass rewiring can make the percolation threshold 0 on infinite directed (undirected) random networks. From the results on infinite random networks, it is generalized that a finite network has a strongly connected spanning subnetwork which has an Eulerian path or cycle if and only if there exists an way of bypass rewiring to make the finite network extremely robust for every combination of removed nodes; Eulerian networks are extremely robust with bypass rewiring for every combination of removed nodes. The generalized results say that bypass rewiring improves connectivity and robustness of not only infinite networks but also real-world networks, like the Internet, with a finite number of nodes.