Desmantelamiento óptimo de redes delincuenciales. Una perspectiva desde el modelado matemático y computacional
Main Article Content
Keywords
Sistemas complejos, modelado computacional, modelos en redes, teoría de juegos, redes delincuenciales, mecánica estadística, TICs
Resumen
El objetivo de este trabajo es estudiar y comparar diferentes estrategias para el desmantelamiento óptimo de redes delincuenciales, las cuales están representadas en algoritmos que permiten la identificación óptima de los individuos claves en la red. La estrategia de mayor complejidad se basa en la métrica de centralidad de Katz-Bonacich como medida de influencia en la red, y da lugar a un problema NP-difícil por lo que se debe recurrir a métodos heurísticos para encontrar soluciones aproximadas. Aquí se desarrolla un algoritmo basado en el método Monte Carlo y se compara con un método basado en algoritmos voraces introducido recientemente en la literatura. En este trabajo se compara además el desempeño de éstos con estrategias menos sofisticadas y se proporciona evidencia que dichos algoritmos se desempeñan relativamente bien, contribuyendo así a proporcionar un mejor entendimiento de éstos. Se discute además un modelo introducido recientemente que justifica el uso de la centralidad de Katz-Bonacich desde el punto de vista de la teoría de juegos sobre redes.
Descargas
Los datos de descargas todavía no están disponibles.
Referencias
[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