2016/12/26 by Jiamou Liu, Liu, Jiamou, Ziheng Wei +1
Decision Sciences · Physics and Astronomy · Social Sciences · #68Q15 #68T42 #91A12 #91A40 #91Cxx #91D30 #Computational Complexity (cs.CC) #Computer Science and Game Theory (cs.GT) #F.1.3 #FOS: Computer and information sciences #Game Theory and Applications #I.2.11 #J.4 #Multiagent Systems (cs.MA) #Opinion Dynamics and Social Influence #Social Capital and Networks #Social and Information Networks (cs.SI)
paper · pdf · doi:10.48550/arxiv.1612.08351
openalex publication_date 2016/12/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 between members of the group. 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 the classical notion of structural cohesion. 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.