Computational Analysis of Connectivity Games with Applications to the Investigation of Terrorist Networks

Michalak, Tomasz P.; Rahwan, Talal; Szczepanski, Piotr L.; Skibski, Oskar; Narayanam, Ramasuri; Jennings, Nicholas R.; Wooldridge, Michael J.

Computational Analysis of Connectivity Games with Applications to the Investigation of Terrorist Networks

Tomasz P. Michalak, Talal Rahwan, Piotr L. Szczepanski, Oskar Skibski, Ramasuri Narayanam, Nicholas R. Jennings, Michael J. Wooldridge

Download BibTeX Cite

Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence. Pages 293-300.

Abstract

We study a recently developed centrality metric to identify key players in terrorist organisations due to Lindelauf et al. [2011]. This metric, which involves computation of the Shapley value for connectivity games on graphs proposed by Amer and Gimenez [2004], was shown to produce substantially better results than previously used standard centralities. In this paper, we present the first computational analysis of this class of coalitional games, and propose two algorithms for computing Lindelauf et al.'s centrality metric. Our first algorithm is exact, and runs in time linear by number of connected subgraphs in the network. As shown in the numerical simulations, our algorithm identifies key players in the WTC 9/11 terrorist network, constructed of 36 members and 125 links, in less than 40 minutes. In contrast, a general-purpose Shapley value algorithm would require weeks to solve this problem. Our second algorithm is approximate and can be used to study much larger networks.

Tomasz P. Michalak, Talal Rahwan, Piotr L. Szczepanski, Oskar Skibski, Ramasuri Narayanam, Nicholas R. Jennings, and Michael J. Wooldridge. 2013. Computational Analysis of Connectivity Games with Applications to the Investigation of Terrorist Networks. In Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence, IJCAI-13. IJCAI, 293–300. https://ijcai.org/proceedings/2013/52

@inproceedings{ijcai2013p52,
  title     = {Computational Analysis of Connectivity Games with Applications to the Investigation of Terrorist Networks},
  author    = {Michalak, Tomasz P. and Rahwan, Talal and Szczepanski, Piotr L. and Skibski, Oskar and Narayanam, Ramasuri and Jennings, Nicholas R. and Wooldridge, Michael J.},
  booktitle = {Proceedings of the Twenty-Third International Joint Conference on
               Artificial Intelligence, {IJCAI-13}},
  publisher = {AAAI Press / International Joint Conferences on Artificial Intelligence},
  editor    = {Francesca Rossi},
  pages     = {293--300},
  year      = {2013},
  month     = {8},
  url       = {https://ijcai.org/proceedings/2013/52},
}

TY  - CPAPER
TI  - Computational Analysis of Connectivity Games with Applications to the Investigation of Terrorist Networks
AU  - Michalak, Tomasz P.
AU  - Rahwan, Talal
AU  - Szczepanski, Piotr L.
AU  - Skibski, Oskar
AU  - Narayanam, Ramasuri
AU  - Jennings, Nicholas R.
AU  - Wooldridge, Michael J.
T2  - Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence, IJCAI-13
PB  - AAAI Press / International Joint Conferences on Artificial Intelligence
PY  - 2013
SP  - 293
EP  - 300
UR  - https://ijcai.org/proceedings/2013/52
ER  -