From Acquaintances to Friends: Homophily and Learning in Networks

Mihaela van der Schaar, Simpson Zhang

Abstract

This paper introduces a novel mathematical framework to jointly analyze how homophily, incomplete information, and active learning drive the evolution of social networks. Moving beyond traditional "complete information" assumptions, the model demonstrates that imperfect learning acts as a form of "noise." This noise counter-intuitively reduces network clustering and can lead to the accidental dissolution of mutually beneficial friendships, ultimately resulting in sparser, more diverse networks than those formed under perfect information.

Introduction

Traditional network formation literature often operates under the assumption of "complete information"—the premise that agents possess perfect knowledge of others' "types" (interests, backgrounds, or values) before deciding to establish a link. In practice, social connections typically begin as acquaintanceships and mature into friendships only after a period of mutual learning and experimentation.

The authors address a critical gap in this field: the interaction between the preference for similarity (homophily) and the process of learning about others. If agents have limited capacity for maintaining friendships and a preference for homophily but are prone to errors during the "getting to know you" phase, how does the final network structure change? This research provides a framework for quantitative predictions about network emergence in stochastic environments where information is initially hidden.

Methods

The researchers developed a discrete-time stochastic model that formalizes the transition from initial contact to a stable social structure. The process consists of three primary phases:

  1. Baseline Network ($G^0$): Agents form initial links based on readily available public information and prior beliefs.
  2. Experimentation Phase: Linked agents interact over $T$ periods. During each period, they receive a noisy signal regarding their partner's type and update their beliefs using Bayesian inference. If a partner is perceived to exceed a "social tolerance threshold" ($\delta$), the link is severed.
  3. Link Refinement Phase: Following a final, perfectly revealing signal, agents apply capacity constraints ($c_i$). They must select their most preferred partners to stay within their individual limits, ensuring the final network is pairwise stable—meaning no two agents would mutually prefer to drop an existing link to form a new one together.
The multi-stage process of network formation from baseline to final stable state.

The study utilizes mathematical proofs to establish the uniqueness of these stable networks and employs Monte Carlo simulations (with populations of 10 to 51 agents) to explore the impact of social tolerance and capacity on the resulting network topology.

Key Insights and Results

The model reveals several counter-intuitive properties of networks formed under incomplete information:

The Learning Penalty and Clustering

Because the learning process is inherently noisy, agents frequently drop "good" links (those with similar individuals) by mistake before their true type is fully understood. Consequently, networks formed under incomplete information exhibit significantly lower local clustering coefficients—fewer "friend-of-a-friend" triangles—compared to complete-information benchmarks ($G^*_c$).

Noise as a Diversity Generator

Interestingly, incomplete information can enhance network diversity. By accidentally breaking links with similar neighbors, agents are often forced to seek out others who may be less similar but remain "good enough" to satisfy capacity. This mechanism prevents the extreme social stratification typically observed in perfect-information homophilous models.

The Intermediate Homophily Peak

The divergence between a "perfect" network and a "learned" network (measured by Jaccard distance) is most pronounced at intermediate levels of homophily. When social tolerance is extremely high, almost everyone remains linked; when it is extremely low, few links form at all. The errors introduced by noisy learning have the greatest structural impact in the middle ground of social preference.

Capacity Sensitivity and Life Stages

In scenarios involving "Extreme Agents" (a central group versus fringe outliers), the network structure is highly sensitive to capacity. A marginal increase in a central agent's capacity can lead to sudden, non-monotonic shifts in whether fringe agents are integrated or isolated. Furthermore, when modeling "stages of life" where types stabilize over time, the impact of learning noise is most profound in early stages (e.g., childhood) and gradually fades as agents age.

Conclusion and Future Work

This research highlights that the "noise" of getting to know people is not just a nuisance but a fundamental architect of social structure. While the current model assumes independent signals and static types during experimentation, it provides a robust foundation for future empirical validation. Future work may incorporate "indirect learning" (gossip) or correlated signals to better reflect the complexities of real-world social dynamics, such as those found in academic co-authorship or evolving digital social networks.

Summary updated

Abstract

This paper considers the evolution of a network in a discrete time, stochastic setting in which agents learn about each other through repeated interactions and maintain/break links on the basis of what they learn from these interactions. Agents have homophilous preferences and limited capacity, so they maintain links with others who are learned to be similar to themselves and cut links to others who are learned to be dissimilar to themselves. Thus learning influences the evolution of the network, but learning is imperfect so the evolution is stochastic. Homophily matters. Higher levels of homophily decrease the (average) number of links that agents form. However, the effect of homophily is anomalous: mutually beneficial links may be dropped before learning is completed, thereby resulting in sparser networks and less clustering than under complete information. There may be big differences between the networks that emerge under complete and incomplete information. Homophily matters here as well: initially, greater levels of homophily increase the difference between the complete and incomplete information networks, but sufficiently high levels of homophily eventually decrease the difference. Complete and incomplete information networks differ the most when the degree of homophily is intermediate. With multiple stages of life, the effects of incomplete information are large initially but fade somewhat over time.
BibTeX
@article{schaar2015from,
  author = {Mihaela van der Schaar and Simpson Zhang},
  title = {{From Acquaintances to Friends: Homophily and Learning in Networks}},
  journal = {IEEE JSAC},
  year = {2015},
  doi = {10.1109/jsac.2017.2672238},
}
Figure