skip to main content
10.1145/3097983.3098116acmconferencesArticle/Chapter ViewAbstractPublication PageskddConference Proceedingsconference-collections
research-article
Public Access

Structural Diversity and Homophily: A Study Across More Than One Hundred Big Networks

Published: 04 August 2017 Publication History

Abstract

A widely recognized organizing principle of networks is structural homophily, which suggests that people with more common neighbors are more likely to connect with each other. However, what influence the diverse structures embedded in common neighbors have on link formation is much less well-understood. To explore this problem, we begin by characterizing the structural diversity of common neighborhoods. Using a collection of 120 large-scale networks, we demonstrate that the impact of the common neighborhood diversity on link existence can vary substantially across networks. We find that its positive effect on Facebook and negative effect on LinkedIn suggest different underlying networking needs in these networks. We also discover striking cases where diversity violates the principle of homophily---that is, where fewer mutual connections may lead to a higher tendency to link with each other. We then leverage structural diversity to develop a common neighborhood signature (CNS), which we apply to a large set of networks to uncover unique network superfamilies not discoverable by conventional methods. Our findings shed light on the pursuit to understand the ways in which network structures are organized and formed, pointing to potential advancement in designing graph generation models and recommender systems.

References

[1]
Lada A. Adamic and Eytan Adar 2001. Friends and Neighbors on the Web. SOCIAL NETWORKS Vol. 25 (2001), 211--230.
[2]
Nicomachean Ethics1162a Aristotle and VIII Book 1934. Aristotle in 23 Volumes, Vol. 19, translated by H. Rackham. (1934).
[3]
Lars Backstrom and Jon M. Kleinberg 2014. Romantic Partnerships and the Dispersion of social ties: a netwrok analysis of relationship status on Facebook. In CSCW '14. 831--841.
[4]
Albert-Laszlo Barabasi and Reka Albert 1999. Emergence of Scaling in Random Networks. Science, Vol. 286, 5439 (1999), 509--512.
[5]
Carlo Vittorio Cannistraci, Gregorio Alanis-Lobato, and Timothy Ravasi 2013. From link-prediction in brain connectomes and protein interactomes to the local-community-paradigm in complex networks. Scientific reports Vol. 3 (2013).
[6]
Yuxiao Dong, Yang Yang, Jie Tang, Yang Yang, and Nitesh V. Chawla 2014. Inferring User Demographics and Social Strategies in Mobile Social Networks KDD'14. ACM, 15--24.
[7]
Yuxiao Dong, Jing Zhang, Jie Tang, Nitesh V. Chawla, and Bai Wang 2015. CoupledLP: Link Prediction in Coupled Networks. In KDD '15. ACM, 199--208.
[8]
David Easley and Jon Kleinberg 2010. Networks, Crowds, and Markets: Reasoning about a Highly Connected World. Cambridge University Press.
[9]
P ErdHos and A Rényi 1959. On random graphs I. Publ. Math. Debrecen Vol. 6 (1959), 290--297.
[10]
Péter L. Erdös, István Miklós, and Zoltán Toroczkai 2016. New classes of degree sequences with fast mixing swap Markov chain sampling. CoRR Vol. abs/1601.08224 (2016). showURL%http://arxiv.org/abs/1601.08224
[11]
Michalis Faloutsos, Petros Faloutsos, and Christos Faloutsos. 1999. On power-law relationships of the Internet topology SIGCOMM'99. 251--262.
[12]
Zhanpeng Fang, Xinyu Zhou, Jie Tang, Wei Shao, A.C.M. Fong, Longjun Sun, Ying Ding, Ling Zhou, and Jarder Luo 2014. Modeling Paying Behavior in Game Social Networks. CIKM '14. 411--420.
[13]
Mark Granovetter. 1985. Economic Action and Social Structure: The Problem of Embeddedness. The American Journal of Sociology (1985).
[14]
Mark Granovetter. 1992. Problems of explanation in economic sociology. Networks and organizations: Structure, form, and action Vol. 25 (1992), 56.
[15]
Emily M. Jin, Michelle Girvan, and M. E. J. Newman. 2001. Structure of growing social networks. Phys. Rev. E Vol. 64 (2001), 046132. Issue 4.
[16]
Xiangnan Kong and Philip S Yu 2010. Semi-supervised feature selection for graph classification KDD '12. 793--802.
[17]
Ravi Kumar, Jasmine Novak, and Andrew Tomkins. 2006. Structure and Evolution of Online Social Networks. KDD '06. ACM, 611--617.
[18]
Jérôme Kunegis. 2013. Konect: the koblenz network collection. In WWW'13 companion. 1343--1350.
[19]
P. F. Lazarsfeld and R. K. Merton 1954. Friendship as a social process: A substantive and methodological analysis. Freedom and control in modern society, New York: Van Nostrand (1954), 8--66.
[20]
Jure Leskovec, Lars Backstrom, Ravi Kumar, and Andrew Tomkins 2008. Microscopic evolution of social networks. In KDD '08. 462--470.
[21]
Jure Leskovec, Deepayan Chakrabarti, Jon Kleinberg, Christos Faloutsos, and Zoubin Ghahramani. 2010. Kronecker graphs: An approach to modeling networks. JMLR, Vol. 11, Feb (2010), 985--1042.
[22]
Jure Leskovec, Jon Kleinberg, and Christos Faloutsos. 2005. Graphs over Time: Densification Laws, Shrinking Diameters and Possible Explanations KDD '05. 177--187.
[23]
Jure Leskovec, Kevin J Lang, Anirban Dasgupta, and Michael W Mahoney 2008. Statistical properties of community structure in large social and information networks WWW '08. ACM, 695--704.
[24]
David Liben-Nowell and Jon M. Kleinberg 2007. The link-prediction problem for social networks. JASIST, Vol. 58, 7 (2007), 1019--1031.
[25]
Hao Ma 2014. On measuring social friend interest similarities in recommender systems SIGIR '14. ACM, 465--474.
[26]
Peter V Marsden and Karen E Campbell 1984. Measuring tie strength. Social forces, Vol. 63, 2 (1984), 482--501.
[27]
M. McPherson, L. Smith-Lovin, and J.M. Cook. 2001. Birds of a feather: Homophily in social networks. Annual review of sociology (2001), 415--444.
[28]
R. Milo, S. Itzkovitz, N. Kashtan, R. Levitt, S. Shen-Orr, I. Ayzenshtat, M. Sheffer, and U. Alon. 2004. Superfamilies of evolved and designed networks. Science, Vol. 303, 5663 (March 2004), 1538--1542.
[29]
Alan Mislove, Massimiliano Marcon, Krishna P. Gummadi, Peter Druschel, and Bobby Bhattacharjee. 2007. Measurement and Analysis of Online Social Networks IMC'07. 29--42.
[30]
Mark E. J. Newman. 2001. Clustering and preferential attachment in growing networks. Phys. Rev. E, Vol. 64, 2 (2001), 025102.
[31]
Mark E. J. Newman. 2006. Finding community structure in networks using the eigenvectors of matrices. Phys. Rev. E Vol. 74 (2006), 036104. Issue 3.
[32]
Mark E. J. Newman, Steven H Strogatz, and Duncan J Watts. 2001. Random graphs with arbitrary degree distributions and their applications. Phys. Rev. E, Vol. 64, 2 (2001), 026118.
[33]
Ali Pinar, C. Seshadhri, and V. Vishal 2017. ESCAPE: Efficiently Counting All 5-Vertex Subgraphs WWW '17. 1431--1440.
[34]
Pablo Robles, Sebastian Moreno, and Jennifer Neville. 2016. Sampling of Attributed Networks from Hierarchical Generative Models KDD '16. ACM, 1155--1164.
[35]
Ryan A. Rossi and Nesreen K. Ahmed 2015. The Network Data Repository with Interactive Graph Analytics and Visualization AAAI' 15. 4292--4293. showURL%http://networkrepository.com
[36]
Rok Sosic and Jure Leskovec 2015. Large Scale Network Analytics with SNAP. In WWW '15 Companion. ACM, 1537--1538.
[37]
Jie Tang, Jing Zhang, Limin Yao, Juanzi Li, Li Zhang, and Zhong Su 2008. ArnetMiner: Extraction and Mining of Academic Social Networks KDD '08. 990--998.
[38]
Johan Ugander, Lars Backstrom, and Jon Kleinberg. 2013. Subgraph Frequencies: Mapping the Empirical and Extremal Geography of Large Graph Collections WWW '13. 1307--1318.
[39]
Johan Ugander, Lars Backstrom, Cameron Marlow, and Jon Kleinberg 2012. Structural diversity in social contagion. PNAS, Vol. 109, 16 (2012), 5962--5966.
[40]
Julian R Ullmann. 1976. An algorithm for subgraph isomorphism. J. ACM Vol. 23, 1 (1976), 31--42.
[41]
Brian Uzzi. 1997. Social structure and competition in interfirm networks: The paradox of embeddedness. Administrative science quarterly (1997), 35--67.
[42]
Joe H Ward Jr. 1963. Hierarchical grouping to optimize an objective function. Journal of the American statistical association, Vol. 58, 301 (1963), 236--244.
[43]
Duncan J. Watts and Steven H. Strogatz Jun 1998. Collective dynamics of small-world networks. Nature ( Jun 1998), 440--442.
[44]
Rongjing Xiang, Jennifer Neville, and Monica Rogati. 2010. Modeling relationship strength in online social networks WWW '10. 981--990.
[45]
R. Zafarani and H. Liu 2009. Social Computing Data Repository at ASU. (2009). showURL%http://socialcomputing.asu.eduendthebibliography

