Robustness of complex networks with applications to random graphs

A notion of k-robustness for complex networks has received much attention recently. The motivation for this notion of robustness is to measure the effectiveness of local-information-based diffusion algorithms in the presence of adversarial nodes. In this paper, we first correct the relationship between k-robustness and k-connectivity studied in related work. Then we derive a sharp zero-one law for k-robustness in a random graph model called binomial random s-intersection graph, which has a wide range of applications. In such a graph, each node is equipped with a set of items following a binomial process, and any two nodes establish an undirected edge in between if and only if they have at least s common items. Our zero-one law improves relevant results in the literature.