Selfish Creation of Social Networks

Davide Bilò, Tobias Friedrich, Pascal Lenzner, Stefanie Lowski, Anna MelnichenkoAAAI 2021 · DOI

Abstract

Traditional models of social network formation often rely on stochastic processes like preferential attachment. However, real-world networks are the result of rational agents making selfish decisions. This paper introduces the Social Network Creation Game (SNCG), a game-theoretic model where connection costs are proportional to the topological distance between agents. We demonstrate that this simple mechanism leads to the emergence of small-world properties, high clustering, and power-law degree distributions—a combination that previous game-theoretic models struggled to achieve.

Introduction

Real-world social networks consistently exhibit three core structural properties: the small-world phenomenon (low diameter), high clustering coefficients (local "friend-of-a-friend" triangles), and power-law degree distributions (scale-free hubs). While random graph models can replicate these features, they lack a grounding in individual agency. Existing game-theoretic models have successfully predicted small-world properties but often fail to produce realistic clustering or degree distributions. The SNCG bridges this gap by modeling network growth as a strategic game among selfish agents.

The Social Network Creation Game (SNCG)

The SNCG models network formation as a strategic game among $n$ selfish agents. Each agent (node) seeks to minimize its total cost, which is defined as the sum of the costs of its incident edges and its distance to all other nodes in the network (centrality).

A critical innovation of this model is the distance-dependent cost function. Unlike previous models with constant edge costs, the cost of establishing an edge $uv$ is a convex function $\sigma(d(u,v))$ of the distance between $u$ and $v$ prior to the edge's creation. If $u$ and $v$ have a common neighbor (distance 2), the edge is cheap. If they are far apart, it is expensive.

Figure 1: Illustration of the distance-dependent cost function σ in the SNCG model. Edges connecting distant nodes are more expensive than those connecting nearby nodes.

In this framework:

  • Bilateral Consent: An edge forms only if both agents agree to pay for it, though either can unilaterally delete it.
  • Bridge Costs: Connecting to a node in a different component incurs a maximum cost $\sigma(n)$, representing a "bridge" edge.

Key Insights: The Triangle Incentive

The convexity of the cost function $\sigma$ creates a natural "triangle incentive." Because $\sigma(2)$ is significantly smaller than $\sigma(d)$ for $d > 2$, agents are incentivized to "close triangles" by connecting to their neighbors' neighbors. This mechanism directly leads to the high clustering observed in empirical social data.

Figure 2: An improving move where agents u and v at distance 2 decide to form a cheap edge σ(2), increasing the local clustering coefficient.

Furthermore, the model generates a "dynamic geometry." While no physical distance is assumed, the topological distance within the network itself dictates the cost of future growth. This leads to a hierarchical organization where the local clustering coefficient is inversely proportional to node degree ($CC \sim k^{-1}$), a hallmark of complex networks.

Results and Discussion

Through theoretical analysis and large-scale simulations ($n=1000$ to $3000$), the authors established several key results:

  • Small-World Diameter: The diameter of stable networks is bounded by $\sigma(2) + 2$, resulting in the characteristic logarithmic scaling.
  • Scale-Free Structure: The degree distribution follows a power law $P(k) \sim k^{-\gamma}$ with $2 < \gamma < 3$, matching real-world observations.
  • Convergence: Although the game lacks the formal Finite Improvement Property, simulations almost always converge to a stable state under sequential improving moves.

Conclusion

The SNCG provides a robust game-theoretic foundation for understanding the emergence of complex social structures. By incorporating distance-dependent costs, the model bridges the gap between individual rationality and global network properties. Future research will explore the impact of dynamic agent entry and exit on network stability.

Summary updated

BibTeX
@inproceedings{bilo2021selfish,
  author = {Davide Bilò and Tobias Friedrich and Pascal Lenzner and Stefanie Lowski and Anna Melnichenko},
  title = {{Selfish Creation of Social Networks}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.1609/aaai.v35i6.16655},
}
Figure