Constructing Provably Robust Scale-Free Networks

Scale-free networks have been described as robust to random failures but vulnerable to targeted attacks. We show that their degree sequences admit realizations that are, in fact, provably robust against any vertex removal strategy. We propose an algorithm that constructs such realizations almost surely, requiring only linear time and space. Our experiments confirm the robustness of the networks generated by this algorithm against adaptive and non-adaptive vertex removal strategies.