@article{2cd07c63c6af4ab5a0f391891dcd72d8,
title = "How Members of Covert Networks Conceal the Identities of Their Leaders",
abstract = "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.",
keywords = "Social networks, centrality, complexity analysis., covert networks",
author = "Marcin Waniek and Michalak, {Tomasz P.} and Michael Wooldridge and Talal Rahwan",
note = "Funding Information: Marcin Waniek was supported by the Polish National Science Centre Grant No. 2015/17/N/ST6/03686. Michael Wooldridge was supported by the European Research Council under Advanced Grant No. 291528 (“RACE”). Tomasz Michalak was supported for this version of this work by the Polish National Science Centre Grant No. 2016/23/B/ST6/03599, and for the previous, conference version by the Polish National Science Centre Grant No. 2014/13/B/ST6/01807 and the European Research Council under Advanced Grant No. 291528 (“RACE”). Authors{\textquoteright} addresses: M. Waniek, New York University Abu Dhabi, Saadiyat Island, 129188, Abu Dhabi, UAE and University of Warsaw, Banacha 2, 02-097 Warsaw, Poland; email: mjwaniek@nyu.edu; T. P. Michalak, University of Warsaw, Banacha 2, 02-097 Warsaw, Poland; email: tpm@mimuw.edu.pl; M. Wooldridge, University of Oxford, Wolfson Building, Parks Road, OX1 3QD, Oxford, UK; email: mjw@cs.ox.ac.uk; T. Rahwan, New York University Abu Dhabi, Saadiyat Island, 129188, Abu Dhabi, UAE; email: tr72@nyu.edu. Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from permissions@acm.org. {\textcopyright} 2021 Copyright held by the owner/author(s). Publication rights licensed to ACM. 2157-6904/2021/11-ART12 $15.00 https://doi.org/10.1145/3490462 Publisher Copyright: {\textcopyright} 2021 Copyright held by the owner/author(s). Publication rights licensed to ACM.",
year = "2022",
month = feb,
doi = "10.1145/3490462",
language = "English (US)",
volume = "13",
journal = "ACM Transactions on Intelligent Systems and Technology",
issn = "2157-6904",
publisher = "Association for Computing Machinery (ACM)",
number = "1",
}