Home | Browse | Search | Credits | About
Register | User Area | DL-Harvest | Help
DLIST

Fighting organized crimes: using shortest-path algorithms to identify associations in criminal networks

Xu, Jennifer J. and Chen, Hsinchun (2004) Fighting organized crimes: using shortest-path algorithms to identify associations in criminal networks. Decision Support Systems 38(3):pp. 473-487.

Full text available as:
PDF - Requires Adobe Acrobat Reader or other PDF viewer.

Abstract

Effective and efficient link analysis techniques are needed to help law enforcement and intelligence agencies fight organized crimes such as narcotics violation, terrorism, and kidnapping. In this paper, we propose a link analysis technique that uses shortest-path algorithms, priority-first-search (PFS) and two-tree PFS, to identify the strongest association paths between entities in a criminal network. To evaluate effectiveness, we compared the PFS algorithms with crime investigators’ typical association-search approach, as represented by a modified breadth-first-search (BFS). Our domain expert considered the association paths identified by PFS algorithms to be useful about 70% of the time, whereas the modified BFS algorithm’s precision rates were only 30% for a kidnapping network and 16.7% for a narcotics network. Efficiency of the two-tree PFS was better for a small, dense kidnapping network, and the PFS was better for the large, sparse narcotics network.

EPrint Type:Journal Article (Paginated)
Keywords:National Science Digital Library, NSDL, Artificial Intelligence Lab, AI Lab
Subjects:Artificial Intelligence
ID Code:534
Deposited On:29 October 2004
Alternative Locations:http://ai.bpa.arizona.edu/go/papers.html
Eprint Statistics:View statistics for this eprint
Tell A Colleague:Tell a colleague about it.

[1] M. Ali, F. Kamoun, Neural networks for shortest path computation and routing in computer networks, IEEE Transactions on Neural Networks 4 (5) (1993) 941–953.

[2] T. Anderson, L. Arbetter, A. Benawides, A. Longmore-Etheridge, Security works, Security Management 38(17) (1994) 17– 20.

[3] F. Araujo, B. Ribeiro, L. Rodrigues, A neural network for shortest path computation, IEEE Transactions on Neural Networks 12 (5) (2001) 1067–1073.

[4] T. Asano, D. Kirkpatrick, C. Yap, Pseudo approximation algorithms, with applications to optimal motion planning, Proceedings of the Eighteenth Annual Symposium on Computational Geometry (Barcelona, Spain), 2002, pp. 170-178.

[5] M. Chau, J. Xu, H. Chen, Extracting meaningful entities from police narrative reports, Proceedings of the National Conference on Digital Government Research (Los Angeles, CA), 2002, pp. 271– 275.

[6] H. Chen, K.J. Lynch, Automatic construction of networks of concepts characterizing document databases, IEEE Transactions on Systems, Man and Cybernetics 22 (5) (1992) 885– 902.

[7] N.A. Chinchor, Overview of MUC-7/MET-2, Proceedings of the Seventh Message Understanding Conference (MUC-7),1998.

[8] W.F. Coady, Automated link analysis: artificial intelligence based tool for investigators, Police Chief 52 (9) (1985) 22–23.

[9] T.H. Cormen, C.E. Leiserson, R.L. Rivest, Introduction to Algorithms, MIT Press, Cambridge, MA, 1991.

[10] G. Dantzig, On the shortest route through a network, Management Science 6 (1960) 187– 190.

[11] E. Dijkstra, A note on two problems in connection with graphs, Numerische Mathematik 1 (1959) 269– 271.

[12] J. Evans, E. Minieka, Optimization Algorithms for Networks and Graphs, Marcel Dekker, New York, 1992.

[13] R.W. Floyd, Algorithm 97: shortest path, Communications of the ACM 5 (6) (1962) 345– 370.

[14] H.G. Goldberg, T.E. Senator, Restructuring databases for knowledge discovery by consolidation and link formation, Proceedings of 1998 AAAI Fall Symposium on Artificial Intelligence and Link Analysis, AAAI Press, Menlo Park, CA, 1998.

[15] H.G. Goldberg, R.W.H. Wong, Restructuring transactional data for link analysis in the FinCen AI System, Proceedings of 1998 AAAI Fall Symposium on Artificial Intelligence and Link Analysis, AAAI Press, Menlo Park, CA, 1998.

[16] W.R. Harper, D.H. Harris, The application of link analysis to police intelligence, Human Factors 17 (2) (1975) 157– 164.

[17] R.V. Hauck, H. Atabakhsh, P. Ongvasith, H. Gupta, H. Chen, Using coplink to analyze criminal-justice data, IEEE Computer 35 (3) (2002) 30– 37.

[18] R.V. Helgason, J.L. Kennington, B.D. Stewart, The one-toone shortest-path problem: an empirical analysis with the two-tree dijkstra algorithm, Computational Optimization and Applications 1 (1993) 47– 75.

[19] P. Klerks, The network paradigm applied to criminal organizations: theoretical nitpicking or a relevant doctrine for investigators? Recent developments in The Netherlands, Connections 24 (3) (2001) 53–65.

[20] V.E. Krebs, Mapping networks of terrorist cells, Connections 24 (3) (2001) 43–52.

[21] R. Lee, Automatic information extraction from documents: a tool for intelligence and law enforcement analysts, Proceedings of 1998 AAAI Fall Symposium on Artificial Intelligence and Link Analysis, AAAI Press, Menlo Park, CA, 1998.

[22] D. McAndrew, The structural analysis of criminal networks, in: D. Canter, L. Alison (Eds.), The Social Psychology of Crime: Groups, Teams, and Networks, Offender Profiling Series, Aldershot, Dartmouth, vol. III, 1999.

[23] C.E. Perkins, P. Bhagwat, Highly dynamic Destination- Sequenced Distance-Vector routing (DSDV) for mobile computers, Proceedings of SIGCOMM Symposium on Communications Architectures and Protocols, London, UK, 1994, pp. 212–225.

[24] M.K. Sparrow, The application of network analysis to criminal intelligence: an assessment of the prospects, Social Networks 13 (1991) 251– 274.

[25] K.M. Tolle, H. Chen, Comparing noun phrasing techniques for use with Medical Digital Library tools, Journal of the American Society for Information Science 51 (4) (2000) 352–370.

[26] Z. Wang, J. Crowcroft, Analysis of shortest-path routing algorithms in a dynamic network environment, ACM Computer Communication Review 22 (2) (1992) 63–71.

[27] S. Wasserman, K. Faust, Social Network Analysis: Methods and Applications, Cambridge Univ. Press, Cambridge, 1994.

EPrints dLIST, an open access archive for the Information Sciences, is supported by the School of Information Resources and Library Science and Learning Technologies Center, University of Arizona. Established in 2002, dLIST has a global Advisory Board and is a part of the Information Technology & Society Research Lab. Open Archives
Contact: Admin | Donate