---
title: "Community Detection in Social Networks through Community Formation Games"
authors:
  - "Wei Chen"
  - "Zhenming Liu"
  - "Xiaorui Sun"
  - "Yajun Wang"
doi: "10.5591/978-1-57735-516-8/IJCAI11-429"
url: "https://ijcai.org/proceedings/2011/429"
pdf: "https://ijcai.org/proceedings/2011/0429.pdf"
venue: "Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence"
year: 2011
pages: "2576-2580"
track: ""
keywords:
---

# Community Detection in Social Networks through Community Formation Games

Wei Chen, Zhenming Liu, Xiaorui Sun, Yajun Wang

*Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence*, pages 2576-2580. DOI: [10.5591/978-1-57735-516-8/IJCAI11-429](https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-429)

## Abstract

We introduce a game-theoretic framework to address the community detection problem based on the social networks’ structure. The dynamics of community formation is framed 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 is often better than other algorithms we evaluated especially when many people belong to multiple communities.