Miltiadis Allamanis
Salvatore Scellato
Cecilia Mascolo
ABSTRACT
Connections established by users of online social networks are influenced by mechanisms such as preferential attachment and triadic closure. Yet, recent research has found that geographic factors also constrain users: spatial proximity fosters the creation of online social ties. While the effect of space might need to be incorporated to these social mechanisms, it is not clear to which extent this is true and in which way this is best achieved.
To address these questions, we present a measurement study of the temporal evolution of an online location-based social network. We have collected longitudinal traces over 4 months, including information about when social links are created and which places are visited by users, as revealed by their mobile check-ins. Thanks to this fine-grained temporal information, we test and compare whether different probabilistic models can explain the observed data adopting an approach based on likelihood estimation, quantitatively comparing their statistical power to reproduce real events. We demonstrate that geographic distance plays an important role in the creation of new social connections: node degree and spatial distance can be combined in a gravitational attachment process that reproduces real traces. Instead, we find that links arising because of triadic closure, where users form new ties with friends of existing friends, and because of common focus, where connections arise among users visiting the same place, appear to be mainly driven by social factors.
We exploit our findings to describe a new model of network growth that combines spatial and social factors. We extensively evaluate our model and its variations, demonstrating that it is able to reproduce the social and spatial properties observed in our traces. Our results offer useful insights for systems that take advantage of the spatial properties of online social services.
Supplemental Material
Available for Download
Summary Review Documentation for "Evolution of a Location-based Online Social Network: Analysis and Models", Authors: M. Allamanis, S. Scellato, and C. Mascolo
- L. Backstrom, E. Sun, and C. Marlow. Find me if you can: improving geographical prediction with social and spatial proximity. In Proceedings of WWW'10, 2010. Google Scholar
Digital Library
- A.-L. Barabási and R. Albert. Emergence of Scaling in Random Networks. Science, 286(5439), 1999.Google Scholar
- A. Barrat, M. Barthélemy, and A. Vespignani. The effects of spatial constraints on the evolution of weighted complex networks. Journal of Statistical Mechanics, (05), 2005.Google ScholarCross Ref
- M. Barthélemy. Crossover from scale-free to spatial networks. Europhysics Letters, 63, 2003.Google Scholar
- M. Barthélemy. Spatial Networks. Physics Reports, 499, 2011.Google Scholar
- V. Carrothers. A Historical Review of the Gravity and Potential Concepts of Human Interaction. Journal of the American Institute of Planners, 22, 1956.Google Scholar
- D. J. Crandall, L. Backstrom, D. Cosley, S. Suri, D. Huttenlocher, and J. M. Kleinberg. Inferring social ties from geographic coincidences. PNAS, 107(52):22436--22441, 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 Proceedings of UbiComp'10, Copenhagen, Denmark, 2010. Google ScholarDigital Library
- P. Expert, T. S. Evans, V. D. Blondel, and R. Lambiotte. Uncovering space-independent communities in spatial networks. PNAS, 108(19):7663--7668, May 2011.Google ScholarCross Ref
- S. L. Feld. The Focused Organization of Social Ties. American Journal of Sociology, 86(5):1015--1035, 1981.Google ScholarCross Ref
- D. Fetterly, M. Manasse, M. Najork, and J. Wiener. A large-scale study of the evolution of web pages. In Proceedings of WWW'03, 2003. Google ScholarDigital Library
- M. Kaiser and C. C. Hilgetag. Spatial growth of real-world networks. PRE, 69:036103, Mar 2004.Google ScholarCross Ref
- T. Karagiannis, C. Gkantsidis, D. Narayanan, and A. Rowstron. Hermes: clustering users in large-scale e-mail services. In Proceedings of SoCC'10, 2010. Google ScholarDigital Library
- D. Krackhardt and M. S. Handcock. Heider vs Simmel: emergent features in dynamic structures. In Proceedings of ICML'06, 2006. Google ScholarDigital Library
- R. Kumar, J. Novak, and A. Tomkins. Structure and Evolution of Online Social Networks. In Proceedings of KDD'06, 2006. Google ScholarDigital Library
- R. Lambiotte, V. Blondel, C. Dekerchove, E. Huens, C. Prieur, Z. Smoreda, and P. Vandooren. Geographical dispersal of mobile communication networks. Physica A, 387(21), 2008.Google Scholar
- J. Leskovec, L. Backstrom, R. Kumar, and A. Tomkins. Microscopic evolution of social networks. In Proceedings of KDD'08, 2008. Google ScholarDigital Library
- J. Leskovec, J. Kleinberg, and C. Faloutsos. Graphs over time: densification laws, shrinking diameters and possible explanations. In Proceedings of KDD'05, 2005. Google ScholarDigital Library
- D. Liben-Nowell and J. Kleinberg. The link prediction problem for social networks. In Proceedings of CIKM'03, 2003. Google ScholarDigital Library
- D. Liben-Nowell, J. Novak, R. Kumar, P. Raghavan, and A. Tomkins. Geographic routing in social networks. PNAS, 102(33):11623--11628, 2005.Google ScholarCross Ref
- R. N. Lichtenwalter, J. T. Lussier, and N. V. Chawla. New perspectives and methods in link prediction. In Proceedings of KDD'10, 2010. Google ScholarDigital Library
- A. Mislove, M. Marcon, K. P. Gummadi, P. Druschel, and B. Bhattacharjee. Measurement and Analysis of Online Social Networks. In Proceedings of IMC '07, 2007. Google ScholarDigital Library
- J.-P. Onnela, S. Arbesman, M. C. González, A.-L. Barabási, and N. A. Christakis. Geographic constraints on social network groups. PLoS ONE, 6(4):e16939, 2011.Google ScholarCross Ref
- J. M. Pujol, V. Erramilli, G. Siganos, X. Yang, N. Laoutaris, P. Chhabra, and P. Rodriguez. The little engine(s) that could: scaling online social networks. In Proceedings of SIGCOMM'10, 2010. Google ScholarDigital Library
- D. M. Romero and J. Kleinberg. The Directed Closure Process in Hybrid Social-Information Networks, with an Analysis of Link Formation on Twitter. In Proceedings of ICWSM'11, 2011.Google Scholar
- S. Scellato, A. Noulas, R. Lambiotte, and C. Mascolo. Socio-spatial Properties of Online Location-based Social Networks. In Proceedings of ICWSM'11, 2011.Google Scholar
- S. Scellato, A. Noulas, and C. Mascolo. Exploiting place features in link prediction on location-based social networks. In Proceedings of KDD'11, 2011. Google ScholarDigital Library
- G. Simmel. The Sociology of Georg Simmel. The Free Press, 1908.Google Scholar
- S. Traverso, K. Huguenin, V. Trestian, I. Erramilli, N. Laoutaris, and K. Papagiannaki. TailGate: Handling Long-Tail Content with a Little Help from Friends. In Proceedings of WWW'12, 2012. Google ScholarDigital Library
- B. M. Waxman. Routing of multipoint connections. Selected Areas in Communications, 6(9):1617--1622, 1988. Google ScholarDigital Library
- M. P. Wittie, V. Pejovic, L. Deek, K. C. Almeroth, and B. Y. Zhao. Exploiting locality of interest in online social networks. In Proceedings of CONEXT'10, 2010. Google ScholarDigital Library
- C. Wiuf, M. Brameier, O. Hagberg, and M. P. H. Stumpf. A likelihood approach to analysis of network data. PNAS, 103(20):7566--7570, 2006.Google ScholarCross Ref
Index Terms
- Evolution of a location-based online social network: analysis and models
Recommendations
Structure and evolution of online social networks
KDD '06: Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data miningIn this paper, we consider the evolution of structure within large online social networks. We present a series of measurements of two such networks, together comprising in excess of five million people and ten million friendship links, annotated with ...
Investigating Homophily in Online Social Networks
WI-IAT '10: Proceedings of the 2010 IEEE/WIC/ACM International Conference on Web Intelligence and Intelligent Agent Technology - Volume 01Similarity breeds connections, the principle of homophily, has been well studied in existing sociology literature. %Several studies have observed this phenomena by conducting surveys on human subjects. These studies have concluded that new ties are ...
Personality and location-based social networks
We investigate personality and use of location based social networks.We examine the five-factor personality model against places that users check-in at.Conscientiousness positively correlates with the number of venues visited.Openness positively ...
Comments