Hostname: page-component-586b7cd67f-t7czq Total loading time: 0 Render date: 2024-11-24T22:36:11.698Z Has data issue: false hasContentIssue false
  • English
  • Français

Edge overlap in weighted and directed social networks

Published online by Cambridge University Press:  16 February 2021

Heather Mattie Open the ORCID record for Heather Mattie [Opens in a new window]  and
Jukka-Pekka Onnela
Heather Mattie*
Affiliation:
Department of Biostatistics, Harvard University, Boston, MA02115, USA (e-mail: [email protected])
Jukka-Pekka Onnela
Affiliation:
Department of Biostatistics, Harvard University, Boston, MA02115, USA (e-mail: [email protected])
*
*Corresponding author. Email: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

With the increasing availability of behavioral data from diverse digital sources, such as social media sites and cell phones, it is now possible to obtain detailed information about the structure, strength, and directionality of social interactions in varied settings. While most metrics of network structure have traditionally been defined for unweighted and undirected networks only, the richness of current network data calls for extending these metrics to weighted and directed networks. One fundamental metric in social networks is edge overlap, the proportion of friends shared by two connected individuals. Here, we extend definitions of edge overlap to weighted and directed networks and present closed-form expressions for the mean and variance of each version for the Erdős–Rényi random graph and its weighted and directed counterparts. We apply these results to social network data collected in rural villages in southern Karnataka, India. We use our analytical results to quantify the extent to which the average overlap of the empirical social network deviates from that of corresponding random graphs and compare the values of overlap across networks. Our novel definitions allow the calculation of edge overlap for more complex networks, and our derivations provide a statistically rigorous way for comparing edge overlap across networks.

Keywords

edge overlapweighted networksdirected networkssocial networksErdős–Rényi random graphweighted random graphdirected random graph
Type
Research Article
Information
Network Science , Volume 9 , Issue 2 , June 2021 , pp. 179 - 193
Copyright
© The Author(s), 2021. Published by Cambridge University Press

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.)

Footnotes

Action Editor: Stanley Wasserman

References

