  Random intersection graphs have received much attention recently and been
used in a wide range of applications ranging from key predistribution in
wireless sensor networks to modeling social networks. For these graphs, each
node is equipped with a set of objects in a random manner, and two nodes have
an undirected edge in between if they have at least one object in common. In
this paper, we investigate connectivity and robustness in a general random
intersection graph model. Specifically, we establish sharp asymptotic zero-one
laws for k-connectivity and k-robustness, as well as the asymptotically exact
probability of k-connectivity, for any positive integer k. The k-connectivity
property quantifies how resilient is the connectivity of a graph against node
or edge failures, while k-robustness measures the effectiveness of
local-information-based consensus algorithms (that do not use global graph
topology information) in the presence of adversarial nodes. In addition to
presenting the results under the general random intersection graph model, we
consider two special cases of the general model, a binomial random intersection
graph and a uniform random intersection graph, which both have numerous
applications as well. For these two specialized graphs, our results on
asymptotically exact probabilities of k-connectivity and asymptotic zero-one
laws for k-robustness are also novel in the literature.
