Abstract
Many complex networks exhibit homophilic, or assortative degree mixing–the tendency for networked nodes to connect with others of similar degree. For social networks, this phenomenon is often referred to colloquially by the mantra ‘your friends have more friends than you do.’ We analyzed datasets for 16 directed social networks, and report that some of them exhibit both assortative (positive correlations) and disassortative (negative correlations) degree mixing across the totality of their degrees. We show that this mixed trend can be predicted based on the value of Pearson correlations computed for the directed networks. This stands in contrast to previous results reported for social networks that mark them as purely assortative. Finally, we discuss mechanisms by which these trends emerge from random models of network creation.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Albert, R., Barabasi, A.: Statistical mechanics of complex networks. Rev. Mod. Phys. 74, 47 (2002)
Albert, R., Jeong, H., Barabasi, A.: Error and attack tolerance of complex networks. Nature 406, 378–382 (2000)
Bagler, G., Sinha, S.: Assortative mixing in protein contact networks and protein folding kinetics. Bioinformatics 23, 1760–1767 (2007)
Barabasi, A., Albert, R.: Emergence of scaling in random networks. Science 286, 509–512 (1999)
Barabasi, A., Albert, R., Jeong, H.: Mean-field theory for scale-free random networks. Physica A 272, 173–187 (1999)
Barrat, A., Barthelemy, M., Pastor-Satorras, R., Vespignani, A.: The architecture of complex weighted networks. Proc. Natl. Acad. Sci. U.S.A. 101, 3747 (2004)
Bollen, J., Gonalvesj, B., Ruan, G., Mao, H.: Happiness is assortative in online social networks. Artif. Life 17, 237–251 (2011)
Brede, M., Sinha, S.: Assortative mixing by degree makes a network more unstable. arXiv preprint cond-mat, p. 0507710 (2005)
Capocci, A., Servedio, V., Colaiori, F., Buriol, L., Donato, D., Leonardi, S., Caldarelli, G.: Preferential attachment in the growth of social networks: The internet encyclopedia wikipedia. Phys. Rev. E 74, 036116 (2006)
Catanzaro, M., Bogu, M., Pastor-Satorras, R.: Generation of uncorrelated random scale-free networks. Phys. Rev. E 71, 027103 (2005)
Croft, D., James, R., Ward, A., Botham, M., Mawdsley, D., Krause, J.: Assortative interactions and social networks in fish. Oecologia 143, 211–219 (2005)
Feld, S.: Why your friends have more friends than you do. Am. J. Sociol. 96, 1464–1477 (1991)
Foster, J., Foster, D., Grassberger, P., Paczuski, M.: Edge direction and the structure of networks. Proc. Natl. Acad. Sci. U.S.A 107, 10815–10820 (2010)
Fowler, J., Settle, J., Christakis, N.: Correlated genotypes in friendship networks. Proc. Natl. Acad. Sci. U.S.A. 108, 1993–1997 (2011)
Gehrke, J., Ginsparg, P., Kleinberg, J.M.: Overview of the 2003 kdd cup. ACM SIGKDD Newsl. 5, 149–151 (2003)
Holme, P., Kim, B., Yoon, C., Han, S.: Attack vulnerability of complex networks. Phys. Rev. E 65, 056109 (2002)
Hu, H., Wang, X.: Disassortative mixing in online social networks. Europhys. Lett. 86, 18003 (2009)
Isalan, M., Lemerle, C., Michalodimitrakis, K., Horn, C., Beltrao, P., Raineri, E., Garriga-Canut, M., Serrano, L.: Evolvability and hierarchy in rewired bacterial gene networks. Nature 452, 840 (2008)
Johnson, S., Torres, J., Marro, J., Munoz, M.: Entropic origin of disassortativity in complex networks. Phys. Rev. Lett. 104, 108702 (2010)
Leskovec, J., Adamic, L., Adamic, B.: The dynamics of viral marketing. ACM Trans. Web 1, 5 (2007)
Leskovec, J., Huttenlocher, D., Kleinberg, J.: Predicting positive and negative links in online social networks. In: Proceedings of the 19th International Conference on World wide web, pp. 641–650. ACM (2010)
Leskovec, J., Huttenlocher, D., Kleinberg, J.: Signed networks in social media. In: Proceedings of the SIGCHI Conference on Human Factors in Computing Systems, pp. 1361–1370. ACM (2010)
Leskovec, J., Kleinberg, J., Faloutsos, C.: Graphs over time: densification laws, shrinking diameters and possible explanations. In: Proceedings of the Eleventh ACM SIGKDD International Conference on Knowledge Discovery in Data Mining, pp. 177–187. ACM (2005)
Leskovec, J., Kleinberg, J., Faloutsos, C.: Graph evolution: Densification and shrinking diameters. ACM Trans. Knowl. Discov. Data 1, 2 (2007)
Leskovec, J., Lang, K., Dasgupta, A., Mahoney, M.: Community structure in large networks: Natural cluster sizes and the absence of large well-defined clusters. Internet Math. 6, 29–123 (2009)
Litvak, N., van der Hofstad, R.: Uncovering disassortativity in large scale-free networks. Phys. Rev. E 87, 022801 (2013)
Lusseau, D., Newman, M.: Identifying the role that animals play in their social networks. P. Roy. Soc. B-Biol. Sci. 271, S477–S481 (2004)
Maslov, S., Sneppen, K., Zaliznyak, A.: Detection of topological patterns in complex networks: Correlation properties of the internet. Physica A 333, 529–540 (2004)
Massa, P., Salvetti, M., Tomasoni, D.: Bowling alone and trust decline in social network sites. In: Eighth IEEE International Conference on Dependable, Autonomic and Secure Computing, 2009. DASC ’09, pp. 658–663. IEEE (2009)
McPherson, M., Smith-Lovin, L., Cook, J.: Birds of a feather: Homophily in social networks. Annu. Rev. Sociol. 27, 415–444 (2001)
Mislove, A., Marcon, M., Gummadi, K., Druschel, P., Bhattacharjee, B.: Measurement and analysis of online social networks. In: Proceedings of the 7th ACM SIGCOMM Conference on Internet Measurement. pp. 29–42. ACM (2007)
Newman, M.: Scientific collaboration networks I. Network construction and fundamental results. Phys. Rev. E 64, 016131 (2001)
Newman, M.: Scientific collaboration networks II. shortest paths, weighted networks, and centrality. Phys. Rev. E 64, 016132 (2001)
Newman, M.: The structure of scientific collaboration networks. Proc. Natl. Acad. Sci. U.S.A. 98, 404–409 (2001)
Newman, M.: Assortative mixing in networks. Phys. Rev. Lett. 89, 208701 (2002)
Newman, M.: Mixing patterns in networks. Phys. Rev. E 67, 026126 (2003)
Newman, M., Park, J.: Why social networks are different from other types of networks. Phys. Rev. E 68, 036122 (2003)
Park, J., Newman, M.: Origin of degree correlations in the internet and other networks. Phys. Rev. E 68, 026112 (2003)
Piraveenan, M., Prokopenko, M., Zomaya, A.: Assortative mixing in directed biological networks. IEEE/ACM Trans. Comput. Biol. Bioinform. (TCBB) 9, 66–78 (2012)
Ramasco, J., Dorogovtsev, S., Pastor-Satorras, R.: Self-organization of collaboration networks. Phys. Rev. E 70, 036106 (2004)
Richardson, M., Agrawal, R., Domingos, P.: Trust management for the semantic web. In: Fensel, D., Sycara, K., Mylopoulos, J. (eds.) ISWC 2003. LNCS, vol. 2870, pp. 351–368. Springer, Heidelberg (2003)
Salgado, H., Peralta-Gil, M., Gama-Castro, S., Santos-Zavaleta, A., Muiz-Rascado, L., Garca-Sotelo, J.S., Weiss, V., Solano-Lira, H., Martnez-Flores, I., Medina-Rivera, A., Salgado-Osorio, G., Alquicira-Hernndez, S., Alquicira-Hernndez, K., Lpez-Fuentes, A., Porrn-Sotelo, L., Huerta, A.M., Bonavides-Martnez, C., Balderas-Martnez, Y.I., Pannier, L., Olvera, M., Labastida, A., Jimnez-Jacinto, V., Vega-Alvarado, L., del Moral-Chvez, V., Hernndez-Alvarez, A., Morett, E., Collado-Vides, J.: Regulondb v8.0: omics data sets, evolutionary conservation, regulatory phrases, cross-validated gold standards and more. Nucleic Acids Res. 41(D1), D203–D213 (2013)
Serrano, M., Maguitman, A., Bogu, M., Fortunato, S., Vespignani, A.: Decoding the structure of the www: A comparative analysis of web crawls. ACM Trans. Web 1, 10 (2007)
Sorrentino, F., Bernardo, M.D., Garofalo, F.: Synchronizability and synchronization dynamics of weighed and unweighed scale free networks with degree mixing. Int. J. Bifurcat. Chaos 17, 2419–2434 (2007)
Viswanath, B., Mislove, A., Cha, M., Gummadi, K.P.: On the evolution of user interaction in facebook. In: Proceedings of the 2nd ACM SIGCOMM Workshop on Social Networks (WOSN’09) (August 2009)
Vazquez, A.: Growing network with local rules: Preferential attachment, clustering hierarchy, and degree correlations. Phys. Rev. E 67, 056104 (2003)
Watts, D., Strogatz, S.: Collective dynamics of ‘small-world’ networks. Nature 393, 440–442 (1998)
Acknowledgments
This work was funded in part by the US Army’s Environmental Quality and Installations 6.1 basic research program. Opinions, interpretations, conclusions, and recommendations are those of the author(s) and are not necessarily endorsed by the U.S. Army.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Mayo, M., Abdelzaher, A., Ghosh, P. (2014). Mixed Degree-Degree Correlations in Directed Social Networks. In: Zhang, Z., Wu, L., Xu, W., Du, DZ. (eds) Combinatorial Optimization and Applications. COCOA 2014. Lecture Notes in Computer Science(), vol 8881. Springer, Cham. https://doi.org/10.1007/978-3-319-12691-3_42
Download citation
DOI: https://doi.org/10.1007/978-3-319-12691-3_42
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-12690-6
Online ISBN: 978-3-319-12691-3
eBook Packages: Computer ScienceComputer Science (R0)