On the Construction of Covert Networks

Centrality measures are widely used to identify leaders of covert networks. We study how a group of such leaders can avoid being detected by such measures. More concretely, we study the hardness of choosing a set of edges that can be added to the network in order to decrease the leaders' ranking according to two fundamental centrality measures, namely degree, and closeness. We prove that this problem is NP-complete for each measure. We then study how the leaders can construct a network from scratch, designed specifically for them to hide in disguise. We identify a network structure that not only guarantees to hide the leaders to a certain extent, but also allows them to spread their influence across the network.