Cited By

View all
  • (2024)LPFormer: An Adaptive Graph Transformer for Link PredictionProceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining10.1145/3637528.3672025(2686-2698)Online publication date: 25-Aug-2024
  • (2024)Higher-order homophily on simplicial complexesProceedings of the National Academy of Sciences10.1073/pnas.2315931121121:12Online publication date: 12-Mar-2024
  • (2023)On solving simplified diversified top-k s-plex problemComputers and Operations Research10.1016/j.cor.2023.106187153:COnline publication date: 1-May-2023
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
KDD '17: Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining
August 2017
2240 pages
ISBN:9781450348874
DOI:10.1145/3097983
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 04 August 2017

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. big data
  2. embeddedness
  3. link prediction
  4. network diversity
  5. network signature
  6. social networks
  7. triadic closure

Qualifiers

  • Research-article

Funding Sources

Conference

KDD '17
Sponsor:

Acceptance Rates

KDD '17 Paper Acceptance Rate 64 of 748 submissions, 9%;
Overall Acceptance Rate 1,133 of 8,635 submissions, 13%

Upcoming Conference

KDD '25

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)114
  • Downloads (Last 6 weeks)13
Reflects downloads up to 22 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2024)LPFormer: An Adaptive Graph Transformer for Link PredictionProceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining10.1145/3637528.3672025(2686-2698)Online publication date: 25-Aug-2024
  • (2024)Higher-order homophily on simplicial complexesProceedings of the National Academy of Sciences10.1073/pnas.2315931121121:12Online publication date: 12-Mar-2024
  • (2023)On solving simplified diversified top-k s-plex problemComputers and Operations Research10.1016/j.cor.2023.106187153:COnline publication date: 1-May-2023
  • (2023)Generalizing Homophily to Simplicial ComplexesComplex Networks and Their Applications XI10.1007/978-3-031-21131-7_24(311-323)Online publication date: 26-Jan-2023
  • (2022)On the Effect of Triadic Closure on Network SegregationProceedings of the 23rd ACM Conference on Economics and Computation10.1145/3490486.3538322(249-284)Online publication date: 12-Jul-2022
  • (2022)Attributed Graph Modeling with Vertex Replacement GrammarsProceedings of the Fifteenth ACM International Conference on Web Search and Data Mining10.1145/3488560.3498492(928-936)Online publication date: 11-Feb-2022
  • (2022)Truss-Based Structural Diversity Search in Large GraphsIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2020.302795034:8(4037-4051)Online publication date: 1-Aug-2022
  • (2022)How are You Affected? A Structural Graph Neural Network Model Predicting Individual Social Influence StatusCollaborative Computing: Networking, Applications and Worksharing10.1007/978-3-030-92638-0_24(401-415)Online publication date: 1-Jan-2022
  • (2022)Modeling social network behavior spread based on group cohesion under uncertain environmentConcurrency and Computation: Practice and Experience10.1002/cpe.710134:21Online publication date: 4-Jun-2022
  • (2021)On Influencing the InfluentialProceedings of the 30th ACM International Conference on Information & Knowledge Management10.1145/3459637.3482375(1804-1813)Online publication date: 26-Oct-2021
  • Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media