Abstract

In a networked system, any change in the underlying network structure, such as node and link removals due to an attack, could severely affect the overall system behavior. Typically, by adding more links and connections between nodes, networks can be made structurally robust. However, this approach is not always feasible, especially in sparse networks. In this paper, we aim to improve the structural robustness in networks using the notions of diversity and trustiness. Diversity means that nodes in a network are of different types and have many variants. Trustiness means that a small subset of nodes are immune to failures and attacks. We show that by combining diversity and trustiness within the network, we can significantly limit the attacker’s ability to change the underlying network structure by strategically removing nodes. Using pairwise connectivity as a measure, we show that by appropriately distributing trusted nodes and assigning types to nodes, network robustness can be significantly improved. We analyze the complexity of diversifying and computing a set of trusted nodes, and then present heuristics to compute attacks consisting of node removals. We also present heuristics to defend networks against such attacks by distributing node types and trusted nodes. Finally, we evaluate our results on various networks to demonstrate the usefulness of our approach.