Covert networks: How hard is it to hide?

Pa Jash Dey, Sourav Medya

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations

Abstract

Covert networks arc 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 leaders) from being detected via these measures by introducing new edges Waniek et al (72] show that the corresponding computational problem, called Hiding Leader, is NP-complete for the degree and closeness centrality measures Wc 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-1) factor approximation algorithm for any constant e > 0 unless there is a'/2 factor polynomial time algorithm for the Densest k-Subgraph problem which would be considered a significant breakthrough We empirically establish that our 2 factor approximation algorithm frequently finds out a near optimal solution On the contrary, for the corc centrality measure, we show that the Hiding Leader problem does not admit any (1- A ) In n factor approximation algorithm for any constant a (0.1) unless P = NP even when the core centrality of every leader is only 3 Hence, our work shows that, although classical complexity theoretic framework fails to shed any light on relative difficulty of Hiding Leader for different centrality measures, the problem is significantly "harder" for the core centrality measure than the degree centrality one.

Original languageEnglish (US)
Title of host publication18th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2019
PublisherInternational Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS)
Pages628-637
Number of pages10
ISBN (Electronic)9781510892002
StatePublished - 2019
Externally publishedYes
Event18th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2019 - Montreal, Canada
Duration: May 13 2019May 17 2019

Publication series

NameProceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS
Volume2
ISSN (Print)1548-8403
ISSN (Electronic)1558-2914

Conference

Conference18th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2019
Country/TerritoryCanada
CityMontreal
Period5/13/195/17/19

Keywords

  • Algorithms
  • Approximation algorithm
  • Centrality
  • Core
  • Covert network
  • Densest subgraph
  • Hiding in networks
  • Network design
  • Social influence
  • Social network analysis

ASJC Scopus subject areas

  • Artificial Intelligence
  • Software
  • Control and Systems Engineering

Fingerprint

Dive into the research topics of 'Covert networks: How hard is it to hide?'. Together they form a unique fingerprint.

Cite this