Hostname: page-component-586b7cd67f-2plfb Total loading time: 0 Render date: 2024-11-22T21:14:53.091Z Has data issue: false hasContentIssue false
  • English
  • Français

Stars, holes, or paths across your Facebook friends: A graphlet-based characterization of many networks

Published online by Cambridge University Press:  19 September 2019

Raphaël Charbey Open the ORCID record for Raphaël Charbey [Opens in a new window]  and
Christophe Prieur
Raphaël Charbey*
Affiliation:
Département LUSSI, IMT Atlantique, Lab-STICC, UMR CNRS 6285, F-29238 Brest, France
Christophe Prieur
Affiliation:
I3, CNRS, Telecom Paris, Institut Polytechnique de Paris (e-mail: [email protected])
*
*Corresponding author. Email: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

Network science gathers methods coming from various disciplines which sometimes hardly cross the boundaries between these disciplines. Widely used in molecular biology in the study of protein interaction networks, the enumeration, in a network, of all possible subgraphs of a limited size (usually around four or five nodes), often called graphlets, can only be found in a few works dealing with social networks. In the present work, we apply this approach to an original corpus of about 10,000 non-overlapping Facebook ego networks gathered from voluntary participants by a survey application. To deal with so many similar networks, we adapt the relative graphlet frequency to a measure that we call graphlet representativity, which we show to be more effective to classify random networks having slight structural differences. From our data, we produce two clusterings, one of graphlets (paths, star-like, holes, light triangles, and dense), one of networks. The latter is presented with a visualization scheme using our representativity measure. We describe the distinct structural characteristics of the five clusters of Facebook ego networks so obtained and discuss the empirical differences between results obtained with 4-node and 5-node graphlets. We also provide suggestions of follow-ups of this work, both in sociology and in network science.

Keywords

