Optimal dismantling of criminal networks. A perspective from the mathematical and computational modeling
Main Article Content
Keywords
Complex systems, computational modeling, network models, game theory, delinquent networks, statistical mechanics, ICT
Abstract
This work deals with the study and comparison of different strategies for the optimal dismantling of delinquent networks, which aim to optimally identify the most relevant individuals in the network. The strategy of greater complexity that we have studied here, is based on the Katz-Bonacich centrality criteria as a measure of influence of the individuals in the network. This results in an NP-hard type of problem, therefore, in order to apply that criteria, we must use heuristic methods which allow us to find approximate solutions. In particular, the methods used in this work are the Monte Carlo and greedy algorithms. We compared their performance against less sophisticated strategies and we were able to find that these algorithms perform relatively better, which contributes to improve our understanding of these approaches. In addition, we discuss a model that was recently introduced, which justifies the use of Katz-Bonacich centrality from the point of view of game theory on networks.
Downloads
Download data is not yet available.
References
[1] L. E. Blume, W. A. Brock, S. N. Durlauf, and Y. M. Ioannides, “Identification of social interactions,” pp. 853–964, 2011. [Online]. Available: http://dx.doi.org/10.1016/B978-0-444-53707-2.00001-3 84
[2] S. N. Durlauf and Y. M. Ioannides, “Social interactions,” Annu. Rev. Econ., vol. 2, no. 1, pp. 451–478, 2010. [Online]. Available: http://www.annualreviews.org/doi/abs/10.1146/annurev.economics. 050708.143312?journalCode=economics 84
[3] M. O. Jackson and Others, Social and economic networks. Princeton University Press, 2008, vol. 3. [Online]. Available: http://www.nber.org/econometrics_minicourse_2014/Jackson-NBER-slides2014_lecture1.pdf 84, 85
[4] S. N. Durlauf, “How can statistical mechanics contribute to social science?” Proceedings of the National Academy of Sciences, vol. 96, no. 19, pp. 10 582–10 584, 1999. [Online]. Available: http://www.pnas.org/content/96/19/10582.full 84
[5] T. C. Schelling, “Dynamic models of segregation,” Journal of mathematical sociology, vol. 1, no. 2, pp. 143–186, 1971. [Online]. Available: http://dx.doi.org/10.1080/0022250X.1971.9989794 84
[6] S. Fortunato, M. Macy, and S. Redner, “Editorial,” Journal of Statistical Physics, vol. 151, no. 1-2, pp. 1–8, 2013. [Online]. Available: http://dx.doi.org/10.1007/s10955-013-0703-2 84
[7] M. O. Jackson and Y. Zenou, “Games on networks,” Handbook of game theory, vol. 4, p. 1, 2014. [Online]. Available: http://voxeu.org/sites/default/files/file/DP9127.pdf 85
[8] C. Ballester, Y. Zenou, and A. Calvó-Armengol, “Delinquent networks,” Journal of the European Economic Association, vol. 8, no. 1, pp. 34–61, 2010. [Online]. Available: https://dx.doi.org/10.1111/j.1542-4774.2010.tb00494.x85, 86, 87, 88, 92, 94, 99
[9] G. S. Becker, “Crime and punishment: An economic approach,” in Journal of Politixal Economy. Springer, 1968, vol. 76, no. 2, pp. 169–217. [Online]. Available: http://dx.doi.org/10.1086/259394 85
[10] S. N. Durlauf and D. S. Nagin, “The deterrent effect of imprisonment,” in Controlling Crime: Strategies and Tradeoffs, J. M. Philip Cook; Jens Ludwig;, Ed. University of Chicago Press, 2010, pp. 43–94. [Online]. Available: http://www.nber.org/chapters/c12078.pdf 85
[11] C. Ballester, A. Calvó-Armengol, and Y. Zenou, “Who’s who in networks. wanted: the key player,” Econometrica, vol. 74, no. 5, pp. 1403–1417, 2006.85
[12] M. B. Short, P. J. Brantingham, A. L. Bertozzi, and G. E. Tita, “Dissipation and displacement of hotspots in reaction-diffusion models of crime,” Proceedings of the National Academy of Sciences, vol. 107, no. 9, pp. 3961–3965, 2010. [Online]. Available: http://www.pnas.org/content/107/9/3961.full 85
[13] M. B. Gordon, “A random walk in the literature on criminality: A partial and critical view on some statistical analyses and modelling approaches,” European Journal of Applied Mathematics, vol. 21, no. 4-5, pp. 283–306, 2010. [Online]. Available: https://hal.archives-ouvertes.fr/hal-00404405/file/CrimeModeling_Gordonv2.pdf 85
[14] E. L. Glaeser, B. Sacerdote, and J. A. Scheinkman, “Crime and Social Interactions,” The Quarterly Journal of Economics, vol. 111, no. 2, pp. 507–548, 1996. [Online]. Available: http://dx.doi.org/10.2307/2946686 85
[15] K. Keizer, S. Lindenberg, and L. Steg, “The spreading of disorder,” Science, vol. 322, no. 5908, pp. 1681–1685, 2008. [Online]. Available: http://dx.doi.org/10.1126/science.1161405 85
[16] A. Calvó-Armengoi and Y. Zenou, “Social networks and crime decisions: The role of social structure in facilitating delinquent behavior,” International Economic Review, vol. 45, no. 3, pp. 939–958, 2004. [Online]. Available: http://www.jstor.org/stable/3663642 85
[17] C. Morselli, Inside criminal networks. Springer, 2009. [Online]. Available: http://dx.doi.org/10.1007/978-0-387-09526-4 85
[18] C. Moore and S. Mertens, The nature of computation. OUP Oxford, 2011. [Online]. Available: http://dannyreviews.com/h/Nature_Computation.html?iframe=true&width=90%& 86
[19] F. Altarelli, A. Braunstein, L. Dall’Asta, J. R. Wakeling, and R. Zecchina, “Containing Epidemic Outbreaks by Message-Passing Techniques,” Phys. Rev. X, vol. 4, no. 2, p. 21024, May 2014. [Online]. Available: http://dx.doi.org/10.1103/PhysRevX.4.021024 86
[20] C. E. A. Cabrera, E. J. A. Lotero, and V. G. Umaña, “Modelos epidemiológicos en redes: una presentación introductoria,” Boletín de Matemáticas, vol. 22, no. 1, pp. 21–37, 2015. [Online]. Available: http://www.revistas.unal.edu.co/index.php/bolma/article/viewFile/51844/51641 86
[21] E. Estrada, The Structure of Complex Networks: Theory and Applications. OUP Oxford, 2011. [Online]. Available: http://dx.doi.org/10.1093/acprof:oso/9780199591756.001.0001 86
[22] J. Von Neumann and O. Morgenstern, Theory of Games and Economic Behavior. Princeton University Press, 1947. 86, 87
[23] A. T. Villalón and A. M. Caraballo, “Un paseo por la historia de la Teoría de Juegos,” Boletín de Matemáticas, vol. 22, no. 1, pp. 77–95, 2015. [Online]. Available: http://www.revistas.unal.edu.co/index.php/bolma/article/view/51847 86, 87
[24] L. Katz, “A new status index derived from sociometric analysis,” Psychometrika, vol. 18, no. 1, pp. 39–43, 1953. [Online]. Available: http://dx.doi.org/10.1007/BF02289026 86
[25] P. Bonacich, “Power and Centrality: A Family of Measures,” American Journal of Sociology, vol. 92, no. 5, pp. pp. 1170–1182, 1987. [Online]. Available: http://www.jstor.org/stable/2780000 86
[26] R. Albert and A.-L. Barabási, “Statistical mechanics of complex networks,” Rev. Mod. Phys., vol. 74, no. 1, pp. 47–97, 2002. [Online]. Available: https://doi.org/10.1103/RevModPhys.74.47 86
[27] M. E. J. Newman, “Resource Letter CS-1: Complex Systems,” American Journal of Physics, vol. 79, no. 8, pp. 800–810, 2011. [Online]. Available: http://dx.doi.org/10.1119/1.3590372 86, 99
[28] J. Xu and H. Chen, “The Topology of Dark Networks,” Commun. ACM, vol. 51, no. 10, p. 58–65, 2008. [Online]. Available: https://doi.org/10.1145/1400181.1400198 87, 99
[29] P. W. Glimcher and E. Fehr, Neuroeconomics: Decision Making and the Brain. Elsevier Science, 2013. 87
[30] J. Realpe-Gomez, B. Szczesny, L. Dall’Asta, and T. Galla, “Fixation and escape times in stochastic game learning,” Journal of Statistical Mechanics: Theory and Experiment, vol. 2012, no. 10, p. P10022, 2012. [Online]. Available: http://stacks.iop.org/1742-5468/2012/i=10/a=P10022 87
[31] L. C. Freeman, “A set of measures of centrality based on betweenness,” Sociometry, vol. 40, no. 1, pp. 35–41, 1977. [Online]. Available: http://dx.doi.org/10.2307/3033543 89
[32] ——, “Centrality in social networks conceptual clarification,” Social networks, vol. 1, no. 3, pp. 215–239, 1978. [Online]. Available: http://leonidzhukov.ru/hse/2013/socialnetworks/papers/freeman79-centrality.pdf 89
[33] P. Bonacich and P. Lloyd, “Eigenvector-like measures of centrality for asymmetric relations,” Social Networks, vol. 23, no. 3, pp. 191–201, 2001. [Online]. Available: http://dx.doi.org/10.1016/S0378-8733(01)00038-7 89
[34] R. Ghosh, K. Lerman, T. Surachawala, K. Voevodski, and S.-h. Teng, “Non-conservative Diffusion and its Application to Social Network Analysis,” arXiv:1102.4639, p. 11, 2011. [Online]. Available: http://arxiv.org/abs/1102.4639 90
[35] A. K. Hartmann and M. Weigt, Phase Transitions in Combinatorial Optimization Problems: Basics, Algorithms and Statistical Mechanics. Wiley, 2006. 95, 96
[2] S. N. Durlauf and Y. M. Ioannides, “Social interactions,” Annu. Rev. Econ., vol. 2, no. 1, pp. 451–478, 2010. [Online]. Available: http://www.annualreviews.org/doi/abs/10.1146/annurev.economics. 050708.143312?journalCode=economics 84
[3] M. O. Jackson and Others, Social and economic networks. Princeton University Press, 2008, vol. 3. [Online]. Available: http://www.nber.org/econometrics_minicourse_2014/Jackson-NBER-slides2014_lecture1.pdf 84, 85
[4] S. N. Durlauf, “How can statistical mechanics contribute to social science?” Proceedings of the National Academy of Sciences, vol. 96, no. 19, pp. 10 582–10 584, 1999. [Online]. Available: http://www.pnas.org/content/96/19/10582.full 84
[5] T. C. Schelling, “Dynamic models of segregation,” Journal of mathematical sociology, vol. 1, no. 2, pp. 143–186, 1971. [Online]. Available: http://dx.doi.org/10.1080/0022250X.1971.9989794 84
[6] S. Fortunato, M. Macy, and S. Redner, “Editorial,” Journal of Statistical Physics, vol. 151, no. 1-2, pp. 1–8, 2013. [Online]. Available: http://dx.doi.org/10.1007/s10955-013-0703-2 84
[7] M. O. Jackson and Y. Zenou, “Games on networks,” Handbook of game theory, vol. 4, p. 1, 2014. [Online]. Available: http://voxeu.org/sites/default/files/file/DP9127.pdf 85
[8] C. Ballester, Y. Zenou, and A. Calvó-Armengol, “Delinquent networks,” Journal of the European Economic Association, vol. 8, no. 1, pp. 34–61, 2010. [Online]. Available: https://dx.doi.org/10.1111/j.1542-4774.2010.tb00494.x85, 86, 87, 88, 92, 94, 99
[9] G. S. Becker, “Crime and punishment: An economic approach,” in Journal of Politixal Economy. Springer, 1968, vol. 76, no. 2, pp. 169–217. [Online]. Available: http://dx.doi.org/10.1086/259394 85
[10] S. N. Durlauf and D. S. Nagin, “The deterrent effect of imprisonment,” in Controlling Crime: Strategies and Tradeoffs, J. M. Philip Cook; Jens Ludwig;, Ed. University of Chicago Press, 2010, pp. 43–94. [Online]. Available: http://www.nber.org/chapters/c12078.pdf 85
[11] C. Ballester, A. Calvó-Armengol, and Y. Zenou, “Who’s who in networks. wanted: the key player,” Econometrica, vol. 74, no. 5, pp. 1403–1417, 2006.85
[12] M. B. Short, P. J. Brantingham, A. L. Bertozzi, and G. E. Tita, “Dissipation and displacement of hotspots in reaction-diffusion models of crime,” Proceedings of the National Academy of Sciences, vol. 107, no. 9, pp. 3961–3965, 2010. [Online]. Available: http://www.pnas.org/content/107/9/3961.full 85
[13] M. B. Gordon, “A random walk in the literature on criminality: A partial and critical view on some statistical analyses and modelling approaches,” European Journal of Applied Mathematics, vol. 21, no. 4-5, pp. 283–306, 2010. [Online]. Available: https://hal.archives-ouvertes.fr/hal-00404405/file/CrimeModeling_Gordonv2.pdf 85
[14] E. L. Glaeser, B. Sacerdote, and J. A. Scheinkman, “Crime and Social Interactions,” The Quarterly Journal of Economics, vol. 111, no. 2, pp. 507–548, 1996. [Online]. Available: http://dx.doi.org/10.2307/2946686 85
[15] K. Keizer, S. Lindenberg, and L. Steg, “The spreading of disorder,” Science, vol. 322, no. 5908, pp. 1681–1685, 2008. [Online]. Available: http://dx.doi.org/10.1126/science.1161405 85
[16] A. Calvó-Armengoi and Y. Zenou, “Social networks and crime decisions: The role of social structure in facilitating delinquent behavior,” International Economic Review, vol. 45, no. 3, pp. 939–958, 2004. [Online]. Available: http://www.jstor.org/stable/3663642 85
[17] C. Morselli, Inside criminal networks. Springer, 2009. [Online]. Available: http://dx.doi.org/10.1007/978-0-387-09526-4 85
[18] C. Moore and S. Mertens, The nature of computation. OUP Oxford, 2011. [Online]. Available: http://dannyreviews.com/h/Nature_Computation.html?iframe=true&width=90%& 86
[19] F. Altarelli, A. Braunstein, L. Dall’Asta, J. R. Wakeling, and R. Zecchina, “Containing Epidemic Outbreaks by Message-Passing Techniques,” Phys. Rev. X, vol. 4, no. 2, p. 21024, May 2014. [Online]. Available: http://dx.doi.org/10.1103/PhysRevX.4.021024 86
[20] C. E. A. Cabrera, E. J. A. Lotero, and V. G. Umaña, “Modelos epidemiológicos en redes: una presentación introductoria,” Boletín de Matemáticas, vol. 22, no. 1, pp. 21–37, 2015. [Online]. Available: http://www.revistas.unal.edu.co/index.php/bolma/article/viewFile/51844/51641 86
[21] E. Estrada, The Structure of Complex Networks: Theory and Applications. OUP Oxford, 2011. [Online]. Available: http://dx.doi.org/10.1093/acprof:oso/9780199591756.001.0001 86
[22] J. Von Neumann and O. Morgenstern, Theory of Games and Economic Behavior. Princeton University Press, 1947. 86, 87
[23] A. T. Villalón and A. M. Caraballo, “Un paseo por la historia de la Teoría de Juegos,” Boletín de Matemáticas, vol. 22, no. 1, pp. 77–95, 2015. [Online]. Available: http://www.revistas.unal.edu.co/index.php/bolma/article/view/51847 86, 87
[24] L. Katz, “A new status index derived from sociometric analysis,” Psychometrika, vol. 18, no. 1, pp. 39–43, 1953. [Online]. Available: http://dx.doi.org/10.1007/BF02289026 86
[25] P. Bonacich, “Power and Centrality: A Family of Measures,” American Journal of Sociology, vol. 92, no. 5, pp. pp. 1170–1182, 1987. [Online]. Available: http://www.jstor.org/stable/2780000 86
[26] R. Albert and A.-L. Barabási, “Statistical mechanics of complex networks,” Rev. Mod. Phys., vol. 74, no. 1, pp. 47–97, 2002. [Online]. Available: https://doi.org/10.1103/RevModPhys.74.47 86
[27] M. E. J. Newman, “Resource Letter CS-1: Complex Systems,” American Journal of Physics, vol. 79, no. 8, pp. 800–810, 2011. [Online]. Available: http://dx.doi.org/10.1119/1.3590372 86, 99
[28] J. Xu and H. Chen, “The Topology of Dark Networks,” Commun. ACM, vol. 51, no. 10, p. 58–65, 2008. [Online]. Available: https://doi.org/10.1145/1400181.1400198 87, 99
[29] P. W. Glimcher and E. Fehr, Neuroeconomics: Decision Making and the Brain. Elsevier Science, 2013. 87
[30] J. Realpe-Gomez, B. Szczesny, L. Dall’Asta, and T. Galla, “Fixation and escape times in stochastic game learning,” Journal of Statistical Mechanics: Theory and Experiment, vol. 2012, no. 10, p. P10022, 2012. [Online]. Available: http://stacks.iop.org/1742-5468/2012/i=10/a=P10022 87
[31] L. C. Freeman, “A set of measures of centrality based on betweenness,” Sociometry, vol. 40, no. 1, pp. 35–41, 1977. [Online]. Available: http://dx.doi.org/10.2307/3033543 89
[32] ——, “Centrality in social networks conceptual clarification,” Social networks, vol. 1, no. 3, pp. 215–239, 1978. [Online]. Available: http://leonidzhukov.ru/hse/2013/socialnetworks/papers/freeman79-centrality.pdf 89
[33] P. Bonacich and P. Lloyd, “Eigenvector-like measures of centrality for asymmetric relations,” Social Networks, vol. 23, no. 3, pp. 191–201, 2001. [Online]. Available: http://dx.doi.org/10.1016/S0378-8733(01)00038-7 89
[34] R. Ghosh, K. Lerman, T. Surachawala, K. Voevodski, and S.-h. Teng, “Non-conservative Diffusion and its Application to Social Network Analysis,” arXiv:1102.4639, p. 11, 2011. [Online]. Available: http://arxiv.org/abs/1102.4639 90
[35] A. K. Hartmann and M. Weigt, Phase Transitions in Combinatorial Optimization Problems: Basics, Algorithms and Statistical Mechanics. Wiley, 2006. 95, 96