Banerjee, A., Chandrasekhar, A., Duflo, E., & Jackson, M. (2013). The diffusion of microfinance. Science, 341.Google ScholarPubMed
Bianconi, G., Darst, R., Iacovacci, J., & Fortunato, S. (2014). Triadic closure as a basic generating mechanism of communities in complex networks. Physics Review, 90, 042806.Google ScholarPubMed
Bollobás, B. (1985). Random graphs. New York, NY: Academic Press.Google Scholar
Centola, D. (2018). How behavior spreads: The science of complex contagions. Princeton, NJ: Princeton University Press.Google Scholar
Choumane, A., Awada, A., & Harkous, A. (2020). Core expansion: A new community detection algorithm based on neighborhood overlap. Social Network Analysis and Mining, 10, 30.CrossRefGoogle Scholar
Christakis, N. A., & Fowler, J. H. (2007). The spread of obesity in a large social network over 32 years. The New England Journal of Medicine, 357, 370–379.CrossRefGoogle Scholar
Christakis, N. A., & Fowler, J. H. (2008). The collective dynamics of smoking in a large social network. The New England Journal of Medicine, 358, 2249–2258.CrossRefGoogle Scholar
Elandt-Johnson, R., & Johnson, N. (1998). Survival models and data analysis. New York, NY: John Wiley & Sons.Google Scholar
Erdős, P., & Rényi, A. (1959). On random graphs i. Publicationes Mathematicae, 6, 290–297.Google Scholar
Erdős, P., & Rényi, A. (1960). On the evolution of random graphs. Publications of the Mathematical Institute of the Hungarian Academy of Sciences, 5, 17–60.Google Scholar
Fortunato, S. (2010). Community detection in graphs. Physics, 486, 75–174.Google Scholar
Fowler, J. H., & Christakis, N. A. (2008a). Dynamic spread of happiness in a large scale network: Longitudinal analysis over 20 years in the framingham heart study. BMJ, 337.Google Scholar
Fowler, J. H., & Christakis, N. A. (2008b). Estimating peer effects on health in social networks. Journal of Health Economics, 27, 1400–1405.CrossRefGoogle ScholarPubMed
Garlaschelli, D. (2009). The weighted random graph model. New Journal of Physics, 11, 073005.CrossRefGoogle Scholar
Goodreau, S., Kitts, J., & Morris, M. (2009). Birds of a feather, or friend of a friend? using exponential random graph models to investigate adolescent social networks. EPL, 87, 103–125.Google Scholar
Granovetter, M. (1973). The strength of weak ties. American Journal of Sociology, 78, 1360–1380.CrossRefGoogle Scholar
Harling, G., & Onnela, J.-P. (2016). Impact of degree truncation on the spread of a contagious process on networks. Network Science, 6, 34–53.CrossRefGoogle Scholar
Kim, D., Hwong, A., Stafford, D., Hughes, D., O’Malley, A., Fowler, J., & Christakis, N. (2015). Social network targeting to maximise population behaviour change: A cluster randomised controlled trial. The Lancet, 386, 145–153.CrossRefGoogle ScholarPubMed
Kim, D., O’Malley, A. J., & Onnela, J.-P. (2016). The social geography of american medicine. [Unpublished doctoral dissertation]. Harvard Medical School.Google Scholar
Kumpula, J., Onnela, J.-P., Saramaki, J., Kaski, K., & Kertesz, J. (2007). Emergence of communities in weighted networks. Physical Review Letters, 99, 228701.CrossRefGoogle ScholarPubMed
Landon, B., Keating, N., Barnett, M., Onnela, J.-P., Paul, S., O’Malley, A., … Christakis, N. (2012). Variation in patient-sharing networks of physicians across the united states. JAMA, 308, 265–273.CrossRefGoogle ScholarPubMed
Lin, K. (2007). Motif counts, clustering coefficients and vertex degrees in models of random networks. [Unpublished doctoral dissertation]. University of Oxford.Google Scholar
Onnela, J.-P., Landon, B., Kahn, A. L., Ahmed, D., Verma, H., O’Malley, A., … Christakis, N. (2016). Polio vaccine hesitancy in the networks and neighborhoods of malegaon, india. Social Science and Medicine, 153, 99–106.CrossRefGoogle ScholarPubMed
Onnela, J.-P., Saramaki, J., Hyvonen, J., Szabo, G., Lazer, D., Kaski, K., … Barabasi, A.-L. (2007). Structure and tie strengths in mobile communication networks. PNAS, 104, 7332–7336.CrossRefGoogle ScholarPubMed
Papadatos, N. (1995). Maximum variance of order statistics. Annals of the Institute of Statistical Mathematics, 47, 185–193.CrossRefGoogle Scholar
Porter, M., Onnela, J.-P., & Mucha, P. J. (2009). Communities in networks. Notices of the AMS, 56, 1082–1166.Google Scholar
Saramaki, J., Kivela, M., Onnela, J.-P., Kaski, K., & Kertesz, J. (2007). Generalizations of the clustering coefficient to weighted complex networks. Physical Review E, 75, 027105.CrossRefGoogle ScholarPubMed
Sima, C., Panageas, K., Heller, G., & Schrag, D. (2010). Analytical strategies for characterizing chemotherapy diffusion with patient-level population-based data. Applied Health Economics and Health Policy, 8, 37–51.CrossRefGoogle ScholarPubMed
Skellam, J. G. (1946). The frequency distribution of the difference between two poisson variates belonging to different populations. Journal of the Royal Statistical Society, 109, 296.CrossRefGoogle ScholarPubMed
Staples, P., Ogburn, E., & Onnela, J-P. (2015). Incorporating contact network structure in cluster randomized trials. Scientific Reports 5, 17581.CrossRefGoogle ScholarPubMed
Stuart, A., & Ord, K. (1998). Kendall’s advanced theory of statistics, Volume 1: Distribution theory. Hoboken, NJ: Wiley-Blackwell.Google Scholar
Tore, O. (2013). Triadic closure in two-mode networks: Redefining the global and local clustering coefficients. Social networks, 35, 159–167.Google Scholar
Valente, T. (2005). Network models and methods for studying the diffusion of innovations. In Models and methods in social network analysis (pp. 98–116).CrossRefGoogle Scholar
VanderWeele, T. (2011). Sensitivity analysis for contagion effects in social networks. Sociological Methods and Research, 40, 240–255.CrossRefGoogle ScholarPubMed
Wang, J., Li, M., Wang, H., & Pan, Y. (2012). Identification of essential proteins based on edge clustering coefficient. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 9(4), 1070–1080.CrossRefGoogle ScholarPubMed
Wasserman, S., & Faust, K. (1994). Social network analysis: Methods and applications. New York, NY: Cambridge University Press.CrossRefGoogle Scholar
Watts, D. J., & Strogatz, S. H. (1998). Collective dynamics of ‘small-world’ networks. Nature, 393, 440–442.CrossRefGoogle ScholarPubMed