Exploiting Social Tie Structure for Cooperative Wireless Networking: A Social Group Utility Maximization Framework

Xu Chen, Xiaowen Gong, Lei Yang, Junshan Zhang

Abstract

In this paper, we develop a social group utility maximization (SGUM) framework for cooperative wireless networking that takes into account both social relationships and physical coupling among users. We show that this framework provides rich modeling flexibility and spans the continuum between non-cooperative game and network utility maximization (NUM) -- two traditionally disjoint paradigms for network optimization. Based on this framework, we study three important applications of SGUM, in database assisted spectrum access, power control, and random access control, respectively. For the case of database assisted spectrum access, we show that the SGUM game is a potential game and always admits a socially-aware Nash equilibrium (SNE). We develop a randomized distributed spectrum access algorithm that can asymptotically converge to the optimal SNE, derive upper bounds on the convergence time, and also quantify the trade-off between the performance and convergence time of the algorithm. We further show that the performance gap of SNE by the algorithm from the NUM solution decreases as the strength of social ties among users increases and the performance gap is zero when the strengths of social ties among users reach the maximum values. For the cases of power control and random access control, we show that there exists a unique SNE. Furthermore, as the strength of social ties increases from the minimum to the maximum, a player's SNE strategy migrates from the Nash equilibrium strategy in a standard non-cooperative game to the socially-optimal strategy in network utility maximization. Furthermore, we show that the SGUM framework can be generalized to take into account both positive and negative social ties among users and can be a useful tool for studying network security problems.

Introduction

In traditional wireless networking, resource management strategies typically fall into two disjoint paradigms: selfish non-cooperative games, where users maximize their own utility at the expense of others, and centralized network utility maximization (NUM), which assumes perfect altruism or central control. Neither extreme accurately reflects modern mobile networks where devices are operated by humans with complex social relationships.

This paper introduces the Social Group Utility Maximization (SGUM) framework, which mathematically integrates human social ties into wireless resource management. By accounting for social awareness, the framework encourages decentralized cooperation, significantly improving network efficiency and moving beyond the "every user for themselves" mentality.

The SGUM Framework

The core innovation of the SGUM framework is the coupling of the social domain with the physical domain. While the physical domain dictates signal interference and hardware constraints, the social domain defines the relationships between users that can be leveraged for cooperative behavior.

Social and physical domain coupling in the SGUM framework.

For any user $n$, their "social group utility" is defined as: $$S_n(x) = U_n(x) + \sum_{m \in \text{friends}} w_{nm} U_m(x)$$ where $U_n$ represents the individual's physical utility (e.g., data rate) and $w_{nm}$ represents the strength of the social tie between user $n$ and user $m$. This formulation allows users to make decentralized decisions that consider the welfare of their social neighbors.

Applications and Theoretical Analysis

The authors apply SGUM to three critical wireless networking scenarios:

  • Database-Assisted Spectrum Access: Modeled as a Potential Game, the authors develop a distributed algorithm based on Glauber Dynamics. This allows users to reach a Socially-aware Nash Equilibrium (SNE) that asymptotically approaches the global optimum as social ties strengthen.
  • Power Control: Modeled as a Supermodular Game, the analysis shows that increasing social awareness naturally leads users to adopt lower-power strategies, reducing overall network interference.
  • Random Access Control: The framework derives a unique SNE for channel access frequency, demonstrating that social awareness reduces collision probabilities in shared channels.

Key Insights: Bridging the Gap

A fundamental contribution of the SGUM framework is its role as a mathematical bridge. It spans the continuum between the two traditional extremes of network modeling.

The continuum of social awareness in network optimization.

As social tie strength ($w_{nm}$) varies from zero to its maximum value, the network's behavior migrates monotonically from a standard non-cooperative Nash Equilibrium to the socially optimal solution found in NUM. This suggests that even moderate levels of information sharing and social awareness can drastically reduce the "Price of Anarchy" in decentralized networks.

Validation and Results

The framework was validated using both synthetic Erdos-Renyi graphs and real-world traces from the Brightkite location-based social network. Key findings include:

  • Interference Reduction: SGUM reduced system-wide interference by up to 23% compared to non-cooperative models.
  • Real-World Gains: Even with sparse real-world social ties, the framework achieved 13-15% performance gains over selfish models.
  • Scalability: The distributed spectrum access algorithm scales efficiently, with convergence time growing at approximately $O(\ln N)$, where $N$ is the number of users.

Conclusion

The SGUM framework provides a flexible and realistic approach to cooperative wireless networking. By exploiting existing social structures, it enables efficient decentralized resource management. Future work will address the overhead of utility exchange, the challenges of accurate tie estimation in dynamic environments, and the security implications of malicious actors within the social graph.

Summary updated

Abstract

In this paper, we develop a social group utility maximization (SGUM) framework for cooperative wireless networking that takes into account both social relationships and physical coupling among users. We show that this framework provides rich modeling flexibility and spans the continuum between non-cooperative game and network utility maximization (NUM) -- two traditionally disjoint paradigms for network optimization. Based on this framework, we study three important applications of SGUM, in database assisted spectrum access, power control, and random access control, respectively. For the case of database assisted spectrum access, we show that the SGUM game is a potential game and always admits a socially-aware Nash equilibrium (SNE). We develop a randomized distributed spectrum access algorithm that can asymptotically converge to the optimal SNE, derive upper bounds on the convergence time, and also quantify the trade-off between the performance and convergence time of the algorithm. We further show that the performance gap of SNE by the algorithm from the NUM solution decreases as the strength of social ties among users increases and the performance gap is zero when the strengths of social ties among users reach the maximum values. For the cases of power control and random access control, we show that there exists a unique SNE. Furthermore, as the strength of social ties increases from the minimum to the maximum, a player's SNE strategy migrates from the Nash equilibrium strategy in a standard non-cooperative game to the socially-optimal strategy in network utility maximization. Furthermore, we show that the SGUM framework can be generalized to take into account both positive and negative social ties among users and can be a useful tool for studying network security problems.
BibTeX
@article{chen2016exploiting,
  author = {Xu Chen and Xiaowen Gong and Lei Yang and Junshan Zhang},
  title = {{Exploiting Social Tie Structure for Cooperative Wireless Networking: A Social Group Utility Maximization Framework}},
  journal = {IEEE/ACM Trans. Networking},
  year = {2016},
  url = {https://openreview.net/forum?id=bdB7y7mJEQ},
}
Figure