graphletsego networksbig Data
Type
Original Article
Information
Network Science , Volume 7 , Issue 4 , December 2019 , pp. 476 - 497
Copyright
© Cambridge University Press 2019 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Ali, W., Rito, T., Reinert, G., Sun, F., & Deane, C. M. (2014). Alignment-free protein interaction network comparison. Bioinformatics, 30(17), i430–i437.CrossRefGoogle ScholarPubMed
Artzy-Randrup, Y., Fleishman, S. J., Ben-Tal, N., & Stone, L. (2004). Comment on “network motifs: simple building blocks of complex networks” and “superfamilies of evolved and designed networks”. Science, 305(5687), 1107–1107.CrossRefGoogle Scholar
Backstrom, L., & Kleinberg, J. (2014). Romantic partnerships and the dispersion of social ties: A network analysis of relationship status on facebook. In Proceedings of the 17th ACM Conference on Computer Supported Cooperative Work & Social Computing, pp. 831–841. ACM.CrossRefGoogle Scholar
Barabási, A.-L., & Albert, R. (1999). Emergence of scaling in random networks. Science, 286(5439), 509–512.CrossRefGoogle ScholarPubMed
Barnes, J. A. (1954). Class and Committees in a Norwegian Island Parish. Human Relations, 7(1), 39–58.CrossRefGoogle Scholar
Bidart, C., & Lavenu, D. (2005). Evolutions of personal networks and life events. Social Networks, 27(4), 359–376.CrossRefGoogle Scholar
Blondel, V. D., Guillaume, J.-L., Lambiotte, R., & Lefebvre, E. (2008). Fast unfolding of communities in large networks. Journal of Statistical Mechanics: Theory and Experiment, 2008(10), P10008.CrossRefGoogle Scholar
Bornholdt, S., & Schuster, H. G. (2006). Handbook of Graphs and Networks: From the Genome to the Internet. Hoboken: John Wiley & Sons.Google Scholar
Bott, E. (1957). Family and Social Network: Roles, Norms and External Relationships in Ordinary Urban Families. London: Routledge.Google Scholar
Brandes, U., Robins, G., McCRANIE, A., & Wasserman, S. (2013). What is network science? Network Science, 1(01), 1–15.CrossRefGoogle Scholar
Brooks, B., Hogan, B., Ellison, N., Lampe, C., & Vitak, J. (2014). Assessing structural correlates to social capital in Facebook ego networks. Social Networks, 38(July), 1–15.CrossRefGoogle Scholar
Cunningham, P., Harrigan, M., Wu, G., & O’Callaghan, D. (2013). Characterizing ego-networks using motifs. Network Science, 1(02), 170–190.CrossRefGoogle Scholar
Easley, D., & Kleinberg, J. (2010). Networks, Crowds, and Markets: Reasoning About a Highly Connected World. Cambridge: Cambridge University Press.CrossRefGoogle Scholar
Faloutsos, M., Faloutsos, P., & Faloutsos, C. (1999). On power-law relationships of the internet topology. In ACM SIGCOMM Computer Communication Review, vol. 29, pp. 251–262. ACM.CrossRefGoogle Scholar
Faust, K. (2010). A puzzle concerning triads in social networks: Graph constraints and the triad census. Social Networks, 32(3), 221–233.CrossRefGoogle Scholar
Freeman, L. (2004). The development of social network analysis. A Study in the Sociology of Science, 1.Google Scholar
Friggeri, A., Chelius, G., & Fleury, E. (2011). Triangles to capture social cohesion. 2011 IEEE Third International Conference on Privacy, Security, Risk and Trust (PASSAT) and 2011 IEEE Third International Conference on Social Computing (SocialCom), pp. 258–265. IEEE.CrossRefGoogle Scholar
Harrigan, M., Archambault, D., Cunningham, P., & Hurley, N. (2012). Egonav: Exploring networks through egocentric spatializations. In Proceedings of the International Working Conference on Advanced Visual Interfaces, pp. 563–570. ACM.CrossRefGoogle Scholar
Hocevar, T., & Demsar, J. (2014). A combinatorial approach to graphlet counting. Bioinformatics, 30(4), 559–565.CrossRefGoogle ScholarPubMed
Hočevar, T, & Demšar, J. (2017). Combinatorial algorithm for counting small induced graphs and orbits. Plos One, 12(2), e0171428.CrossRefGoogle ScholarPubMed
Hogan, B. (2018). Social media giveth, social media taketh away: Facebook, friendships, and APIs. International Journal of Communication. preprint.Google Scholar
Holland, P. W., & Leinhardt, S. (1976). Local structure in social networks. Sociological Methodology, 7, 1–45.CrossRefGoogle Scholar
Holland, P. W., Laskey, K. B., & Leinhardt, S. (1983). Stochastic blockmodels: First steps. Social Networks, 5(2), 109–137.CrossRefGoogle Scholar
Kalmijn, M. (2012). Longitudinal analyses of the effects of age, marriage, and parenthood on social contacts and support. Advances in Life Course Research, 17(4), 177–190.CrossRefGoogle Scholar
Kovanen, L., Karsai, M., Kaski, K., Kertész, J., & Saramäki, J. (2011). Temporal motifs in time-dependent networks. Journal of Statistical Mechanics: Theory and Experiment, 2011(11), P11005.CrossRefGoogle Scholar
Milo, R. (2002). Network motifs: Simple building blocks of complex networks. Science, 298(5594), 824–827.CrossRefGoogle ScholarPubMed
Moreno, J. L. (1934). Who Shall Survive. vol. 58. New York: JSTOR.Google Scholar
Nasim, M., Charbey, R., Prieur, C., & Brandes, U. (2016). Investigating link inference in partially observable networks: Friendship ties and interaction. IEEE Transactions on Computational Social Systems, 3(3), 113–119.CrossRefGoogle Scholar
Newman, M. E. J. (2003). The structure and function of complex networks. Siam Review, 45(2), 167–256.CrossRefGoogle Scholar
Ortmann, M., & Brandes, U. (2017). Efficient orbit-aware triad and quad census in directed and undirected graphs. Applied Network Science, 2(1), 13.CrossRefGoogle ScholarPubMed
Park, N., Lee, S., & Kim, J. H. (2012). Individuals’ personal network characteristics and patterns of Facebook use: A social network approach. Computers in Human Behavior, 28(5), 1700–1707.CrossRefGoogle Scholar
Pinar, A., Seshadhri, C., & Vishal, V. (2017). Escape: Efficiently counting all 5-vertex subgraphs. In Proceedings of the 26th International Conference on World Wide Web. International World Wide Web Conferences Steering Committee, pp. 1431–1440.CrossRefGoogle Scholar
Pržulj, N. (2007). Biological network comparison using graphlet degree distribution. Bioinformatics, 23(2), e177–e183.CrossRefGoogle ScholarPubMed
Pržulj, N., Corneil, D. G., & Jurisica, I. (2004). Modeling interactome: scale-free or geometric? Bioinformatics, 20(18), 3508–3515.CrossRefGoogle ScholarPubMed
Robins, G., Pattison, P., Kalish, Y., & Lusher, D. (2007). An introduction to exponential random graph (p*) models for social networks. Social Networks, 29(2), 173–191.CrossRefGoogle Scholar
Rousseeuw, P. J. (1987). Silhouettes: A graphical aid to the interpretation and validation of cluster analysis. Journal of Computational and Applied Mathematics, 20, 53–65.CrossRefGoogle Scholar
Scott, J. (2017). Social Network Analysis. Thousand Oaks: Sage.Google Scholar
Simmel, G. (1908). Sociology: Investigations on the Forms of Sociation. Berlin, Germany: Duncker & Humblot.Google Scholar
Spiliotopoulos, T., & Oakley, I. (2013). Understanding motivations for Facebook use: Usage metrics, network structure, and privacy. In Proceedings of the SIGCHI Conference on Human Factors in Computing Systems. ACM, pp. 3287–3296.CrossRefGoogle Scholar
Stoica, A., & Prieur, C. (2009). Structure of neighborhoods in a large social network. In International Conference on Computational Science and Engineering, CSE 2009, vol. 4. IEEE.CrossRefGoogle Scholar
Watts, D. J., & Strogatz, S. H. (1998). Collective dynamics of “small-world” networks. Nature, 393(6684), 440–442.CrossRefGoogle ScholarPubMed
Wellman, B. (2007). The network is personal: Introduction to a special issue of Social Networks. Social Networks, 29(3), 349–356.CrossRefGoogle Scholar
Wernicke, S. (2006). Efficient detection of network motifs. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 3(4).CrossRefGoogle ScholarPubMed
Wernicke, S., & Rasche, F. (2006). Fanmod: a tool for fast network motif detection. Bioinformatics, 22(9), 1152–1153.CrossRefGoogle ScholarPubMed
Yaveroğlu, Ö. N., Malod-Dognin, N., Davis, D., Levnajic, Z., Janjic, V., Karapandza, R., Stojmirovic, A., & Pržulj, N. (2015). Revealing the hidden language of complex networks. Scientific Reports, 4(1).CrossRefGoogle Scholar
Zhao, Z., Wang, G., Butt, A. R., Khan, M., Kumar, V. S. A., & Marathe, M. V. (2012). Sahad: Subgraph analysis in massive networks using hadoop. In 2012 IEEE 26th International Parallel & Distributed Processing Symposium (IPDPS), pp. 390–401. IEEE.CrossRefGoogle Scholar