Abstract
Knowing patterns of relationship in a social network is very useful for law enforcement agencies to investigate collaborations among criminals, for businesses to exploit relationships to sell products, or for individuals who wish to network with others. After all, it is not just what you know, but also whom you know, that matters. However, finding out who is related to whom on a large scale is a complex problem. Asking every single individual would be impractical, given the huge number of individuals and the changing dynamics of relationships. Recent advancement in technology has allowed more data about activities of individuals to be collected. Such data may be mined to reveal associations between these individuals. Specifically, we focus on data having space and time elements, such as logs of people's movement over various locations or of their Internet activities at various cyber locations. Reasoning that individuals who are frequently found together are likely to be associated with each other, we mine from the data instances where several actors co-occur in space and time, presumably due to an underlying interaction. We call these spatio-temporal co-occurrences events, which we use to establish relationships between pairs of individuals. In this paper, we propose a model for constructing a social network from events, and provide an algorithm that mines these events from the data. Experiments on a real-life data tracking people's accesses to cyber locations have also yielded encouraging results.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Adamic, L.A. and E. Adar (2003), “Friends and Neighbors on the Web,” Social Networks, 25(3), 211–230.
Agrawal, R., S. Rajagopalan, R. Srikant, and Y. Xu (2003), “Mining Newsgroups Using Networks Arising from Social Behavior,” in Proceedings of the 12th International World Wide Web Conference, Budapest, Hungary, pp. 688–703.
Agrawal, R. and R. Srikant (1994), “Fast Algorithm for Mining Association Rules,” in Proceedings of the 20th International Conference on Very Large Databases, Santiago, Chile, pp. 487–499.
Agrawal, R. and R. Srikant (1995), “Mining Sequential Patterns,” in Proceedings of the 11th International Conference on Data Engineering, Taipei, Taiwan, pp. 3–14.
Berry, M.W. and M. Browne (2005), “Email Surveillance Using Nonnegative Matrix Factorization,” in Proceedings of the Workshop on Link Analysis, Counterterrorism, and Security (in conj. with SIAM International Conference on Data Mining), Newport Beach, CA, USA, pp. 45–54.
Boyd, D.M. (2004), “Friendster and Publicly Articulated Social Networking,” in Extended abstracts of the Conference on Human Factors and Computing Systems, Vienna, Austria, pp. 1279–1282.
Carley, K. (1991), “A Theory of Group Stability,” American Sociological Review, 56(3), 331–354.
Chapanond, A., M.S. Krishnamoorthy, and B. Yener (2005), “Graph Theoretic and Spectral Analysis of Enron Email Data,” in Proceedings of the Workshop on Link Analysis, Counterterrorism, and Security (in conj. with SIAM International Conference on Data Mining), Newport Beach, CA, USA, pp. 15–22.
Das, G., K. Lin, H. Mannila, G. Renganathan, and P. Smyth (1998), “Rule Discovery from Time Series,” in Proceedings of the 4th International Conference on Knowledge Discovery and Data Mining, New York, NY, USA, pp. 27–31.
Diesner, J. and K.M. Carley (2005), “Exploration of Communication Networks from the Enron Email Corpus,” in Proceedings of the Workshop on Link Analysis, Counterterrorism, and Security (in conj. with SIAM International Conference on Data Mining), Newport Beach, CA, USA, pp. 3–14.
Duan, Y., J. Wang, M. Kam, and J. Canny (2005), “A Secure Online Algorithm for Link Analysis on Weighted Graph,” in Proceedings of the Workshop on Link Analysis, Counterterrorism, and Security (in conj. with SIAM International Conference on Data Mining), Newport Beach, CA, USA, pp. 71–81.
Faloutsos, C., K.S. McCurley, and A. Tomkins (2004), “Connection Subgraphs in Social Networks,” in Proceedings of the Workshop on Link Analysis, Counterterrorism, and Privacy (in conj. with SIAM International Conference on Data Mining), Lake Buena Vista, FA, USA.
Keila, P.S. and D.B. Skillicorn (2005), “Structure in the Enron Email Dataset,” in Proceedings of the Workshop on Link Analysis, Counterterrorism, and Security (in conj. with SIAM International Conference on Data Mining), Newport Beach, CA, USA, pp. 55–64.
Kempe, D., J. Kleinberg, and E. Tardos, (2003), “Maximizing the Spread of Influence through a Social Network,” in Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Washington, D.C, USA, pp. 137–146.
Koperski, K. and J. Han, (1995), “Discovery of Spatial Association Rules in Geographic Information Databases,” in Proceedings of the 4th International Symposium on Advances in Spatial Databases, Portland, Maine, USA, pp. 47—66.
Krebs, V.E. (2002), “Mapping Networks of Terrorist Cells,” Connections, 24(3), 43–52.
Kumar, R., J. Novak, P. Raghavan, and A. Tomkins (2004), “Structure and Evolution of Blogspace,” Communications of the ACM, 47(12), 35–39.
Lehmann, S. (2005), “Live and Dead Nodes,” in Proceedings of the Workshop on Link Analysis, Counterterrorism, and Security (in conj. with SIAM International Conference on Data Mining), Newport Beach, CA, USA, pp. 65–70.
Lin, S. and H. Chalupsky (2003), “Unsupervised Link Discovery in Multi-Relational Data via Rarity Analysis,” in Proceedings of the 3rd IEEE International Conference on Data Mining, Melbourne, FL, USA, pp. 171–178.
Lu, H., L. Feng, and J. Han (2000), “Beyond Intratransaction Association Analysis: Mining Multidimensional Intertransaction Association Rules,” ACM Transactions on Information Systems, 18(4), 423–454.
Mannila, H., H. Toivonen, and A.I. Verkamo (1995), “Discovering Frequent Episodes in Sequences,” in Proceedings of the 1st International Conference on Knowledge Discovery and Data Mining, Montreal, Canada, pp. 210–215.
McCallum, A., A. Corrada-Emmanuel, and X. Wang (2005), “The Author-Recipient-Topic Model for Topic and Role Discovery in Social Networks, with Application to Enron and Academic Email,” in Proceedings of the Workshop on Link Analysis, Counterterrorism, and Security (in conj. with SIAM International Conference on Data Mining), Newport Beach, CA, USA, pp. 33–44.
Mukherjee, M. and L.B. Holder (2004), “Graph-Based Data Mining on Social Networks,” in Workshop on Link Analysis and Group Detection (in conj. with the 10th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining), Seattle, WA, USA.
Resig, J., S. Dawara, C.M. Homan, and A. Teredesai (2004), “Extracting Social Networks from Instant Messaging Populations,” in Workshop on Link Analysis and Group Detection (in conj. with the 10th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining), Seattle, WA, USA.
Richardson, M. and P. Domingo (2002), “Mining Knowledge-Sharing Sites for Viral Marketing,” in Proceedings of the 8th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Edmonton, Alberta, Canada, pp. 61–70.
Schwartz, M.F. and D.C.M. Wood (1993), “Discovering Shared Interests Using Graph Analysis,” Communications of the ACM, 36(8), 78–89.
Shekhar, S., S. Chawla, S. Ravada, A. Fetterer, X. Liu, and C. Lu (1999), “Spatial Databases—Accomplishments and Research Needs,” IEEE Transactions on Knowledge and Data Engineering, 11(1), 45–55.
Shekhar, S. and Y. Huang (2001), “Discovering Spatial Co-Location Patterns: A Summary of Results,” in Proceedings of the 7th International Symposium on Spatial and Temporal Databases, Redondo Beach, CA, USA, pp. 236–256.
Vlachos, M., G. Kollios, and D. Gunopulos (2002), “Discovering Similar Multidimensional Trajectories,” in Proceedings of the 18th International Conference on Data Engineering, San Jose, CA, USA, pp. 673–684.
Wang, Y., E. Lim, and S. Hwang (2003), “On Mining Group Patterns of Mobile Users,” in Proceedings of the 14th International Conference on Database and Expert Systems Applications, Prague, Czech Republic, pp. 287–296.
Wasserman, S. and K. Faust (1994), Social Network Analysis: Methods and Applications. Cambridge University Press.
Xu, J. and H. Chen (2004), “Fighting Organized Crimes: Using Shortest-Path Algorithms to Identify Associations in Criminal Networks,” Decision Support Systems, 38(3), 473–487.
Author information
Authors and Affiliations
Corresponding author
Additional information
Hady W. Lauw is a graduate student at the School of Computer Engineering, Nanyang Technological University, Singapore. His research interests include spatio-temporal data mining, social network discovery, and link analyisis. He has a BEng in computer engineering from Nanyang Technological University.
Ee-Peng Lim is an Associate Professor with the School of Computer Engineering, Nanyang Technological University, Singapore. He received his PhD from the University of Minnesota, Minneapolis in 1994 and B.Sc. in Computer Science from National University of Singapore. Ee-Peng's research interests include information integration, data/text/web mining, digital libraries, and wireless intelligence. He is currently an Associate Editor of the ACM Transactions on Information Systems (TOIS), International Journal of Digital Libraries (IJDL) and International Journal of Data Warehousing and Mining (IJDWM). He was the Program Co-Chair of the ACM/IEEE Joint Conference on Digital Libraries (JCDL 2004), and Conference/Program Co-Chairs of International Conference on Asian Digital Libraries (ICADL 2004). He has also served in the program committee of numerous international conferences. Dr Lim is a Senior Member of IEEE and a Member of ACM.
HweeHwa Pang received the B.Sc.—with first class honors—and M.S. degrees from the National University of Singapore in 1989 and 1991, respectively, and the PhD degree from the University of Wisconsin at Madison in 1994, all in Computer Science. He is currently an Associate Professor at the Singapore Management University. His research interests include database management systems, data security and quality, operating systems, and multimedia servers. He has many years of hands-on experience in system implementation and project management. He has also participated in transferring some of his research results to industry.
Teck-Tim Tan is an IT Manager (Operations) at the Centre for IT Services, Nanyang Technological University (NTU), Singapore. He administers and oversees NTU's campus-wide wireless LAN infrastructure which facilitates access to the University's vast IT resources and services practically anywhere on campus.
Rights and permissions
About this article
Cite this article
Lauw, H.W., Lim, EP., Pang, H. et al. Social Network Discovery by Mining Spatio-Temporal Events. Comput Math Organiz Theor 11, 97–118 (2005). https://doi.org/10.1007/s10588-005-3939-9
Issue Date:
DOI: https://doi.org/10.1007/s10588-005-3939-9