STEvent: Spatio-temporal event model for social network discovery

Abstract

Spatio-temporal data concerning the movement of individuals over space and time contains latent information on the associations among these individuals. Sources of spatio-temporal data include usage logs of mobile and Internet technologies. This article defines a spatio-temporal event by the co-occurrences among individuals that indicate potential associations among them. Each spatio-temporal event is assigned a weight based on the precision and uniqueness of the event. By aggregating the weights of events relating two individuals, we can determine the strength of association between them. We conduct extensive experimentation to investigate both the efficacy of the proposed model as well as the computational complexity of the proposed algorithms. Experimental results on three real-life spatio-temporal datasets cross-validate each other, lending greater confidence on the reliability of our proposed model.

References

1. Adamic, L. A. and Adar, E. 2003. Friends and neighbors on the Web. Social Netw. 25, 3, 211--230.
2. Borgs, C., Chayes, J., Mahdian, M., and Saberi, A. 2004. Exploring the community structure of newsgroups. In Proceedings of the 10th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, New York, 783--787.
3. Boyd, D. M. 2004. Friendster and publicly articulated social networking. In Extended Abstracts of the Conference on Human Factors and Computing Systems. 1279--1282.
4. Carley, K. 1991. A theory of group stability. Amer. Soc. Rev. 56, 3, 331--354.
5. Choudhury, T. and Pentland, A. 2003. Sensing and modeling human networks using the Sociometer. In Proceedings of the 7th IEEE International Symposium on Wearable Computing. IEEE, Los Alamitos, CA, 216--222.
6. Domingos, P. and Richardson, M. 2001. Mining the network value of customers. In Proceedings of the 7th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, New York, 57--66.
7. Eagle, N. and Pentland, A. 2006. Reality mning: Sensing complex social systems. Person Ubiquitous Comput. 10, 4, 255--268.
8. Faloutsos, C., McCurley, K. S., and Tomkins, A. 2004. Fast discovery of connection sub- graphs. In Proceedings of the 10th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, New York, 118--127.
9. Kempe, D., Kleinberg, J., and Tardos, E. 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. ACM, New York, 137--146.
10. Krebs, V. E. 2002. Mapping networks of terrorist cells. Connections 24, 3, 43--52.
11. Kumar, R., Novak, J., Raghavan, P., and Tomkins, A. 2004. Structure and evolution of blogspace. Comm. ACM 47, 12, 35--39.
12. Lampe, C., Ellison, N., and Steinfield, C. 2006. A face(book) in the crowd: Social searching vs. social browsing. In Proceedings of the 20th ACM Conference on Computer Supported Cooperative Work. ACM, New York, 167--170.
13. Lin, S. and Chalupsky, H. 2003. Unsupervised link discovery in multi-relational data via rarity analysis. In Proceedings of the 3rd IEEE International Conference on Data Mining, IEEE, Los Alamitos, CA, 171--178.
14. McPherson, M., Smith-Lovin, L., and Cook, J. M. 2001. Birds of a feather: homophily in social networks. Annual Rev. Sociology 27, 415--444.
15. Resig, J., Dawara, S., Homan, C. M., and Teredesai, A. 2004. Extracting social networks from instant messaging populations. In Proceedings of the Workshop on Link Analysis and Group Detection (in conjunction with the 10th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining).
16. Richardson, M. and Domingos, P. 2002. Mining knowledge-sharing sites for viral marketing. In Proceedings of the 8th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, New York, 61--70.
17. Schwartz, M. F. and Wood, D. C. M. 1993. Discovering shared interests using graph analysis. Comm. ACM 36, 8, 78--89.
18. Terry, M., Mynatt, E., Ryall, K., and Leigh, D. 2002. Social net: Using patterns of physical proximity over time to infer shared interests. In Extended Abstracts of the ACM Conference on Human Factors in Computing Systems. ACM, New York, 816--817.
19. Walpole, R. E., Myers, R. H., Myers, S. L., and Ye, K. 2002. Probability & Statistics for Engineers & Scientists 7th Ed., Prentice-Hall, Englewood Cliffs, NJ.
20. Wang, Y., Lim, E., and Hwang, S. 2003. On mining group patterns of mobile users. In Proceedings of the 14th International Conference on Database and Expert Systems Applications. 287--296.
21. Wasserman, S. and Faust, K. 1994. Social Network Analysis: Methods and Applications. Cambridge University Press.
22. Xu, J. J. and Chen, H. 2005. CrimeNet explorer: A framework for criminal network knowledge discovery. ACM Trans. Inform. Syst. 23, 2, 201--226.
23. Yu, B. and Singh, M. P. 2003. Searching social networks. In Proceedings of the 2nd Joint Conference on Autonomous Agents and Multiagent Systems. ACM, New York, 65--72.
24. Zhang, J. and van Alstyne, M. 2004. SWIM: Fostering social network based information search. In Extended Abstracts on Human Factors in Computing Systems. ACM, New York, 1568--1568.

Index Terms

• Applied computing

  • Law, social and behavioral sciences

• Information systems

  • Information storage systems

    • Storage architectures

      • Storage network architectures

• Mathematics of computing

  • Discrete mathematics

    • Graph theory