Dashun Wang
ABSTRACT
Our understanding of how individual mobility patterns shape and impact the social network is limited, but is essential for a deeper understanding of network dynamics and evolution. This question is largely unexplored, partly due to the difficulty in obtaining large-scale society-wide data that simultaneously capture the dynamical information on individual movements and social interactions. Here we address this challenge for the first time by tracking the trajectories and communication records of 6 Million mobile phone users. We find that the similarity between two individuals' movements strongly correlates with their proximity in the social network. We further investigate how the predictive power hidden in such correlations can be exploited to address a challenging problem: which new links will develop in a social network. We show that mobility measures alone yield surprising predictive power, comparable to traditional network-based measures. Furthermore, the prediction accuracy can be significantly improved by learning a supervised classifier based on combined mobility and network measures. We believe our findings on the interplay of mobility patterns and social ties offer new perspectives on not only link prediction but also network dynamics.
- L. Adamic and E. Adar. Friends and neighbors on the web. Social Networks, 25(3):211--230, 2003.Google Scholar
Cross Ref
- M. Al Hasan, V. Chaoji, S. Salem, and M. Zaki. Link prediction using supervised learning. In SDM: Workshop on Link Analysis, Counter-terrorism and Security, 2006.Google Scholar
- L. Backstrom, E. Sun, and C. Marlow. Find me if you can: improving geographical prediction with social and spatial proximity. In WWW, pages 61--70, 2010. Google ScholarDigital Library
- D. Brockmann, L. Hufnagel, and T. Geisel. The scaling laws of human travel. Nature, 439(7075):462--465, 2006.Google ScholarCross Ref
- G. Caldarelli. Scale-free networks: complex webs in nature and technology. Oxford University Press, 2007.Google Scholar
- D. A. Cieslak and N. V. Chawla. Learning decision trees for unbalanced data. In ECML/PKDD, pages 241--256, 2008. Google ScholarDigital Library
- D. Crandall, L. Backstrom, D. Cosley, S. Suri, D. Huttenlocher, and J. Kleinberg. Inferring social ties from geographic coincidences. Proceedings of the National Academy of Sciences, 107(52):22436, 2010.Google ScholarCross Ref
- J. Cranshaw, E. Toch, J. Hong, A. Kittur, and N. Sadeh. Bridging the gap between physical location and online social networks. In Ubicomp, pages 119--128, New York, NY, USA, 2010. ACM. Google ScholarDigital Library
- N. Eagle and A. Pentland. Eigenbehaviors: Identifying structure in routine. Behavioral Ecology and Sociobiology, 63(7):1057--1066, 2009.Google ScholarCross Ref
- N. Eagle, A. Pentland, and D. Lazer. Inferring friendship network structure by using mobile phone data. Proceedings of the National Academy of Sciences, 106(36):15274, 2009.Google ScholarCross Ref
- D. Easley and J. Kleinberg. Networks, crowds, and markets: Reasoning about a highly connected world. Cambridge University Press, 2010. Google ScholarDigital Library
- F. Giannotti, M. Nanni, and D. Pedreschi. Efficient mining of temporally annotated sequences. In SDM, 2006.Google ScholarCross Ref
- F. Giannotti, M. Nanni, F. Pinelli, and D. Pedreschi. Trajectory pattern mining. In KDD, pages 330--339, 2007. Google ScholarDigital Library
- M. González, C. Hidalgo, and A.-L. Barabási. Understanding individual human mobility patterns. Nature, 453(7196):779--782, 2008.Google ScholarCross Ref
- Z. Huang, X. Li, and H. Chen. Link prediction approach to collaborative filtering. In JCDL, pages 141--142. ACM, 2005. Google ScholarDigital Library
- H. Jeung, Q. Liu, H. T. Shen, and X. Zhou. A hybrid prediction model for moving objects. In ICDE, pages 70--79, 2008. Google ScholarDigital Library
- L. Katz. A new status index derived from sociometric analysis. Psychometrika, 18(1):39--43, 1953.Google ScholarCross Ref
- G. Krings, F. Calabrese, C. Ratti, and V. Blondel. Urban gravity: a model for inter-city telecommunication flows. J. Stat. Mech.-Theor. Exp., page L07003, 2009.Google Scholar
- R. Lambiotte, V. Blondel, C. De Kerchove, E. Huens, C. Prieur, Z. Smoreda, and P. Van Dooren. Geographical dispersal of mobile communication networks. Physica A: Statistical Mechanics and its Applications, 387(21):5317--5325, 2008.Google ScholarCross Ref
- J. Leskovec, L. Backstrom, R. Kumar, and A. Tomkins. Microscopic evolution of social networks. In KDD, pages 462--470, 2008. Google ScholarDigital Library
- D. Liben-Nowell and J. M. Kleinberg. The link prediction problem for social networks. In CIKM, pages 556--559, 2003. Google ScholarDigital Library
- D. Liben-Nowell, J. Novak, R. Kumar, P. Raghavan, and A. Tomkins. Geographic routing in social networks. Proceedings of the National Academy of Sciences, 102(33):11623, 2005.Google ScholarCross Ref
- R. Lichtenwalter, J. T. Lussier, and N. V. Chawla. New perspectives and methods in link prediction. In KDD, pages 243--252, 2010. Google ScholarDigital Library
- A. Monreale, F. Pinelli, R. Trasarti, and F. Giannotti. Wherenext: a location predictor on trajectory pattern mining. In KDD, pages 637--646, 2009. Google ScholarDigital Library
- M. Morzy. Prediction of moving object location based on frequent trajectories. In ISCIS, pages 583--592, 2006. Google ScholarDigital Library
- M. Morzy. Mining frequent trajectories of moving objects for location prediction. In MLDM, pages 667--680, 2007. Google ScholarDigital Library
- J. P. Onnela, J. Saramaki, J. Hyvonen, G. Szabo, D. Lazer, K. Kaski, J. Kertesz, and A.-L. Barabasi. Structure and tie strengths in mobile communication networks. Proceedings of the National Academy of Sciences, 104(18):7332--7336, 2007.Google ScholarCross Ref
- M. Rivera, S. Soderstrom, and B. Uzzi. Dynamics of Dyads in Social Networks: Assortative, Relational, and Proximity Mechanisms. Annual Review of Sociology, 36:91--115, 2010.Google ScholarCross Ref
- C. Song, T. Koren, P. Wang, and A.-L. Barabási. Modelling the scaling properties of human mobility. Nature Physics, 2010.Google ScholarCross Ref
- C. Song, Z. Qu, N. Blumm, and A.-L. Barabasi. Limits of predictability in human mobility. Science, 327(5968):1018, 2010.Google ScholarCross Ref
- C. Wang, V. Satuluri, and S. Parthasarathy. Local probabilistic models for link prediction. In ICDM, pages 322--331, 2007. Google ScholarDigital Library
- G. Yavas, D. Katsaros, Ö. Ulusoy, and Y. Manolopoulos. A data mining approach for location prediction in mobile environments. Data Knowl. Eng., 54(2):121--146, 2005. Google ScholarDigital Library
Index Terms
- Human mobility, social ties, and link prediction
Recommendations
Link Prediction in Human Contact Networks Using Online Social Ties
CGC '13: Proceedings of the 2013 International Conference on Cloud and Green ComputingHuman contact traces has allowed researchers to study how mobile users contact each other in different environments. Most of these traces include other types of useful information such as users' social profiles and their online social connections. This ...
Friendship prediction and homophily in social media
Social media have attracted considerable attention because their open-ended nature allows users to create lightweight semantic scaffolding to organize and share content. To date, the interplay of the social and topical components of social media has ...
Learning to predict reciprocity and triadic closure in social networks
We study how links are formed in social networks. In particular, we focus on investigating how a reciprocal (two-way) link, the basic relationship in social networks, is developed from a parasocial (one-way) relationship and how the relationships ...
Comments