CrimeNet explorer: a framework for criminal network knowledge discovery

ABSTRACT

Knowledge about the structure and organization of criminal networks is important for both crime investigation and the development of effective strategies to prevent crimes. However, except for network visualization, criminal network analysis remains primarily a manual process. Existing tools do not provide advanced structural analysis techniques that allow extraction of network knowledge from large volumes of criminal-justice data. To help law enforcement and intelligence agencies discover criminal network knowledge efficiently and effectively, in this research we proposed a framework for automated network analysis and visualization. The framework included four stages: network creation, network partition, structural analysis, and network visualization. Based upon it, we have developed a system called CrimeNet Explorer that incorporates several advanced techniques: a concept space approach, hierarchical clustering, social network analysis methods, and multidimensional scaling. Results from controlled experiments involving student subjects demonstrated that our system could achieve higher clustering recall and precision than did untrained subjects when detecting subgroups from criminal networks. Moreover, subjects identified central members and interaction patterns between groups significantly faster with the help of structural analysis functionality than with only visualization functionality. No significant gain in effectiveness was present, however. Our domain experts also reported that they believed CrimeNet Explorer could be very useful in crime investigation.

REFERENCES

• 1: Aldenderfer, M. S. and Blashfield R. K. 1984. Cluster Analysis. Sage Publications, Beverly Hills, CA.
• 2: Anderson, T., Arbetter, L., Benawides, A., and Longmore-Etheridge, A. 1994. Security works. Sec. Manage. 38, 17--20.
• 3: Arabie, P., Boorman, S. A., and Levitt, P. R. 1978. Constructing blockmodels: How and why. J. Math. Psych. 17, 21--63.
• 4: Baker, W. E. and Faulkner R. R. 1993. The social organization of conspiracy: Illegal networks in the heavy electrical equipment industry. Amer. Soc. Rev. 58, 837--860.
• 5: Berkowitz, S. D. 1982. An Introduction to Structural Analysis: The Network Approach to Social Research. Butterworth, Toronto, Ont., Canada.
• 6: Breiger, R. L. 2004. The analysis of social networks. In Handbook of Data Analysis, M. A. Hardy and A. Bryman, Eds. Sage Publications, London, U.K. 505--526.
• 7: Breiger, R. L., Boorman, S. A., and Arabie, P. 1975. An algorithm for clustering relational data, with applications to social network analysis and comparison with multidimensional scaling. J. Math. Psych. 12, 328--383.
• 8: Burt, R. S. 1976. Positions in networks. Soc. Forces 55, 93--122.
• 9: Burt, R. S. 1980. Models of network structure. Ann. Rev. Soc. 6, 79--141.
• 10: Chen, H. and Lynch, K. J. 1992. Automatic construction of networks of concepts characterizing document databases. IEEE Trans. Syst. Man Cybernet. 22, 885--902.
• 11: Hsinchun Chen , Daniel Zeng , Homa Atabakhsh , Wojciech Wyzga , Jenny Schroeder, COPLINK: managing law enforcement data and knowledge, Communications of the ACM, v.46 n.1, January 2003 [doi>10.1145/602421.602441]
• 12: Jack S. Cook , Laura L. Cook, Social, ethical and legal issues of data mining, Data mining: opportunities and challenges, Idea Group Publishing, Hershey, PA, 2003
• 13: Dantzig, G. 1960. On the shortest route through a network. Manage. Sci. 6, 187--190.
• 14: Ron Davidson , David Harel, Drawing graphs nicely using simulated annealing, ACM Transactions on Graphics (TOG), v.15 n.4, p.301-331, Oct. 1996 [doi>10.1145/234535.234538]
• 15: Day, W. H. E. and Edelsbrunner, H. 1984. Efficient algorithms for agglomerative hierarchical clustering methods. J. Class. 1, 7--24.
• 16: Defays, D. 1977. An efficient algorithm for a complete link method. Comput. J. 20, 364--366.
• 17: Dijkstra, E. 1959. A note on two problems in connection with graphs. Numer. Math. 1, 269--271.
• 18: Evan, W. M. 1972. An organization-set model of interorganizational relations. In Interorganizational Decision-Making, M. Tuite, R. Chisholm, and M. Radnor, Eds. Aldine Publishers, Chicago, IL, 181--200.
• 19: Robert W. Floyd, Algorithm 97: Shortest path, Communications of the ACM, v.5 n.6, p.345, June 1962 [doi>10.1145/367766.368168]
• 20: Freeman, L. 1979. Centrality in social networks: Conceptual clarification. Soc. Netw. 1, 215--239.
• 21: Freeman, L. 2000. Visualizing social networks. J. Soc. Struct. 1. (Electronic journal; go to http://www.heinz.cmu.edu/project/INSNA/joss/index1.html.)
• 22: Galaskiewicz, J. and Krohn, K. 1984. Positions, roles, and dependencies in a community interorganization system. Sociolog. Quart. 25, 527--550.
• 23: Garton, L., Haythornthwaite, C., and Wellman, B. 1999. Studying online social networks. In Doing Internet Research, S. Jones, Ed. Sage Publications, London, UK, 75--105.
• 24: David Gibson , Jon Kleinberg , Prabhakar Raghavan, Inferring Web communities from link topology, Proceedings of the ninth ACM conference on Hypertext and hypermedia : links, objects, time and space---structure in hypermedia systems: links, objects, time and space---structure in hypermedia systems, p.225-234, June 20-24, 1998, Pittsburgh, Pennsylvania, United States [doi>10.1145/276627.276652]
• 25: Goldberg, H. G. and Senator, T. E. 1998. Restructuring databases for knowledge discovery by consolidation and link formation. In Proceedings of 1998 AAAI Fall Symposium on Artificial Intelligence and Link Analysis (Orlando, FL, Oct.). AAAI Press, Menlo Park, CA.
• 26: Harper, W. R. and Harris, D. H. 1975. The application of link analysis to police intelligence. Hum. Fact. 17, 157--164.
• 27: Roslin V. Hauck , Homa Atabakhsh , Pichai Ongvasith , Harsh Gupta , Hsinchun Chen, Using Coplink to Analyze Criminal-Justice Data, Computer, v.35 n.3, p.30-37, March 2002
• 28: Anil K. Jain , Richard C. Dubes, Algorithms for clustering data, Prentice-Hall, Inc., Upper Saddle River, NJ, 1988
• 29: A. K. Jain , M. N. Murty , P. J. Flynn, Data clustering: a review, ACM Computing Surveys (CSUR), v.31 n.3, p.264-323, Sept. 1999 [doi>10.1145/331499.331504]
• 30: Johnson, S. C. 1967. Hierarchical clustering schemes. Psychometrika 32, 241--254.
• 31: Jordan, P. W. 1998. An Introduction to Usability, Taylor and Francis, Bristol, PA.
• 32: King, B. 1967. Step-wise clustering procedures. J. Amer. Statist. Assoc. 62, 86--101.
• 33: Jon M. Kleinberg, Authoritative sources in a hyperlinked environment, Journal of the ACM (JACM), v.46 n.5, p.604-632, Sept. 1999 [doi>10.1145/324133.324140]
• 34: Klerks, P. 2001. The network paradigm applied to criminal organizations: Theoretical nitpicking or a relevant doctrine for investigators? Recent developments in the Netherlands. Connections 24, 53--65.
• 35: Krebs, V. E. 2001. Mapping networks of terrorist cells. Connections 24, 43--52.
• 36: Kruskal, J. B. 1964. Nonmetric multidimensional scaling: A numerical method. Psychometrika 29, 115--128.
• 37: Kruskal, J. B. and Wish, M. 1978. Multidimensional Scaling. Sage, Beverly Hills, CA.
• 38: Lance, G. N. and Williams, W. T. 1967. A general theory of classificatory sorting strategies: II. Clustering systems. Comput. J. 10, 271--277.
• 39: Lorrain, F. P. and White, H. C. 1971. Structural equivalence of individuals in social networks. J. Math. Soc. 1, 49--80.
• 40: McAndrew, D. 1999. The structural analysis of criminal networks. In The Social Psychology of Crime: Groups, Teams, and Networks. D. Canter and L. Alison, Eds. Dartmouth Publishing, Aldershot, UK, 53--94.
• 41: Murtagh, F. 1984. A survey of recent advances in hierarchical clustering algorithms which use cluster centers. Comput. J. 26, 354--359.
• 42: William H. Press , Saul A. Teukolsky , William T. Vetterling , Brian P. Flannery, Numerical recipes in C (2nd ed.): the art of scientific computing, Cambridge University Press, New York, NY, 1992
• 43: Ronfeldt, D. and Arquilla, J. 2001. What next for networks and netwars? In Networks and Netwars: The Future of Terror, Crime, and Militancy, J. Arquilla and D. Ronfeldt, Eds. Rand Press, Santa Monica, CA, 311--361.
• 44: Dmitri G. Roussinov , Hsinchun Chen, Document clustering for electronic meetings: an experimental comparison of two techniques, Decision Support Systems, v.27 n.1-2, p.67-79, Nov. 1999 [doi>10.1016/S0167-9236(99)00037-8 ]
• 45: Saether, M. and Canter, D. V. 2001. A structural analysis of fraud and armed robbery networks in Norway. In Proceedings of the 6th International Investigative Psychology Conference (Liverpool, UK, Jan.).
• 46: Mehran Sahami , Salim Yusufali , Michelle Q. W. Baldonaldo, SONIA: a service for organizing networked information autonomously, Proceedings of the third ACM conference on Digital libraries, p.200-209, June 23-26, 1998, Pittsburgh, Pennsylvania, United States [doi>10.1145/276675.276697]
• 47: Scott, J. 1991. Social Network Analysis. Sage Publications, London, UK.
• 48: Sibson, R. 1973. Slink: An optimally efficient algorithm for the single-line cluster method. Comput. J. 16, 30--45.
• 49: Sneath, P. H. A. 1957. The application of computers to taxonomy. J. Gen. Microbiol. 17, 201--226.
• 50: Sparrow, M. K. 1991. The application of network analysis to criminal intelligence: An assessment of the prospects. Soc. Netw. 13, 251--274.
• 51: Torgerson, W. S. 1952. Multidimensional scaling: Theory and method. Psychometrika 17, 401--419.
• 52: Ellen M Voorhees, Implementing agglomerative hierarchic clustering algorithms for use in document retrieval, Information Processing and Management: an International Journal, v.22 n.6, p.465-476, Dec. 1986 [doi>10.1016/0306-4573(86)90097-X ]
• 53: Ward Jr., J. H. 1963. Hierarchical grouping to optimize an objective function. J. Amer. Statist. Assoc. 58, 236--244.
• 54: Wasserman, S. and Faust, K. 1994. Social Network Analysis: Methods and Applications. Cambridge University Press, Cambridge, UK.
• 55: Wellman, B. 1988. Structural analysis: From method and metaphor to theory and substance. In Social structures: A network approach, B. Wellman and S. D. Berkowitz, Eds. Cambridge University Press, Cambridge, UK, 19--61.
• 56: White, H. C., Boorman, S. A., and Breiger, R. L. 1976. Social structure from multiple networks: I. Blockmodels of roles and positions. Amer. J. Soc. 81, 730--780.
• 57: Young, F. W. 1987. Multidimensional Scaling: History, Theory, and Applications. Lawrence Erlbaum Associates, Hillsdale, NJ.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.4 INFORMATION SYSTEMS APPLICATIONS
      H.4.2 Types of Systems
          Subjects: Decision support (e.g., MIS)

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.4 Systems and Software
          Subjects: Performance evaluation (efficiency and effectiveness)

General Terms:
Algorithms, Design, Experimentation, Performance

Keywords:
Law enforcement, clustering, complete-link algorithm, concept space, crime investigation, knowledge discovery, multidimensional scaling, precision and recall, social network analysis, visualization