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.
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.
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