Structural Diversity and Homophily: A Study Across More Than One Hundred Big Networks
Yuxiao Dong (University of Notre Dame);Reid Johnson (University of Notre Dame);Jian Xu (University of Notre Dame);Nitesh Chawla (University of Notre Dame)
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, such as its positive effect in Facebook and negative one in LinkedIn, corresponding to different networking needs in these networks. We also discover striking cases where diversity violates the principle of homophily, that is, fewer mutual connections may lead to higher tendency to link with each other. We then leverage structural diversity to develop a common neighborhood signature (CNS) for a network, which we use to uncover distinct 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 random graph models and recommender systems.
