Using an edge-dual graph and k-connectivity to identify strong connections in social networks

ABSTRACT

How close two entities are in social network is a key factor of SNA (Social Network Analysis). Recent studies of social networks contain a large number of entities and huge number of relations/connections in the networks. Efficiently and accurately analyzing relationships in the network is important component of SNA, especially for law enforcement. In this paper we propose using the edge-dual graph to transform the traditional social network graph to a relation context oriented graph and using modified k-connectivity concepts to evaluate the robustness of the relations. We also describe an implementation of a system based on a 450GB data source, involving 5 million people in Alabama. We use this large scale implementation to evaluate the performance and correctness of the proposal. Our evaluation suggests that using this relation context oriented technology will help to construct a more accurate social network.

REFERENCES

• 1: Wasserman, S and Faust, K. 1994. Social network analysis: methods and applications. Cambridge University Press. 4--10
• 2: Howard Rheingold, The Virtual Community: Homesteading on the Electronic Frontier, MIT Press, Cambridge, MA, 2000
• 3: Yasmin H. Said , Edward J. Wegman , Walid K. Sharabati , John T. Rigsby, Social networks of author-coauthor relationships, Computational Statistics & Data Analysis, v.52 n.4, p.2177-2184, January, 2008 [doi>10.1016/j.csda.2007.07.021]
• 4: Kossinets, G and Watts, D. J. 2006. Empirical Analysis of an Evolving Social Network. Science, vol. 311 (Jan, 2006), 88--90.
• 5: Hsinchun Chen , Wingyan Chung , Jennifer Jie Xu , Gang Wang , Yi Qin , Michael Chau, Crime Data Mining: A General Framework and Some Examples, Computer, v.37 n.4, p.50-56, April 2004 [doi>10.1109/MC.2004.1297301]
• 6: Goldberg, H. G and Wong, R. W. H. 1998. Restructuring databases for knowledge discovery by consolidation and link information. In Proceedings of 1998 AAAI Fall Symposium on Artificial Intelligence and Link Analysis (Menlo Park, CA, 1998).
• 7: Goldberg, H. G and Wong, R. W. H. 1998. Restructuring transactional data for link analysis in the FinCen AI system. In Proceedings of 1998 AAAI Fall Symposium on Artificial Intelligence and Link Analysis (Menlo Park, CA, 1998).
• 8: 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
• 9: Jennifer J. Xu , Hsinchun Chen, Fighting organized crimes: using shortest-path algorithms to identify associations in criminal networks, Decision Support Systems, v.38 n.3, p.473-487, December 2004 [doi>10.1016/S0167-9236(03)00117-9]
• 10: Watts, D. J. and Strogatz, S. 1998. Collective dynamics of 'small-world' networks. Nature, vol. 393 (Jun, 1998), 440--442.
• 11: Barabasi, A. L., Jeong, H., Neda, Z., Ravasz, E., Schubert, A. and Vicsek, T. 2002. Evolution of the social network of scientific collaborations. Physica A 311, (3--4) (2002), 590--614.
• 12: Harary, F. 1969. Graph Theory. 45--46
• 13: Moody, J. and White, D. R. 2003. Structural Cohesion and Embeddedness: A Hierarchical Concept of Social Groups. American Sociological Review, vol. 68 (2003), 103--127.
• 14: Clark, J. 1991. A first look at graph theory. World Scientific, 1991.
• 15: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 16: Web site: http://www.jgraph.com/

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.5 INFORMATION INTERFACES AND PRESENTATION (I.7)
      H.5.3 Group and Organization Interfaces

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.5 Model Development
          Subjects: Modeling methodologies

General Terms:
Design

Keywords:
k-connectivity, crime investigation, law enforcement, social network analysis, strong connections