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

Tomasz P. Michalak , Piotr Lech Szczepański , Ramasuri Narayanam , Talal Rahwan , Nicholas R. Jenninges , Oskar Skibski , Michael J. Wooldridge


We study a recently developed centrality metric to identify key players in terrorist organisations due to Lindelauf et al. [2013]. 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.
Author Tomasz P. Michalak
Tomasz P. Michalak,,
, Piotr Lech Szczepański (FEIT / IN)
Piotr Lech Szczepański,,
- The Institute of Computer Science
, Ramasuri Narayanam
Ramasuri Narayanam,,
, Talal Rahwan
Talal Rahwan,,
, Nicholas R. Jenninges
Nicholas R. Jenninges,,
, Oskar Skibski
Oskar Skibski,,
, Michael J. Wooldridge
Michael J. Wooldridge,,
Book Rossi Francesca (eds.): Proceedings of the 23rd International Joint Conference on Artificial Intelligence, 2013, AAAI Press, ISBN 978-1-57735-633-2, 3266 p.
ProjectDevelopment of new methods and algorithms in the following areas: computer graphics, artificial intelligence, and information systems, and distributed systems . Project leader: Rybiński Henryk, , Phone: +48 22 234 7731, start date 29-05-2012, planned end date 31-12-2012, end date 30-11-2013, II/2012/DS/1, Completed
WEiTI Działalność statutowa
Languageen angielski
Score (nominal)15
Score sourceconferenceIndex
ScoreMinisterial score = 10.0, 02-02-2020, BookChapterMatConfByIndicator
Ministerial score (2013-2016) = 15.0, 02-02-2020, BookChapterMatConfByIndicator
Citation count*3 (2014-08-30)
Share Share

Get link to the record

* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or Perish system.
Are you sure?