  Covert networks are social networks that often consist of harmful users.
Social Network Analysis (SNA) has played an important role in reducing criminal
activities (e.g., counter terrorism) via detecting the influential users in
such networks. There are various popular measures to quantify how influential
or central any vertex is in a network. As expected, strategic and influential
miscreants in covert networks would try to hide herself and her partners
(called {\em leaders}) from being detected via these measures by introducing
new edges. Waniek et al. show that the corresponding computational problem,
called Hiding Leader, is NP-Complete for the degree and closeness centrality
measures. We study the popular core centrality measure and show that the
problem is NP-Complete even when the core centrality of every leader is only
$3$. On the contrary, we prove that the problem becomes polynomial time
solvable for the degree centrality measure if the degree of every leader is
bounded above by any constant. We then focus on the optimization version of the
problem and show that the Hiding Leader problem admits a $2$ factor
approximation algorithm for the degree centrality measure. We complement it by
proving that one cannot hope to have any $(2-\varepsilon)$ factor approximation
algorithm for any constant $\varepsilon>0$ unless there is a $\varepsilon/2$
factor polynomial time algorithm for the Densest $k$-Subgraph problem which
would be considered a significant breakthrough.
