Community Detection in Social Networks through Community Formation Games
Wei Chen, Zhenming Liu, Xiaorui Sun, Yajun Wang
In this paper, we introduce a game-theoretic framework to address the community detection problem based on the social networks' structure. The dynamics of community formation is forumated as a strategic game called community formation game: Given a social network, each node is selfish and selects communities to join or leave based on her own utility measurement. A community structure can be interpreted as an equilibrium of this game. We formulate the agents' utility by the combination of a gain function and a loss function. Each agent can select multiple communities, which naturally captures the concept of ``overlapping communities''. We propose a gain function based on Newman's modularity function and a simple loss function that reflects the intrinsic costs incurred when people join the communities. We conduct extensive experiments under this framework; our results show that our algorithm is effective in identifying overlapping communities, and are often better than other algorithms we evaluated especially when many people belong to multiple communities.