How Members of Covert Networks Conceal the Identities of Their Leaders

Marcin Waniek, Tomasz P. Michalak, Michael Wooldridge, Talal Rahwan

Research output: Contribution to journalArticlepeer-review


Centrality measures are the most commonly advocated social network analysis tools for identifying leaders of covert organizations. While the literature has predominantly focused on studying the effectiveness of existing centrality measures or developing new ones, we study the problem from the opposite perspective, by focusing on how a group of leaders can avoid being identified by centrality measures as key members of a covert network. More specifically, we analyze the problem of choosing a set of edges to be added to a network to decrease the leaders' ranking according to three fundamental centrality measures, namely, degree, closeness, and betweenness. We prove that this problem is NP-complete for each measure. Moreover, we study how the leaders can construct a network from scratch, designed specifically to keep them hidden from centrality measures. 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.

Original languageEnglish (US)
Article number12
JournalACM Transactions on Intelligent Systems and Technology
Issue number1
StatePublished - Feb 2022


  • Social networks
  • centrality
  • complexity analysis.
  • covert networks

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Artificial Intelligence


Dive into the research topics of 'How Members of Covert Networks Conceal the Identities of Their Leaders'. Together they form a unique fingerprint.

Cite this