AAAI Publications, Thirty-First AAAI Conference on Artificial Intelligence

Font Size: 
Network, Popularity and Social Cohesion: A Game-Theoretic Approach
Jiamou Liu, Ziheng Wei

Last modified: 2017-02-10


In studies of social dynamics, cohesion refers to a group's tendency to stay in unity, which -- as argued in sociometry — arises from the network topology of interpersonal ties. We follow this idea and propose a game-based model of cohesion that not only relies on the social network, but also reflects individuals' social needs. In particular, our model is a type of cooperative games where players may gain popularity by strategically forming groups. A group is socially cohesive if the grand coalition is core stable. We study social cohesion in some special types of graphs and draw a link between social cohesion and a classical notion of structural cohesion by White and Harary. We then focus on the problem of deciding whether a given social network is socially cohesive and show that this problem is CoNP-complete. Nevertheless, we give two efficient heuristics for coalition structures where players enjoy high popularity and experimentally evaluate their performances.


Computational Social Science;Social Networks;Coordination and Collaboration;Equilibrium;Game Theory

Full Text: PDF